VK18 - Editorial
#PROBLEM LINK:
[Practice][1]
[Contest][2]
**Author:** [Full name][3] [Hruday Pabbisetty][3]
**Tester:** [Full name][4] [Mugurel Ionut Andreica][4]
**Editorialist:** [Oleksandr Kulkov][5] [Kirill Gulin][5]
#PROBLEM
For each cell $(i,j)$ of the grid of size $N \times N$ define its value as the absolute difference between the sum of even digits and sum of odd digits in decimal representation of $i+j$. You are to find the total sum of cell values in the grid.
# QUICK EXPLANATION:
Precalculate answers for each $N$ from $1$ to $10^6$ in ascending order for answering a query in $O(1)$ time. For doing this find how the answer for matrix of order $N - 1$ differs from the answer for the matrix of order $N$.
# EXPLANATION:
Denote $f(x)$ as the total number of diamonds in room with number $x$. It can be easily calculated in $O(L)$ time by splitting $x$ into digits, where $L$ is the length of $x$ in decimal representation. Precalculate these values for each $N$ from $1$ to $10^6$ at the beginning. It requires $O(NL)$ time.
## Subtask 1 solution.
Iterate over all rooms $(i,j)$ $(1 \leq i,j \leq N)$ in $O(N^2)$ time and add $f(i+j)$ to the answer.
Total time complexity: $O(TN^2)$.
## Subtask 2 solution.
Notice there are $O(N)$ different values of $i+j$ in a $N \times N$ grid. Indeed, if $1 \leq i \leq N$ and $1 \leq j \leq N$ then $2 \leq i + j \leq 2N$ and each $x = i+j$ in range $[2; 2N]$ can be reached. Moreover, any $x$ occurs exactly $min(x -1, 2N-x+1)$ times in the grid. To understand this write out room numbers as a grid and notice that the same $x$ occurs only in diagonals parallel to the secondary diagonal of the grid. Here are room numbers of the $5\times5$ grid:
$\begin{matrix}
2& 3 & 4 & 5 & 6 \\
3& 4 & 5 & 6 & 7 \\
4& 5 & 6 & 7 & 8 \\
5& 6 & 7 & 8 & 9 \\
6 & 7 & 8 & 9 & 10
\end{matrix}$
It’s easy to see the written above is true. So iterate through each $x$ in range $[2; 2N]$ and add $f(x) \cdot min(x-1,2N-x-1)$ to the answer.
Total time complexity: $O(TN)$.
## Subtask 3 solution.
Let’s find out how different is the answer for $(N-1) \times (N-1)$ grid from $N \times N$ grid. Actually, $N \times N$ grid fully contains the whole $(N-1)\times(N-1)$ grid with one more row at the bottom and one more column at the right (the right-bottom cell exists in both the row and the column). Write out two grids of sizes $N-1$ and $N$ for some $N$ as above for a better understanding.
Go through each $N$ from $1$ to $10^6$ in ascending order. Suppose now that for some $N$ answers for each grid with less size has been already processed. A part of the current grid of size $(N-1)\times(N-1)$ with left bottom cell is just the answer for the grid of size $N-1$. The last column cells have coordinates of the form $(i,N)$ for each $1 \leq i \leq N$. So the last column increases the answer for the current grid by $f(1 + N) + f(2 + N) + f(3 + N) + … + f(N + N)$. Similarly, the last row cells have coordinates of the form $(N, i)$ for each $1 \leq i \leq N$ and this row increases the answer by $f(N + 1) + f(2 + N) + … + f(N + N)$. The right-bottom cell $(N, N)$ is counted twice so the answer should by decreased by $f(N + N)$. Easy to see the sums above are the same, so eventually the last row and column increase the answer by $2 \cdot (f(N+1)+f(N+2)+…+f(2N)) – f(2N)$.
Still we need to find $f(N+1) + f(N+2) + … + f(2N)$ fast since the naive summation has $O(N)$ complexity.
We can use the fact that such sum can be easily recalculated for $N+1$ if we know it for $N$. Let’s just find the difference between them. Substituting $N+1$ instead of $N$ in the sum above gives the sum $f(N+2) + f(N+3) + … + f(2N) + f(2N+1) + f(2N+2)$. The difference is $(f(N+2) + f(N+3) + … + f(2N) + f(2N+1) + f(2N+2)) – (f(N+1) + f(N+2) + … + f(2N)) = f(2N+1)+f(2N+2)-f(N+1)$. So we can maintain some variable $S$ denoting $f(N+1) + f(N+2) + … f(2N)$ for each $N$. Initially for $N = 1$ $S = f(1 + 1) = 2$. Then, for some $N$ the answer for the appropriate grid is the answer for the grid of size $N-1$ increased by $2\cdot S - f(2N)$. For the next step $S$ should be increased by $f(2N+1)+f(2N+2)-f(N+1)$.
Total time complexity for precalculating the answers for each possible grid size is $O(N)$ obviously, where $N = 10^6$. Answering a query takes $O(1)$ time since all the answers are precalculated, hence the total time for queries is $O(T)$.
[1]: http://www.codechef.com/problems/VK18
[2]: http://www.codechef.com/COOK85/problems/VK18
http://www.codechef.com/DEC17/problems/VK18
[3]: http://www.codechef.com/users/alex_2oo8
http://www.codechef.com/users/hruday968
[4]: http://www.codechef.com/users/djdolls
http://www.codechef.com/users/mugurelionut
[5]: http://www.codechef.com/users/melfice
http://www.codechef.com/users/kefaa
[333]: http://www.codechef.com/download/Solutions/DEC17/Setter/VK18.cpp
[444]: http://www.codechef.com/download/Solutions/DEC17/Tester/VK18.cpp
[555]: http://www.codechef.com/download/Solutions/DEC17/Editorialist/VK18.cpp