### PROBLEM LINK:

**Author:** Hruday Pabbisetty

**Tester:** Mugurel Ionut Andreica

**Editorialist:** Kirill Gulin

### PROBLEM

For each cell (i,j) of the N imes N grid 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, L is the length of x in decimal representation. Precalculate these values for each N from 1 to 2 \cdot 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 the N imes 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 imes5 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 the answer for (N-1) imes (N-1) grid is different from the N imes N grid. Actually, N imes N grid fully contains the whole (N-1) imes(N-1) grid with one more row at the bottom and one more column at the right (the right-bottom cell exists in both this row and this 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) imes(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(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 be 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).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.