VK18 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Hruday Pabbisetty
Tester: Mugurel Ionut Andreica
Editorialist: Kirill Gulin

PROBLEM

For each cell (i,j) of the N \times 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 \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 the answer for (N-1) \times (N-1) grid is different from the 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 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)\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(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.

1 Like
2

Total time complexity for precalculating the answers for each possible grid size is O(N) obviously, where N=106. Answering a query takes O(1) time since all the answers are precalculated, hence the total time for queries is O(T). Facebook

3

but precalculation of 10^6 numbebrs requires an array of size 10^6 which is giving segmentation fault.

4

@manvscode use a vector instead

1 Like
5

Questions of the editorial have been asked and reformed for the success of the reverse the editorial. All the reviews have been shred with thesis writing help uk
for the formation of the wonderful stints and formation of untie good ideals for the readers of the editorial.

6

@Mugurel Ionut Andreica

what is 2LL in your solution…please explain

( g[i] = g[i - 1] + 2LL * (sval[2 * i - 1] - sval[i]) + val[2 * i]; )

link to ur answer :
https://s3.amazonaws.com/codechef_shared/download/Solutions/DEC17/Tester/VK18.cpp

7

LL stands for long long. 2LL means storing the number 2 in a long long memory meaning 64 bit.

8

#include <stdio.h>

int store[2000005]={0,-1,2,-3,4,-5,6,-7,8,-9};

int sumx(int a){
int z=a,r,sum=0;
while(z>0){
if(store[z]){
sum+=store[z];
break;
}
r=z%10;
if(r%2)
sum-=r;
else
sum+=r;
z=z/10;
}
store[a]=sum;
return abs(sum);
}

int main(void) {
// your code goes here
int t,n,i,j,x=4;
long long int tot,storet[1000005]={0,2,12,36};
for(n=4;n<=1000000;n++){
tot=storet[n-1];
x+=abs(store[(n<<1)-2])+abs(store[(n<<1)-3])-abs(store[n]);

    tot+=sumx(n<<1)+2*sumx((n<<1)-1)+(x<<1);
    storet[n]=tot;
}
scanf("%d",&t);
while(t--){
    scanf("%d",&n);
    printf("%llu\n",storet[n]);
}
return 0;

}

9

Editorial : https://letsdocp.wordpress.com/2018/06/06/codechef-problem-total-diamonds/