×

VK18 - Editorial

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.

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)$.

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)$.

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.

This question is marked "community wiki".

6★kefaa
1138
accept rate: 0%

1.7k210

 1 @manvscode use a vector instead answered 17 Dec '17, 18:11 21●2 accept rate: 0%
 0 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 link This answer is marked "community wiki". answered 17 Dec '17, 05:04 0★mike11 1 accept rate: 0%
 0 but precalculation of 10^6 numbebrs requires an array of size 10^6 which is giving segmentation fault. answered 17 Dec '17, 17:38 41●3 accept rate: 0%
 0 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. link This answer is marked "community wiki". answered 18 Dec '17, 19:00 1 accept rate: 0%
 0 @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]; ) answered 28 Dec '17, 11:56 67●1●7 accept rate: 6% LL stands for long long. 2LL means storing the number 2 in a long long memory meaning 64 bit. (07 Jan '18, 20:48)

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;


}

1
accept rate: 0%

 0 answered 06 Jun '18, 01:05 4★vjvjain0 91●1●9 accept rate: 7%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,490
×2,086
×188
×23

question asked: 12 Dec '17, 20:53

question was seen: 2,503 times

last updated: 06 Jun '18, 01:05