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


CHEFHACK - Editorial



Before posting your question with asking for help try this test.
The answer should be 436746489.
If it is hard to debug this test for you, here is the helpful information.
It contains the number of unsuccessful tries for each cell
or -1 if the cell was hacked by the "Grid Hacking Mechanism".
If it still hard to debug try another smaller test that contains answer and similar debug information as above.
If you pass this test then read carefully the bold tip in the QUICK EXPLANATION section.
If you follow this tip but still have WA then post your question and we will help you.



Author: Khadar Basha
Tester: Anton Lunyov
Editorialist: Anton Lunyov




Connected component, Depth-first search, Flood fill algorithm, Sieve of Eratosthenes


You are given N × N grid filled by non-negative integers. We single out 3 types of numbers on the grid: primes, even non-primes and odd non-primes. For each number we define the cost as follows: for the prime number it is the id of this prime in the 0-based list of all primes, for even non-prime number X it is X / 2, and for odd non-prime number Y it is (Y + 3) / 2 (the cost of a number is the shortcut for the number of unsuccessful tries to crack the server secured by the password equals to this number; the mentioned formulas for cost in all three cases are clear from the problem statement).

Two even non-prime numbers that share a side on the grid are connected to each other. The same is true for odd non-prime numbers. But prime number is not connected to any other number. In this way all cells of the grid form a bidirectional graph that has several connected components (each cell having prime number is a separate component). The cost of the component is defined as the cost of the first cell in this component that we meet traversing the grid in row-major order. Now your task is to find the sum of costs over all components.


Actually, most of the job has already made while we reformulated the problem above. Now you simply need to loop over all cells of the grid in row-major order and if we meet the unvisited cell we add its cost to the answer and run DFS from this cell in the graph constructed above to mark other cells of its connected component as visited.

Tip: the total cost could overflow 32-bit integer type. Use 64-bit type instead.

To be able to find the cost of the prime cell fast enough we need to run Sieve of Eratosthenes in advance (even before input the very first test) in order to find all prime numbers. Then we need to create the array of size 107 that contains for each prime its id. Now the cost of each number can be found in O(1).

The overall complexity is O(K * log log K + T * N * N).


As mentioned above at first we run Sieve of Eratosthenes to identify all prime numbers:

isPrime[0] = false
isPrime[1] = false
for i = 2 to K do
    isPrime[i] = true
for i = 2 to sqrt(K) do
    if isPrime[i] then
        for j = i * i to K with step i do
            isPrime[j] = false
where K = 107 − 1.

Next we fill array of costs. We maintain variable prime_id which is equal to the number of primes we met so far:

prime_id = 0
for i = 0 to K do
    if isPrime[i] then
        cost[i] = prime_id
        prime_id = prime_id + 1
        cost[i] = i div 2 + (i mod 2) * 2
Note the formula for the cost for non-prime number.

Now we can input grids and traverse them. We use two-dimensional array A[][] for the initial grid. Also we use another two-dimensional array visited[][] to check visited cells, which could be filled by false while input the grid:

for i = 1 to N do
    for j = 1 to N do
        read A[i][j]
        visited[i][j] = false

Now we can traverse the grid. If we meet visited cell we skip it. Otherwise we always add its cost to the answer and if it is non-prime then run DFS to fill its connected component:

total_cost = 0 // this should be a variable of 64-bit integer type!
for i = 1 to N do
    for j = 1 to N do
        if (visited[i][j]) then
        total_cost = total_cost + cost[A[i][j]]
        if (not isPrime[A[i][j]]) then
            DFS(i, j)

DFS(i, j) is the recursive routine that traverse the grid passing from the cell (i, j) to its neighbors in the graph constructed above:

DSF(i, j)
    if (not visited[i][j]) then
        visited[i][j] = true
        for (x, y) in {(i+1, j), (i-1, j), (i, j-1), (i, j+1)} do
            if (not isPrime[A[x][y]]) and (A[x][y] is of the same parity as A[i][j]) then
                DFS(x, y)
