Блог пользователя msg555

Автор msg555, 10 лет назад, По-английски

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://mirror.codeforces.com/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://mirror.codeforces.com/contest/498/submission/9251777

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

  • Проголосовать: нравится
  • +45
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

I also TLE'd on test case 65.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

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.