Dec 2014
1 / 14
Dec 2014
Dec 2014
jbourne
Dec '14

I have been working on both the problems lately(both being the same problem but with different constraints).
I need some directions/hints about proceeding further.

I have submitted a solution to IITKWPCQ in python. It is giving WA.

Set of Test cases tried -
1. I tried it on all integers from 1-30000
2. First 10000 primes(10000th prime -> 104729)
3. each of the numbers in point 2 raised to the power of 2,3,4 (power 4 gets sufficiently larger than the test limit)
4. all pseudo primes(PSPs) upto 2^64. Yes ! I downloaded the list of pseudo primes(800mb compressed data,2.5 GB on uncompressing) from - cecm.sfu.ca/Pseudoprimes/1 . Ran it for the whole day !! stuck_out_tongue . There are 72875460 base 2 PSPs.

Result of Test 4 - all of them gave "1" as the answer except only 2 numbers(that were perfect squares) - 1194648 and 12327121. Huhh !!!

All the above test cases give the correct answer.
After doing all that when I run my code, it gives WA. Am I missing any important test case?

I can share the solution/approach too. Any help is appreciated.

jbourne
Dec '14

Sorry, I meant 1093^2 = 1194649. The answer is 1194648.
Same way for 3511^2 -> 12327121 -1 = 12327120.

leppyr64
Dec '14

You can PM me your method and I could hopefully point you in the right direction. I can't solve this problem because I don't know an efficient method for factorizing the input since Sieve of Erastothenes doesn't scale that well.

jbourne
Dec '14

Sure, thanks a lot. I just found out that my program has a bug for numbers greater than 20 digits. Giving "1" ans for 20 and 30 digit primes.
I forgot to mention that I am new to python smile .
I think I have introduced some bug. I would mail u personally the solution with a detailed explanation/approach. The approach is correct for sure. But I think there's some Python-related problem I am facing. I have assumed python can handle numbers >= 20 digits as well.

numerix
Dec '14

Your assumption is correct.

jbourne
Dec '14

Actually, I was earlier getting correct answer for digits greater than 20, but not I am not getting it(although i din't alter the logic). I have PMed you the code and approach that I shared with @Leppy. Please if you could have a look. Thanks !

luckymastermin
Dec '14

I have seen you solving this problem, If you try this problem with Python 3 or python 3.4 you can get AC in Classical version. This is Just for your information.

jbourne
Dec '14

Hey, I din't get your point.
I am trying Python 2.7 .Got AC only in the "Tutorial" version(time taken-17 sec). Are you trying to say that if I switch to Py3 or Py3.4 instead of 2.7 , I would get AC ? or something else?

luckymastermin
Dec '14

You got AC in Tutorial version so in order to get Ac in main version http://www.spoj.com/problems/IITKWPCM/3 you can choose python 3 or 3.4 they are faster than 2.7. Hope it is clear now.

jbourne
Dec '14

Hey, thanks for the info, but there is a catch smile !
I am new to Python and am getting some bug in PY3.3 and PY3.4. Thus, I get wrong answer with it.
Now, after so many days of struggle , I was planning to recode it in C++ frowning . I had put that task on hold as of now. I think the issue with my Python code is something minor. I can PM you if you wanna have a look.

Otherwise, I would go with the C++ idea. I have already wasted so many man-days debugging the silly versioning-related bug.

Thanks

luckymastermin
Dec '14

Might be you have some issue with division operator in python "/" and "//" work differently for python 2 and 3 so you can change "/" with "//" in python 3 or 3.4. If issue still persist you can send me your code.