Codeforces 645 Div2

Still doing Div. 2 in 2020—great.

I will keep competing this year. I refuse to believe I cannot get there.

C. Celex Update

Problem C gives a number grid of the gaz-giz kind, a start, and an end. For each possible route, calculate the sum on the path and count how many distinct sums are possible from start to end.

What did I do in the contest? I worked out the exact value at a given point.

Then I realised the answer was simply the difference between the maximum and minimum. Yet I began working out how to calculate each of them. Later I saw that even doing that would overflow long long, and my mindset started to collapse.

Someone sent me this after the contest.

I do not know what I was thinking. The later formula, x * y + 1, was guessable too, but I somehow invented a counterexample that seemed to disprove it; later I found that I had calculated my own counterexample incorrectly.

void solve() {
    SLLA(xx1);
    SLLA(yy1);
    SLLA(xx2);
    SLLA(yy2);
 
    ll ans = (xx2 - xx1 ) *(yy2 - yy1) + 1;
    printf("%lld\n", ans);
}

Afterward I found Problem D easy: binary search finishes it. The only thing to watch is one long long overflow; I pushed through it with double.