cschill's blog

Unable to find the reason for the wrong Answer
By cschill, history, 5 months ago, In English

I was trying this problem — https://codeforces.com/problemset/problem/348/A

Its a simple binary search problem but it shows wrong answer — https://codeforces.com/contest/348/submission/235257891

I changed my high to 1e14 from 1e16 and its accepted. I am unable to understand what was the reason behind the error.... please let me know if anyone have a clue about it :))

Thanks

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

»
5 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

This is due to integer overflow, as you might have guessed.

The variable sum in the function check will overflow as it can be at max n * (x — 1), if all elements in the array are 1.

Since n can go up to 1e5 and x is (1e16) / 2 = 2e15 in the first iteration, n * (x — 1) is about 2e20 which is beyond the 64 bit integer limit

→ Reply