help to optimize code : world cup game

Question

Hello All,

Below is my code:
https://code.sololearn.com/cfipDys44gW0

input and output is explained in code.

Request your view on the same in terms of optimization.

Thanks a lot for your input in advance...!

Answer 1

Looks good enough to me, but you can do better, time complexity-wise. At the moment it's O(n²) but you can knock it down to O(n log n).

After you sort the lists you only need to go through the list once:

If you can beat the current opponent, move both iterators ahead by 1 and increase cnt; if the opponent is stronger, move only the opponent iterator ahead by 1 and don't increase cnt. (That's saying you lose the race by sending your weakest man, from the end of the list.)

Answer 2

wow, you actually used regex for this task?

seems like you know too much for your own good.

Answer 3

Ketan Lalcheta
You’re learning the wrong things and applying them wrongly, but more power to you I guess :-)

Answer 4

What is so bad about using cin repeatedly? Like:
while(N > 0)
cin >> i;
v.push_back(i);
N--;
what is so bad about this code that you had to resort to regex?

Answer 5

I suggest reading your textbook about how cin and variable scope works.

If you still don’t understand, and you think that obtaining series of inputs using cin is too hard, then just use regex.

Stick to what works :-)

Answer 6

Schindlabua thanks a lot for your time and suggestions...

I also thought earlier to just sort both vector and compare for more power of team's player to increment count.... In such scenario, I was getting 5 as output instead of 7 which is expected...

Now I tried to implement the way you suggested and still result is 5 against expected result of 7.

Same code updated and new method method_new is there to implement the changes. Am I missing something or what?

Answer 7

Bobby Fischer learning new things during this covid pandemic :)

Answer 8

Oops is regex is not good ? I thought rather than taking input so many times using cin , I would go for regex and split it into vector.

Let me know what best is for this solution and will improve code and hence learning

Answer 9

Cin>>i on same variable was not working...is it good to declare I inside while loop?

Answer 10

OMG...! A blunder , A total mess.

I was doing vector<long long> v(N) which allocated N elements with zero as values. Then i tried cin and did emplace_back. while result was iterated on N size, all initial values were zero...... That's why I switched to regex considering that it is issue. Generally we handle input through code so not much in cin.

finally you suggested to read and it strike my mind that something is wrong definitely. so debug everything again and here that default initialization is mess.

vector<long long> v(N) changed to vector<long long> v; v.reserve(N) and everything is fine..

You saved me by opting something bad just because of code issue at other point.. A big thanks

Answer 11

why do you need to ‘reserve’? the function does literally nothing.

or you can do v(N) and assign each input to index v[i]

when you found that your code didn’t work, why didn’t you think of debugging your code by printing the content of your vectors?

Answer 12

yeah v[i] is better than doing push_back and reserve.

Answer 13

In my earlier approach of erasing element, I was doing it wrong in terms of time complexity. I just could have done setting value of iterator as -1 rather than performing costly erase operation. setting -1 value will never impact upper_bound.

seems my pain is still upper_bound. How to get rid of the same to optimize code further.