Hello guys,
I haven’t been able to figure out solution of this problem from March Circuits. It would be great if anyone can suggest me an approach to this problem.
P.S : I am a noob in DP so pls explain as you are explaining to a newbie xD
Thanks 
What you have got to notice is that if a cell (i, j) is set to point upward, all cells lying in (0,0) to (i,j) shall point upward, so as to avoid explosion. Similarly, if a cell (i,j) is set to point rightward, cell lying in (i,j) to (n-1,n-1) shall also point rightward, so as to avoid collision. This allows us to use dp.
I recommend you to try this editorial first, and then check the hint.
Click to view
Store two integers dp[i][j][0], the sum of powers when (i,j) is pointing upward and dp[i][j][1], the sum of powers when (i,j) is pointing rightwards. Notice how you can calculate dp[i][j][0] and dp[i][j][1] from dp[i-1][j][0], dp[i-1][j][1], dp[i][j-1][0] and dp[i][j-1][1].
Use the idea of prefix sums on rows and columns during state transitions mentioned above.
Click to view
I can spoil the fun of solving this problem, but atleast give some time to above mentioned hints. If you solve the problem with above hints, you’ll never have to say in future that you are a noob in dp.
Comment if you still need help.
3 Likes
Did it!!
Thanks for the detailed explanation and great words
Also, I couldn’t solve Big Array Number problem from the same contest. Can you give some tips on that. Sorry for being greedy xD.
Thanks again
It’s nice to be a bit grredy if you are stuck in a problem 
About Big Array Number problem, I’m not exactly sure, but here’s the idea.
Make a segment tree, with lazy propagation idea. Updates concerning whole range of current node shall never be pushed down, but stored in auxiliary array. For matching query, take into account net effect of main node, and auxiliary array of all nodes visited to reach current node. We can prove that logN nodes will be visited.
Sqrt dec also works, but I’m not sure if it will pass the time limit.
Haven’t implemented, so, try and do share the solution.
1 Like
Haha. You are correct.
Thanks for the hints of problem. I will definitely try it!!