Try the simplest possible test:
1
1
1
3 Likes
well ā¦ lesson learned ā¦paid for incoherence. .
@anton thank a lot , very much appreciated 
Try this test
1
1
12346
Replace array p[1000] by p[10000]. There are 9592 primes up to 100000.
However this leads to TLE 
http://www.codechef.com/viewsolution/1565776
What is even more fun that your previous solution passes first two tests and get WA on the third test. But the new ācorrectā version get TLE on the second test which have the following structure: T=100000 N=1 A[1]>90000 is prime. So as you see you perform about 9000 operations in average for each number. This is about 900 millions operations in all which of course do not fit in TL.
I can only suggest you to follow the editorial.
1 Like
Due to the lack of space I continue here.
You will be probably interested how you first solution can pass more tests than the corrected version. This is probably because array x[] follows p[] in the memory. So when you iterate over array p[] with condition p[i]<=min after the end of this array you jump to x[] which contain the element x[0] which is prime and it is the answer. So you break here.
1 Like
i am getting same answer as of tester solution .
what is the error?
okā¦got itā¦thanks
Thanks for the editorial, but Iāve found a typo in the part where we find the smallest prime factor of the gcd :
for i = 2 to floor(sqrt(N))
if G is divisible by i
return i
return N // Since N is prime!
Shouldnāt the āNā be āGā ?
1 Like
Yes. Thanks Fixed.
1 Like
The line 45 of your solution
if(min%p[i]==0)
is the reason of why.
By changing it to
while(min%p[i]==0)
I get AC:
http://www.codechef.com/viewsolution/1566165
The simplest test that cause this solution to fail is the following:
1
2
20 25
For old version the variable min will be 10 before the final check and you incorrectly output -1 because of this.
1 Like
@anton_lunyov
As you said: āT=100000 N=1 A[1]>90000 is prime. So as you see you perform about 9000 operations in average for each number. This is about 900 millions operations in all which of course do not fit in TL.ā
Even the editorial solution would require us to do same amount of 9000 operations in average for each number. Please explain.
In editorial solution we iterate only up to sqrt(A[1]) for this case. So it is about 25-30 times faster than naive approach.
You should write the part with calculating smallestprime before reading test data. The test where you get TLE has the structure
T=100000, N=1,2,3,4,ā¦,100000 (some permutation of this)
1 Like
You didnāt get what I mean. You should move part with calculating smallestprime even before you read the number of tests in the file.
Here is my edit of your solution that get AC:
http://www.codechef.com/viewsolution/1649844
The thing is that for the test Iāve mentioned you run loop for calculating smallestprime 100000 times which is definitely very slow.
1 Like