https://codeforces.net/problemset/problem/1358/C
I cannot think simply enough.
First I amused myself with the number of possible paths:
I realized it is useless due to the inputs going to $$$10^9$$$.
Then I focused on figuring out how to calculate value for given coordinate $$$(i,j)$$$.
It took me a while to figure that out:
Then I did not know what to do, so I started calculating all of the possible sums. Then I realized that there is a minimal sum and a maximal sum. Minimal is obtained by going through row $$$x_1$$$ for all $$$y_1$$$ to $$$y_2$$$. Then down the column $$$y_2$$$ for all $$$x_1+1$$$ to $$$x_2$$$. Maximal by first going down by column $$$y_1$$$ and then going right through row $$$x_2$$$.
Given the huge number of possible paths ($$$\approx {10}^{1000000000}$$$) I assumed that the difference between maximal and minimal sum will contain all numbers. So it is max-min+1 .
Then I just quit trying to work out the formula with a pencil and wrote the whole sum calculation in WolframAlpha:
Simplify[
Sum[Sum[i,{i, 1, x2+j-1}] -j +1, {j,y1,y2}]
+ Sum[Sum[i,{i, 1, j+y1-1}] -y1+1, {j,x1,x2-1}]
- Sum[Sum[i,{i, 1, x1+j-1}] -j +1, {j,y1,y2}]
- Sum[Sum[i,{i, 1, j+y2-1}] -y2+1, {j,x1+1,x2}]
]
The output was $$$(y_1-y_2)(x_1-x_2)$$$. I added 1 and tada.
Insane waste of time. I still have no idea how to think simply enough to not go through all of these steps.
just consider the minimum sum and the maximum sum of the paths. It is easy to see that there is a path of the sum of any number between those two.
Yes, thanks, I realized that, but I do not know how to avoid the symbolic math stuff.
How can I realize $$$(y_1-y_2)(x_1-x_2)+1$$$ without explicitly formulating expressions for maximal and minimal sum?
The thinking steps that lead me to solution are too complicated. It took me an hour to solve something that has a 1 line solution and that does not even care about the formula of a particular cell or sums of sums.
I am sure people who solved this at the contest in very short time think very simply and have not seen the problem before.
When you change the subpath of (down -> right) into (right -> down), it is decrementing the sum by 1. Then how many times do you have to make this step, in order to make the maximum sum path (down -> ... -> down -> right -> ... -> right) into the minumum sum path (right -> ... -> right -> down -> ... -> down)? They are the same questions.