Problem C — Codeforces Round #645 (Div. 2)

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

https://codeforces.net/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.