@sarfarajey Read the bold tip in the beginning of the editorial.
1 Like
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.
1 Like
@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
http://discuss.codechef.com/answer_link/5181/
In short, you should use usual array instead of queue.
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.
Your output for this test
4
0 4 8 12
0 1 9 24
0 1 9 12
0 8 16 18
is 16 while should be 2.
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
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(N3).
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.
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 to mainā collect2: ld returned 1 exit statusā when I am submitting my code.
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.
@anton_lunyov : I donāt think its a cheat. Its the first thought that came in my mind after reading this question.
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?
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.
Yes. Even 1536M
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?
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.
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.
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.
@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).