0

help to optimize code : world cup game

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...!

9th Jun 2020, 10:50 AM
Ketan Lalcheta
Ketan Lalcheta - avatar
13 Respuestas
+ 2
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.)
9th Jun 2020, 12:47 PM
Schindlabua
Schindlabua - avatar
+ 1
wow, you actually used regex for this task? seems like you know too much for your own good.
9th Jun 2020, 1:51 PM
Bobby Fischer
Bobby Fischer - avatar
+ 1
Ketan Lalcheta You’re learning the wrong things and applying them wrongly, but more power to you I guess :-)
9th Jun 2020, 2:10 PM
Bobby Fischer
Bobby Fischer - avatar
+ 1
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?
9th Jun 2020, 2:19 PM
Bobby Fischer
Bobby Fischer - avatar
+ 1
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 :-)
9th Jun 2020, 2:35 PM
Bobby Fischer
Bobby Fischer - avatar
0
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?
9th Jun 2020, 2:08 PM
Ketan Lalcheta
Ketan Lalcheta - avatar
0
Bobby Fischer learning new things during this covid pandemic :)
9th Jun 2020, 2:09 PM
Ketan Lalcheta
Ketan Lalcheta - avatar
0
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
9th Jun 2020, 2:12 PM
Ketan Lalcheta
Ketan Lalcheta - avatar
0
Cin>>i on same variable was not working...is it good to declare I inside while loop?
9th Jun 2020, 2:24 PM
Ketan Lalcheta
Ketan Lalcheta - avatar
0
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
9th Jun 2020, 3:10 PM
Ketan Lalcheta
Ketan Lalcheta - avatar
0
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?
9th Jun 2020, 3:22 PM
Bobby Fischer
Bobby Fischer - avatar
0
yeah v[i] is better than doing push_back and reserve.
9th Jun 2020, 4:31 PM
Ketan Lalcheta
Ketan Lalcheta - avatar
0
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.
9th Jun 2020, 4:34 PM
Ketan Lalcheta
Ketan Lalcheta - avatar