Quick Explanation for cooking the Soup.
For each bowl of soup,we calculate how much volume of soup would be there if it was created on the first hour.
(V’[i]=V[i]+(sigma(T[j]),1<=j<=i-1))
We maintain all existing soup volume in a multiset.
When an hour i start, we add V[i] into the multiset.Then we remove all volume with-V[K]<=sigma(T[j],1<=j<=i)
those are the volume that disappear on hour i-and easily calculate the total volume of soup evaporated in them.
All the volume left in the multiset contrubute exactly T[i]*(Size of the multiset).
As the multiset is sorted, and each volume is added and subtracted only once, the total complexity is O(N*log(N))
Quick Explanation for Bad Cells
Let’s turn the field on 45 degrees transforming cells coordinates (x, y) in (x + y, x - y).
Then the cell (x, y) will be bad if one of the conditions occurs x ≡ 0 (mod 2a) or y ≡ 0 (mod 2b).
So good cells will be divided into sectors by vertical and horizontal lines.
For each sector, it is possible to determine the coordinates of a pair of numbers,
the first number that will rise during the transition to the next right sector,
and the second pair number will increase during the transition to the next upper sector.
From the sector with coordinates (x, y) can go to any nearby on the side of the sector,
visiting at least one bad cell, ie in (x - 1, y), (x + 1, y), (x, y - 1) and (x, y + 1).
Since the numbers 2a and 2b have the same parity, then from the sector (x, y) can also go to the sector on the diagonal,
and visiting a bad cell, ie in (x - 1, y + 1), (x + 1, y - 1), (x - 1, y - 1) and (x + 1, y + 1).
Then it turns out that the minimum number of bad cells,
which should be visited on the way out of from the sector (x1, y1) to sector of (x2, y2) equals max(|x1 - x2|, |y1 - y2|).
Let’s transform the coordinates of the initial and final cells as described rule above.
Then find sectors which contain our cells and calculate answer with formula above.
Quick Explanation for Fibonacci
In this problem we had some Fibonacci number modulo 1013 f
and we had to determine the position of its first occurence in Fibonacci sequence modulo 1013.
Let a and b be two different coprime modula — divisors of 10^13.
Let F be the actual Fibonacci number such that F mod 10^13=f.Then (f mod a= F mod a) and (f mod b=F mod b).
Find all occurences of number (f mod a) in Fibonacci sequence modulo a period.
Find all occurences of number (f mod b) in Fibonacci sequence modulo b period.
Let’s fix a pair of such occurences. Let the occurence modulo a be in position i, and the occurence modulo b be in position j.
Let t(m) be Fibonacci sequence modulo m period.
From the Chinese Remainder Theorem, it follows that t(ab) = LCM(t(a), t(b)) (remember that a and b are coprime).
Then from fixed occurences of f in periods of sequences modulo a and b we can recover the position of occurence of f in period of sequence modulo ab.
It could be done by solving the following Diophantine equation: i + t(a) * x = j + t(b) * y. We can solve it using a simple bruteforce of one of the roots.
If the occurence in sequence modulo ab period ( we have just found it) is u, then every occurence f in Fibonacci sequence modulo 10^13 period
can be represented as t(ab) * k + u. Then let’s bruteforce k and find all occurences in sequence modulo 10^13 period.
To determine Fibonacci number on position α + t(ab) from known Fibonacci number on position α, we need to multiply the vector (Fα, Fα + 1) and some matrix.
Let’s choose a = 5^9 and b = 2^13. Note that there is no number that occur Fibonacci sequence modulo a or b period more than 8 times.
That means that total count of pairs will never be greater than 64. For each occurence we’ll bruteforce not more than
t(10^13)/LCM(t(5^9),t(2^13)) numbers.