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.
↵
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.