LEDIV - Editorial

Try the simplest possible test:
1
1
1
:wink:

3 Likes

well … lesson learned …paid for incoherence. .
@anton thank a lot , very much appreciated :slight_smile:

@anton_lunyov:Thanks,i got it :slight_smile:

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 :slight_smile:
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?

No, you are NOT.

tester’s solution returns 24371

your solution returns 12186

1 Like

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 :slight_smile: Fixed.

1 Like

Sry check this 1
http://www.codechef.com/viewsolution/1566136

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 thanks:)

@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

@anton_lunyov still getting TLE…:frowning:
http://www.codechef.com/viewsolution/1649643

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

@anton_lunyov okk…got it…thanx a lot…:))