Mr.ink's blog

439D why does ternary search get accept?
By Mr.ink, 10 years ago, In English

For problem 439D there is a ternary search solution that works very well but this is a ternary search on integers and it can go into an endless loop but the author of questions says it works correct.Why does this solution work?if hi = 3 , lo = 1 when answer is 2 ?The ternary search in this state can not reach 2. here is the code http://mirror.codeforces.com/contest/439/submission/6814294

  • Vote: I like it
  • -15
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for (int it = 0; it < 100; it++)

there are no endless loop, cause only of 100 iterations.

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

    You are right but look if hi = 3 and lo = 1 and answer is 2 then it can not reach 2 and will print 3;

    → Reply