LEDIV - Editorial

editorial
, , ,
21

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
22

Yes. Thanks :slight_smile: Fixed.

1 Like
23

http://www.codechef.com/viewsolution/1565687
i should get TLE…but getting WA .just want to know which test case solution fails…

24

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

25

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
26

@anton_lunyov thanks:)

27

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

28

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.

29

i used the same method as given in this editorial but still getting TLE plzz can anyone tell me why i m getting TLE
http://www.codechef.com/viewsolution/1641999

30

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
31

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

32

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
33

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

34

@admin Is there some way we can get access to input files used to check our solutions for practice problems??

35

When T and N are constrained to 100000, how come the tester’s solution pass with data type “int” used?

36

I don’t get your question. Probably you’ve misunderstood the constraints. We can’t have T=100000 with N=100000 in each test since the sum of N over test file <= 100000.

37

@arag0rn No. It is the general policy of codechef to not reveal the test data even after the contest.

38

I meant that T can be larger (<=100000) than the upper limit (INT_MAX) of “int” (integer data type) used in the tester’s solution for variable T.
Or, am I wrong in the basics?

39

Yes you are wrong in the basics.
INT_MAX is 2^31-1 which is more than 2,000,000,000.

40

Yes, I am getting a magic number 2147483647 when I implemented INT_MAX in C and C++ both. But my machine is older, 32 bits. I thought maximum value “int” can hold is 2^15-1