### rhymehatch's blog

By rhymehatch, history, 6 weeks ago, https://codeforces.com/problemset/problem/1358/C

I cannot think simply enough.

First I amused myself with the number of possible paths:

$\frac{(x_2-x_1+y_2-y_1)!}{(x_2-x_1)!(y_2-y_1)!}$

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:

$\bigg(\sum\limits_{k=1}^{i+j-1} k \bigg) - j + 1 = \frac{(i+j-1)(i+j)}{2}-j+1$

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. 645, math, Comments (5)
 » 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.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   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.
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   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.
•  » » » » Thanks a lot, I see it now!I'm wondering when will I start thinking as simply as that!
 » Auto comment: topic has been updated by rhymehatch (previous revision, new revision, compare).