Note that we pass to the cell (x, y) only if the number in it is non-prime and of the same parity as in the cell (i, j). Missing of any of these checks will definitely lead to WA. Also see tester's solution as a reference to one of the convenient ways how to implement loop:
        for (x, y) in {(i+1, j), (i-1, j), (i, j-1), (i, j+1)} do


For some languages (like Java or Python) the recursive implementation of DFS could lead to runtime error due to stack overflow. In this case you need to implement either non-recursive DFS or BFS (breadth-first search) to mark cells of each connected component. Another alternative is to use disjoint-set data structure to do the same job. But this way requires some additional thinking.

The alternative very fast method to find all primes is to use Atkin Sieve invented in 2004 by Atkin and Bernstein. It allows to find all primes up to K using O(K / log log K) operations. Check it out first 6 related problems to train yourself at fast implementation of sieve.

The remaining 3 problems involves flood fill algorithm.


Author's solution can be found here.
Tester's solution can be found here.


SPOJ - 6488. Printing some primes - TDPRIMES
SPOJ - 6470. Finding the Kth Prime - TDKPRIME
SPOJ - 6488. Printing some primes (Hard) - PRIMES2
SPOJ - 6489. Finding the Kth Prime (Hard) - KPRIMES2
SPOJ - 3505. Prime Number Theorem - CPRIME
SPOJ - 11844. Binary Sequence of Prime Number - BSPRIME
UVA - 352 - The Seasonal War
UVA - 469 - Wetlands of Florida
UVA - 785 - Grid Colouring

This question is marked "community wiki".

asked 15 Jan '13, 15:00

anton_lunyov's gravatar image

6★anton_lunyov ♦
accept rate: 12%

edited 22 Jan '13, 02:38

fantastic editorial. loved it!

(15 Jan '13, 16:25) bugkiller3★

@editorialist : great work to give additional links to similar problems :) thanks. Things are really changing nicely in new year :)

