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 ?

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3567 |

3 | tourist | 3520 |

4 | maroonrk | 3421 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3309 |

8 | Benq | 3283 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 194 |

2 | antontrygubO_o | 193 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | Radewoosh | 168 |

6 | tourist | 166 |

7 | Um_nik | 165 |

8 | ko_osaga | 163 |

9 | McDic | 162 |

9 | Ashishgup | 162 |

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 ?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/07/2020 09:25:01 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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

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.