INOI 2018 Problem(2 Two Paths )

Here is the link to the problem
I am not able to get the logic behind the problem. I know this question has been asked before but not much have been explained there.
Can anyone explain me a detailed solution for this problem. Any help will be appreciated:)

I am Two Paths, the true heir of Salazar Slytherin. I felt that it would not be safe to open the Discuss Forum of CodeChef while I was at school, so I left behind a diary of my 16-year old self, hoping that one day, I would be able to finish Salazar Slytherin’s noble work. And haven’t I told you? - killing mudbloods hasn’t been my target for a while. My new target, for the past few months, has been you. How is that you escaped the curse of one of the greatest wizards of all time? How is it that you escaped with nothing but a scar while Lord Voldemort’s powers were destroyed?

Coming to the problem, there are two hints I can give you :
Use prefix sums and Dynamic programming. There is a detailed editorial in this Forum. Find it by yourself.

1 Like

I saw the editorial prior to asking this question and I couldn’t understand it as the author only briefly described the solution(according to me).

Not a lot many potterheads in the community

You’d do better by asking beneath the editorial itself.

I would have but the editorial itself was 3 years old. So I thought even if I’d ask my question it would most probably go unanswered as the editorial was inactive now.

Untrue, I wrote the editorial and I regularly respond to non trivial help requests (no, I won’t debug your code)

1 Like

I’m sorry but I never came across your editorial. The link which I’m talking about is this one…
Particulary this comment in the editorial by ista2000,

For second one, The observation was that, we can take one path and calculate the total sum without a second path using dp[i][j][k] = min/max(dp[i-1][j][k], dp[i-1][j-1][k-1])+prefix_sum[i][j]. We calculate this two times, once for min and once for max and then we can use the prefix sum intuition to subtract min-dp from max-dp. It’s not clear enough here, but you might get an essence.

Other than this link and this comment, I haven’t found any other thing.

Could you please provide me with the link of the editorial written by you.(I tried searching but am not able to find it).

Also, try searching by the problem code rather than the problem name.

Thank you so much man. Sorry if any trouble caused.

1 Like

Will do. If I had known that it would have saved you the trouble.