nqs_1's blog

Can we solve this problem without binary search?
By nqs_1, history, 7 years ago, In English

here is the link to the problem PROBLEM According to the editorial, this problem is solved using binary search +dp, but can we solve it with 2-D dp or any other way without using binary search ?

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

Comments Comments (2)
| Write comment?
»
7 years ago, hide # |
← Rev. 2  
Vote: I like it -22 Vote: I do not like it

If you drop the CP mentality of using algorithms that have good asymptotic runtime and deterministic results, we can use local search to find the answer as well, I didn't try. But it looks promising.

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

    I was looking for some other algorithm other than that mention above for deterministic results.

    → Reply