linkret's blog

By linkret, history, 3 months ago, In English,

The task I want to discuss is 739E - Гоша выходит на охоту. While the official solution is a greedy algorithm sped up enough to pass the time limit, I recently came upon another solution. The main idea is to speed up the obvious dp approach, where we define dp[i][x][y] as the maximum expected number of caught pokemon in the prefix of first i pokemon, if we throw at most x A-pokeballs and at most y B-pokeballs. The computation of each state is O(1), so the complexity of this solution is O(n^3).

Read more »

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