4o2a's blog

Optimality of today's E problem
By 4o2a, history, 18 months ago, In English

In today's E problem, my submission used exactly n-1 queries for each n to give out the answer. Can this be proven to be the least number of queries needed or is a better bound achievable?

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

Comments Comments (4)
| Write comment?
»
18 months ago, hide # |
 
Vote: I like it -80 Vote: I do not like it

E was one of all time CRINGE problems.

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

Obviously, you can binary search for the first $$$i$$$ such that $$$f(1, i) \gt 0$$$, but it's still $$$O(n)$$$ queries in the worst case.

→ Reply
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    why only for first, like we can binary search for second also such that f(1,j) > f(1,i), then we can fill 0 in between i and j and 1 at j and continue so on. Is it also n queries ??

    → Reply