nqs_1's blog

By nqs_1, history, 2 months 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

»
2 months ago, # |
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.

  • »
    »
    2 months ago, # ^ |
      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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Alright. In any case, don't discard the idea of using non-deterministic algorithms. They can be quite powerful (even if you cannot prove their optimality/runtime). They work because they simply work (i.e. proof by AC). XD.