You are not logged in. Please login at www.codechef.com to post your questions!

×

VK18 - Editorial

1
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.

This question is marked "community wiki".

asked 12 Dec '17, 20:53

kefaa's gravatar image

6★kefaa
1128
accept rate: 0%

edited 13 Feb, 15:02

hruday968's gravatar image

4★hruday968
1.7k210


@manvscode use a vector instead

link

answered 17 Dec '17, 18:11

pratikshit_1's gravatar image

1★pratikshit_1
212
accept rate: 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

mike11's gravatar image

0★mike11
1
accept rate: 0%

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

link

answered 17 Dec '17, 17:38

manvscode's gravatar image

3★manvscode
413
accept rate: 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

russell12's gravatar image

0★russell12
1
accept rate: 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]; )

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

link

answered 28 Dec '17, 11:56

ruhul1995's gravatar image

1★ruhul1995
6717
accept rate: 6%

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

(07 Jan, 20:48) deebhatia3★

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;

}

link

answered 21 Jan, 10:21

madan117's gravatar image

0★madan117
1
accept rate: 0%

link

answered 06 Jun, 01:05

vjvjain0's gravatar image

4★vjvjain0
617
accept rate: 7%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,026
×1,897
×186
×23

question asked: 12 Dec '17, 20:53

question was seen: 2,371 times

last updated: 06 Jun, 01:05