Hello,
I have solved Question 547C, but when I submit my answer it gives me runtime error for gnuG++11 and wrong answer on test three for gnuG++ even though the test case works for me.
Here's a link to my submission:
http://codeforces.com/contest/547/submission/11443674
Basically, my approach to this problem is that I save the relation between all foam heights (whether coprime or not) in a two-dimensional vector "bool coprime". Then using that info I update the new score by calculating the difference in score after a beer is placed or removed. The time complexity of this approach is O(n^2).
I would appreciate it if anyone can figure out what's going on.
Thanks
__gcd(x, 0) causes undefined behavior .... implement your own gcd. see here
Are you sure that this caused a problem? I think that you're simply throwing random guesses and if I'm not mistaken CF uses compiler with correct implementation of __gcd not that stupid described one. See here: http://codeforces.com/blog/entry/13410?#comment-216706
maybe I didn't dig into this topic enough. Thanks for correcting me.
Even if it passed Test #3, your solution will definitely time out in a later case. O(N2) for N = 2 * 105 would take like 7 minutes to run, let alone that it would use over 40 GB of memory.
I'd look for a different approach instead of trying to find the bug on that one.
Thnx.
By the way how did you calculate the time it takes. I'm just curious for future problems. Thanks again
Well, that depends on the CPU you run the program on, but as a general rule, divide the number of operations by 100M and you'll have an estimate of how many seconds it will take.
merC!