ANUTHM - Did you solve it with logic, or by observing the pattern?

Did you solve it with logic, or by observing the pattern? Because personally, I didn’t find the logic very intuitive.

Observing the pattern, of course. What else would it be…

By logic, although the way i got to that logic is a bit weird :stuck_out_tongue:

First thing that came to my mind was obviously DP. Then I realized that it won’t work in time limit as the complexity was O(M * N * T). Then I thought it was a hard problem but later I when I saw that it had the most submissions after the easiest problem I thought there might be some key observation that I need to make to solve it :slight_smile: So I started thinking about it and proved(a bit of a casual proof) that whatever value is stored at (x, y) will always end up going at (n, m).

I firstly observed the pattern, then I understood the logic. So, both of them.

There’s a logic too, which is explained in the editorial.
So you made a few cases of your own and saw that the sum of elements in every diagonal is 1?

1 Like