msg555's blog

Performance Anomaly on R284B — Name That Tune
By msg555, 10 years ago, In English

After TLE'ing this problem in the contest I've been unable to come up with a satisfactory explanation as for why it does so. The mystery is why does my solution behave so much worse on case 65 than any of the other previous max sized cases. Since I cannot clearly see a reason why I feel it's possible this could happen again. I'm not looking for suggestions on how to make my code faster.

My solution is listed at http://codeforces.me/contest/498/submission/9250377

I've noticed other solutions that did manage to pass using essentially the same algorithm are also significantly slower on case 65 than any of the other cases. For example http://codeforces.me/contest/498/submission/9251777

Link to problem — http://codeforces.me/problemset/problem/498/B

  • Vote: I like it
  • +45
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I mentioned the same thing here: http://codeforces.me/blog/entry/15353#comment-202844

I also TLE'd on test case 65.

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

This may or may not be relevant, but I remember a similar thing happening in a topcoder round. You can see the thread here: http://apps.topcoder.com/forums/?module=Thread&threadID=708376

TLDR: There are things called "denormal" numbers that take longer to do operations with

→ Reply
»
10 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Probably, problem is as usual in denormalized numbers.
you may see last my two submissins, I've added if(cur < 1e-12) cur = 0 and my code become 5 times faster

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

Want to see some magic? Here's your solution with minor changes.

Edit: others already posted about denormalized numbers while I was writing this comment.

→ Reply