CHEFHACK - Editorial

anton_lunyov · January 17, 2013, 11:33am

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

anton_lunyov · January 17, 2013, 11:54am

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

But are you sure that this solution has complexity O(N * N) per test?
What about test of the structure:
10
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(N³).

anton_lunyov · January 17, 2013, 12:02pm

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.

anton_lunyov · January 17, 2013, 2:50pm

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.

h_201001039 · January 17, 2013, 4:16pm

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

coolmind · January 17, 2013, 7:07pm

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.

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

Could you please look into it?

anton_lunyov · January 17, 2013, 7:22pm

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.

charchit · January 17, 2013, 7:33pm

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

anton_lunyov · January 17, 2013, 7:36pm

Yes. Even 1536M

coolmind · January 18, 2013, 1:28pm

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?

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

anton_lunyov · January 18, 2013, 1:37pm

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.

coolmind · January 18, 2013, 2:50pm

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.

anton_lunyov · January 18, 2013, 6:53pm

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.

mouad · January 19, 2013, 2:44am

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

nishantshah · January 21, 2013, 1:13pm

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

anton_lunyov · January 21, 2013, 3:04pm

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

chamanchindi · January 21, 2013, 4:05pm

New id is 1742822. Thanks.

chamanchindi · January 21, 2013, 4:27pm

Hi There, your solution did not work on the following test case.

1

6

1034 5036 5076 8099 6543 7853

0 2 4 6 8 10

1 5 7 9 13 15

1034 5036 5076 8099 6543 7853

The answer is 9076. It is giving 5087.

shasha1s2 · January 21, 2013, 6:18pm

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…

anton_lunyov · January 21, 2013, 11:06pm

Try this test:
http://pastebin.com/raw.php?i=j6UWCAZ5
The correct answer is 436746489.
While your answer is 458527862.