l_l's blog

Problem 547C "Wrong answer on test 3"
By l_l, history, 9 years ago, In English

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://mirror.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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

__gcd(x, 0) causes undefined behavior .... implement your own gcd. see here

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thnx.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    By the way how did you calculate the time it takes. I'm just curious for future problems. Thanks again

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply