CHEFHACK - Editorial

SUGGESTION:

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.

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

EASY

PREREQUISITES:

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

PROBLEM:

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.

QUICK EXPLANATION:

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

EXPLANATION:

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
    else
        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
            continue
        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

ALTERNATIVE SOLUTION:

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 AND TESTER’S SOLUTIONS:

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

RELATED PROBLEMS:

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

11 Likes

Can you that what is my problem ID is :1681905

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:
1
1
3
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).

2 Likes

fantastic editorial. loved it!

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.

http://www.codechef.com/viewsolution/1718060

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
http://www.codechef.com/viewsolution/1720890

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

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

4 Likes

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

I’m in the same page :(!

I look here
http://campus.codechef.com/files/stderr/1681905/
Only admins, setter and tester have access to this.
Your answer for 8th test which is very small test is
DATASET NUMBER: 8
-0
-268156158598…
-0
-427197407184…
-125542034707…
-0
-0
-0
where … is some other digits (like hundreds of digits more)
Try to run your code on ideone.com using GNU C++ compiler against this test case.

1 Like

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

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.

same here… :frowning:

What is problem in my solution…
I am getting WA
http://www.codechef.com/viewsolution/1723138

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

3 Likes

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

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.

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…

http://www.codechef.com/viewsolution/1715077

Hi,

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.

HTH,

1 Like

Its Nice…