(15 Jan '13, 20:20) the_c0der1★

Its Nice.....

(16 Jan '13, 15:04) jaydentyler250★

only mistake was... i used 32bit integer for total cost instead of 64 feels like kill-me-now


answered 15 Jan '13, 16:42

charchit's gravatar image

accept rate: 0%

I'm in the same page :(!

(15 Jan '13, 17:11) tyrant2★

same here.. :(

(15 Jan '13, 18:36) kshitij83★


Actually i did the same solution described above in Python but it didn't work (i got Time Limit Exceeded), you can check my attempt here and here.

But actually, i was able to find another algorithm for this problem that got accepted, the idea was that i only check for immediate neighbors of any server to know if it should be included or not, of course this may lead to count a server while it shouldn't (i.e. it should have been already cracked), but to be aware of this case i created a Python dictionary that hold information about which server cracked which one (cracked_by) and then each time i visit a server i check if i should update the cracked_by of the immediate neighbors to know if i added wrongly a server if yes i discard the value from the result.

You can check my solution here, feel free to post any feedback.



answered 16 Jan '13, 02:52

mouad's gravatar image

accept rate: 0%

Quite neat.
I was stuck for a while thinking that you process this test
4 1 4
4 4 4
1 1 1

But are you sure that this solution has complexity O(N * N) per test?
What about test of the structure:
4 1 4 1 4 1 4 1 4 1
1 1 1 1 1 1 1 1 1 1
4 1 4 1 4 1 4 1 4 1
1 1 1 1 1 1 1 1 1 1
4 1 4 1 4 1 4 1 4 1
1 1 1 1 1 1 1 1 1 1
4 1 4 1 4 1 4 1 4 1
1 1 1 1 1 1 1 1 1 1
4 1 4 1 4 1 4 1 4 1
1 1 1 1 1 1 1 1 1 1
It seems to me that finding roots of paths here will be O(N) in average making your solution to be O(N3).

(17 Jan '13, 11:54) anton_lunyov ♦6★

If I'm correct, it would only mean that our test data are weak :)

Well, it's impossible to predict with what approaches contestants can come up with to have a test failing each approach.

(17 Jan '13, 12:02) anton_lunyov ♦6★

@anton_lunyov: First of all thanks for your feedback, as for the two test cases that you gave, AFAIK my solution will return 6 and 52 respectively which is correct, and as for the complexity well i am not sure what is the correct answer ;-) specially i don't know what is the worst case to get roots of the two paths, but what i can tell you is that it will only take O(n**2) for the last test case that you gave, finding the roots will be only O(1) (2 extra iteration at max).

(19 Jan '13, 02:44) mouad2★

Can you that what is my problem ID is :1681905


answered 15 Jan '13, 15:59

shikimaru's gravatar image

accept rate: 0%


Did you test you program at least somehow?
They produce wrong result on any possible test.
I don't know. Consider for example this one:
The correct answer is 1, while you return -0 (yeah, with this crappy minus sign)

One suggestion is that you should use long long type for unsec and print it as printf("%lld ",unsec).

(15 Jan '13, 16:15) anton_lunyov ♦6★

are you sure this test case my program give wrong answer because in my computer answer is 1 not -0.are you sure that you check correct submit my program id is:1681905

(15 Jan '13, 17:00) shikimaru3★

I look here
Only admins, setter and tester have access to this.
Your answer for 8th test which is very small test is
where ... is some other digits (like hundreds of digits more)
Try to run your code on using GNU C++ compiler against this test case.

(15 Jan '13, 17:22) anton_lunyov ♦6★

The editorial is pretty nice. I wonder what was wrong with my implementation. Can you please have a look and let me know my error. It would be great. I'm unable to figure out.


answered 15 Jan '13, 16:33

coolmind's gravatar image

accept rate: 0%


Try to use usual array instead of queue.
You could simply have a loop
for(int k=0;k<len;k++)
where len is the total number of added elements to the queue and it will be increased by 1 after adding each new cell.

I think the queue is the real bottleneck of your solution.

(17 Jan '13, 02:45) anton_lunyov ♦6★

Thanks for spending time to look into the code. As suggested, I replaced queue with usual array. But now I get a runtime error. Now what could be reason for this.

Could you please look into it?

(17 Jan '13, 19:07) coolmind2★

It is quite hard to follow your code.
Try to combine two cases odd and even.
Clearly we could do check like
server[hackX[k]][hackY[k]+1]%2 == server[i][j]%2
so that code for bfs will be only one time in the solution.

Also why don't you declare
int x=hackX[k], y=hackY[k]
and use them everywhere?
It will simplifiy a code drastically.

(17 Jan '13, 19:22) anton_lunyov ♦6★

I made all the suggested improvements. The code looks less cumbersome now. Also, the code for BFS is written only once. Instead of using a separate matrix to store the visited nodes, I make the value of node to -1 when it is visited. That helps me to preserve memory. I hope that would clarify my approach.

Still I get runtime error. I am puzzled. Could you help me please?

(18 Jan '13, 13:28) coolmind2★

You should mark server[x][y-1] = -1 when you add (x,y-1) to hackX, hackY. Otherwise you could add the same cell several times. Probably this is also the reason of TLE for bfs with queue. Maybe fixing this in the first submission will make it faster.

For example. You have (0,0), then you add (0,1) and (1,0) and then when you consider (0,1) you add (1,1) but not mark it, hence when you consider (1,0) you will add (1,1) again.

So the reason of RE is that you add more than 350^2 elements in all.

(18 Jan '13, 13:37) anton_lunyov ♦6★

Thanks anton_lunyov.

Got the solution accepted. I applied the same to my previous solution(queue) one. Both worked. Execution time of array one is better though.

Thanks for devoting your time.

(18 Jan '13, 14:50) coolmind2★

Just for your notice.
The maximal time for array solution is 0.38 while for queue is 0.96.

0.96 is only for special test where we have no primes and each component consists of just one cell.

For other tests time <= 0.5.

Probably the reason of such slow down on this particular test is creating queue 350^2 times.

(18 Jan '13, 18:53) anton_lunyov ♦6★
showing 5 of 7 show all

Nice editorial. I have an unrelated question though. I used BFS instead of DFS. Everything else was same as you suggested in your editorial. But I was getting Wrong answer somehow. I tried it with many test cases generated by hand and it was working fine. How should I approach in finding problems in my code in such scenarios. Any help will be highly appreciated.

BTW, my problem submission was

If anyone can point to what test cases my program was failing, it will be really helpful. Thanks in advance.


answered 15 Jan '13, 16:34

vikram535's gravatar image

accept rate: 0%

I used BFS as well. I got TLE. :(

(15 Jan '13, 18:00) coolmind2★

@vikram535 You have repeated the same mistake as hundreds of contestants and tens of contestants who asking for help after the contest.

You should use 64-bit integer type long long for the answer and output it either using cout or %lld specifier.

Regarding the bfs, see my answer above in the response
In short, you should use usual array instead of queue.

(17 Jan '13, 02:52) anton_lunyov ♦6★

I first used an integer array of size 10e7 for the sieve, but it ran out of memory though...had to half the size of the array and cancel all the even numbers.


answered 15 Jan '13, 18:28

jbupit's gravatar image

accept rate: 0%

Actually the main your issue is declaring all arrays inside main().
They are stored in a stack which is quite limited and hence you received runtime error.
The displayed memory 1500M is just the bug in codechef system.
The stack size seems to be 32M hence initially you have used 40M and get RE
but then half the size to 20M and all became fine.

(17 Jan '13, 11:28) anton_lunyov ♦6★

@anton_lunyov you mean to say if I declare my array globally I can use upto 1500M memory?

(17 Jan '13, 19:33) charchit2★

Yes. Even 1536M :)

(17 Jan '13, 19:36) anton_lunyov ♦6★

What is problem in my solution.. I am getting WA


answered 15 Jan '13, 18:42

shasha1s2's gravatar image

accept rate: 0%

Your output for this test
0 4 8 12
0 1 9 24
0 1 9 12
0 8 16 18
is 16 while should be 2.

(17 Jan '13, 11:29) anton_lunyov ♦6★

How is it coming out to be 2. Can you please explain?

(21 Jan '13, 13:13) nishantshah1★

Its just for testing '1' at place (1,1)... Got my mistake... its a silly one in function kr1(int,int)....wrote pass[i][j] instead of typ[i]][j]... damn shit....

(21 Jan '13, 18:18) shasha1s22★

To implement grid hacking in java, if i use an ArrayDeque or a LinkedList, i get TLE( ), while if i change the data structure to ArrayList( ), i get one of the fastest execution times in java. Any reason as to why this is happening?


answered 15 Jan '13, 21:09

karan173's gravatar image

accept rate: 0%

edited 16 Jan '13, 00:54

Thanks for such a detailed editorial. I learnt a lot. But still my program is not getting submitted. If I am not asking too much, can I get a sample test case for which my code is failing. My submission id is 1724659. Thanks.


answered 15 Jan '13, 21:35

sarfarajey's gravatar image

accept rate: 0%


@sarfarajey Read the bold tip in the beginning of the editorial.

(17 Jan '13, 01:48) anton_lunyov ♦6★

I had the same solution in Java (except I used the Sieve of Atkin and instead of a boolean[][] I changed the original input array directly), but I kept getting WA :/.

Can somebody check my solution to see what's wrong? I tried several test cases, but all of them printed out the right answer...


answered 16 Jan '13, 01:50

kullalok's gravatar image

accept rate: 14%

You have repeated the same mistake as hundreds of contestants and tens of contestants who asking for help after the contest.

You should use 64-bit integer type for the answer.

Also your solution has stack overflow error:
Exception in thread "main" java.lang.StackOverflowError

(17 Jan '13, 11:33) anton_lunyov ♦6★

I got AC after using Sieve of Eratosthenes but I want to implement it by another method by which I couldn't. We can find all prime numbers less than 10^7 by simply making another prime number program and copy the output and assign it to array in our program arr[]={all prime numbers less than 10^7 that we already have.}. Now just apply a for loop for(i=0;i<arr.size;i++) arr1[arr[i]]=i; now just find if any number is a prime by if(arr1[num]!=0) return arr1[num];

but In the above approach I couldn't assign the whole set of prime numbers to arr[] manually by copy paste. I am getting error "/usr/lib/gcc/i486-linux-gnu/4.3.2/../../../../lib/crt1.o: In function _start': /home/aurel32/tmp/glibc/glibc-2.9/csu/../sysdeps/i386/elf/start.S:115: undefined reference tomain' collect2: ld returned 1 exit status" when I am submitting my code.


answered 17 Jan '13, 14:37

h_201001039's gravatar image

accept rate: 0%

This is because source limit is 50000B.
You can't submit a program having more than 50000 characters.
Probably the system react on such submissions in such weird way.
Hence in this problem such cheat with storing primes in the code is not possible.

(17 Jan '13, 14:50) anton_lunyov ♦6★

@anton_lunyov : I don't think its a cheat. Its the first thought that came in my mind after reading this question. :)

(17 Jan '13, 16:16) h_2010010392★

Can the admins tell what's wrong with
In other note :- The tester solution is not getting complied on gcc. Need to include stdio.h.


answered 21 Jan '13, 12:49

chamanchindi's gravatar image

accept rate: 0%


Your code is very long. Delete at least all this annoying debugging printf before asking for help.

(21 Jan '13, 15:04) anton_lunyov ♦6★

New id is 1742822. Thanks.

(21 Jan '13, 16:05) chamanchindi3★

Try this test:
The correct answer is 436746489.
While your answer is 458527862.

(21 Jan '13, 23:06) anton_lunyov ♦6★

I have updated the editorial. Please read and follow the SUGGESTION at the beginning of editorial.

(22 Jan '13, 02:38) anton_lunyov ♦6★

That's great anton_lunyvon. Thanks a lot.

(22 Jan '13, 09:59) chamanchindi3★

I'm getting WA my solution is this


answered 21 Jan '13, 16:15

cyberghost23's gravatar image

accept rate: 0%

Hi There, your solution did not work on the following test case.
1034 5036 5076 8099 6543 7853
0 2 4 6 8 10
1 5 7 9 13 15
1034 5036 5076 8099 6543 7853
1034 5036 5076 8099 6543 7853
1034 5036 5076 8099 6543 7853

The answer is 9076. It is giving 5087.

(21 Jan '13, 16:27) chamanchindi3★

i have checked all the test cases which u have provided in the editorial and it gives right answer.I am unable to figure out the problem.


answered 22 Jan '13, 09:59

akashaple's gravatar image

accept rate: 0%

In routines oddserver and evenserver you should check before accessing valid[k][l] (or valid[m][n]) that cell (k,l) (or (m,n)) lies inside the grid. Probably this is the reason.

(22 Jan '13, 12:36) anton_lunyov ♦6★

@anton_lunyov (valid[i][j] is itself a array which has 1 at (i,j) if i,j lies inside the grid otherwise valid[i][j] contains 0) it is also workin well .please help to sort out this problem ,still unable to fiure out the problem

(23 Jan '13, 15:53) akashaple2★

In evenserver() instead of

     return 0;

you should write

 if(k<0 || k>=n || l<0 || l>=n || !valid[k][l])
     return 0;

where n is the size of the grid that should be defined globally.

The same should be applied to oddserver() but be careful you are using variable n there as y-coordinate of the cell.

If you will have troubles with fixing it you can refer to my edit of your code that got AC:

(23 Jan '13, 16:04) anton_lunyov ♦6★

I habe a problem in my solution based on the editorial which seems to be more a compiler/c++ problem then an algorithmic problem. I got the error "Access violation reading location 0x01A4B7A4" when trying to read from my big prime array. Can anyone help?


answered 23 Jan '13, 13:30

safadurimo's gravatar image

accept rate: 0%


Your array for primes is too small. Add one zero to K. Like here:

(23 Jan '13, 14:15) anton_lunyov ♦6★

Greatly appreciated, Anton! I should have noticed it by myself!

(23 Jan '13, 22:48) safadurimo4★

Please have a look at the following solution :

It gave correct results for the test cases mentioned in the editorial here, those in the problem statement and some cases generated by myself. But still it displays 'Wrong Result' here.

Please help!


answered 24 Jan '13, 13:19

avinrox's gravatar image

accept rate: 10%

Use printf("%lld\n", tries).
I should add this tip to the editorial.
Several guys who asked for help all have this bug:
they use long long but print it as %d

(24 Jan '13, 14:27) anton_lunyov ♦6★

thank you for the correction. i tried another approach.. facing a similar problem..

(24 Jan '13, 23:35) avinrox2★

Wow! Your solution fails for only one grid among 80 grids we have in official test data. It is a grid having the following structure: N=350, a[i][j] are all even non-primes, except very small percent of odd non-primes. Each group of odd passwords is generated as a boundary of a small square.

Your solution is quite hard to follow so I can only suggest you to generate test of the above structure for smaller size and compare your answer with the answer generated by the correct program.

(25 Jan '13, 01:08) anton_lunyov ♦6★

approach is as : 1. generate prime numbers index. 2. read data (simultaneously add attempts for primes). store odd/even flag for remaining. 3. get_neighbors() will store 'valid' neighbors for each data. 'valid' means - (i) it is either [i+1][j] or [i][j+1]. (ii) it has to be of same type (odd/even) non-primes. 4. 'tags[i][j]' for each member is assigned as 'i*N+j'. 5. arrange_and_compute() will do traversal over all members and update 'valid' neighbors with lowest tags among them. this is done in loop until there is no change in an iteration.

this was an attempt on amortization. will see!

(25 Jan '13, 15:11) avinrox2★

Can you please tell whats wrong with my code...its giving correct output for test cases..


answered 27 Jan '13, 15:54

shubham2892's gravatar image

accept rate: 0%

You should not pass through the cells containing 2 in mark_check_even. Try this test:

0 4 2 12
2 1 9 24
0 1 9 12
2 8 2 18

The answer is 12 while your answer is 2.

(27 Jan '13, 16:02) anton_lunyov ♦6★

Thanks a lot...

(27 Jan '13, 16:30) shubham28922★

my code is giving a runtime error(NZEC).Can anyone plz tell what is the problem?


answered 05 Feb '13, 10:55

progpassion's gravatar image

accept rate: 0%

Can anybody look at my solution and explain why am i getting Runtime error(segmentation fault). i cant see why..:(


answered 22 Jun '14, 19:28

dcod's gravatar image

accept rate: 27%

my code runs fine on my machine but shows wrong answer on submission Please help my solution is here


answered 23 Oct '14, 23:06

vishal7695's gravatar image

accept rate: 0%



Hi, I just studied DFS and then searched this problem through question tags. I passed the given test cases and also the cases given in editorial. But still couldn't get AC.

I made these solutions:

1) ---> It gave me WA

2) ---> It gave me RE

The only difference between both these solutions is that i have changed my counter variable which is needed to be printed from long to long long.

I would be so glad if anyone could explain me the bug.


answered 17 Nov '15, 18:26

torque's gravatar image

accept rate: 17%

struggling from a day with my code here it gives correct answer to all cases ever in discussion or editorial but still getting a WA. help would be greatly appreciated


answered 23 May '16, 19:02

sd_7's gravatar image

accept rate: 0%

Hey I solved the problem with same approach as given above but it's showing wrong answer. Please can anyone help


answered 21 Jul '17, 08:16

jha_gaurav98's gravatar image

accept rate: 0%

Hey I solved the problem with same approach as given above but it's showing wrong answer. Please can anyone help


answered 21 Jul '17, 08:17

jha_gaurav98's gravatar image

accept rate: 0%


The test data, is too large for me to debug the program, so I am unable to find why is it giving 421211088 instead of correct result. Can you please help. My solution is


answered 21 Jan '13, 23:38

raman92's gravatar image

accept rate: 0%

edited 21 Jan '13, 23:38

I have updated the editorial. Please read and follow the SUGGESTION at the beginning of editorial.

(22 Jan '13, 02:41) anton_lunyov ♦6★
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 15 Jan '13, 15:00

question was seen: 9,944 times

last updated: 21 Jul '17, 08:17