10299 - Relatives

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

10299 TLE... (now WA) -> TLE again

Post by Wei-Ming Chen »

Got AC now, thanks everyone's help. :D
Last edited by Wei-Ming Chen on Sat Feb 04, 2006 8:53 am, edited 3 times in total.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Precalculate the prime numbers.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen »

I fixed my code, but it changed to WA now.....
Can you help again?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

You have to take care of more number of primes. For example, output of

Code: Select all

997485889
998623201
999002449
are

Code: Select all

997454306
998591600
998970842
Use code tagging for posting codes.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen »

I changed my code.
But why TLE again?
Should I make a int x[1000000000] ?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

Wei-Ming Chen wrote:I changed my code.
But why TLE again?
Should I make a int x[1000000000] ?
nope..
sqrt(1000000000) will be enough..

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen »

Maybe I should think why I used sqrt(1000000000) and got TLE.......

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by Amir Aavani »

one of your code problem is that num must be longint,
because, the problem states that n<1000000000.

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

10299 TLE

Post by Ankur Jaiswal »

I have used sieve to calculate the prime numbers. Then I used Euler's fonction to calculate the number of relatives.
Then too I am getting TLE.
Smbd help me.
Thanx in advance.
Code :
Removed after accpeted :P .
Last edited by Ankur Jaiswal on Tue May 02, 2006 11:30 am, edited 1 time in total.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

Dear - Ankur Jaiswal!

Euler Phi-function works fine here - I did got AC, but long after series of TLE too...
Last edited by serur on Sat Apr 14, 2012 3:26 pm, edited 1 time in total.

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Solution to 10299

Post by Ankur Jaiswal »

I too have used Euler Phi function to solve this question.
But I first calculated prime numbers using Sieve so as to get the prime numbers in lesser time. But then too i am getting TLE. Plz give more hints to solve this problem.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

Clever brute-force check (however weird it sounds :D ) is enough - get rid of factor 2 and run odds. Don't forget about square roots. And also that this algo not necesarily terminates with 1.
Last edited by serur on Sat Apr 14, 2012 3:32 pm, edited 1 time in total.

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Terminating condition on (num==1)

Post by Ankur Jaiswal »

When num!=1 (but i>3401) in the function relatives() and the for loop is done with, then i am keeping a check onto num (whether it is 1 or not).
If it is not 1 then it will obviously be a prime number... therefore i have done ans=(ans/num) *(num-1);
so i dont think that this condition is wrong.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

You can improve your euler phi calculation. Instead of trying with all the prime numbers, try with the prime numbers that are <= sqrt(num).

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Solution

Post by Ankur Jaiswal »

thanks a lot.
But now i am getting WA.

Post Reply

Return to “Volume 102 (10200-10299)”