11960 - Divisor Game

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

Moderator: Board moderators

regan
New poster
Posts: 4
Joined: Wed Apr 28, 2010 6:24 pm

11960 - Divisor Game

Post by regan » Wed Apr 20, 2011 11:47 am

Can any one help me by providing some more cases ....

lgarcia
New poster
Posts: 16
Joined: Mon Sep 14, 2009 7:49 pm
Location: Venezuela

Re: 11960 Divisor Game Getting WA!!

Post by lgarcia » Thu Apr 21, 2011 9:05 pm

Some cases, I hope it helps.

Input:

Code: Select all

20
1
10
100
1000
10000
100000
1000000
2
3
4
5
6
7
8
50
534534
32423
12354
8980
2332
Output:

Code: Select all

1
10
96
840
9240
98280
997920
2
3
4
4
6
6
8
48
498960
30240
10080
7560
2160

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

Re: 11960 Divisor Game Getting WA!!

Post by iriz7482 » Thu Apr 28, 2011 6:18 pm

This problem is pretty similar to problem 294 - Divisors. I tried to find NOD (number of divisors) of all number in a certain range or precaculate NOD of all number from 1 to 1000000 but got TLE. Is there any better method to solve this problem? Please help :oops:

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

Re: 11960 Divisor Game Getting WA!!

Post by robot » Thu Apr 28, 2011 7:37 pm

Actually the problem is a simple precalculating problem...
1. First of all u generate the divisor number using seieve div(n)= n1^(p1+1) * n2^(p2+1)......)
2. next u precalculate maxdiv 1 to range
suppose div[] is a calculating of number of divisor
mdiv[1]=1;
mind[1]=1;
if div[2] >=mdiv[1] {
mdiv[2]=div[2];
mind[2]=2;}
else {
mdiv[2]=mdiv[2-1]
mind[2]=mind[2-1];
}

finally just print mind[n];
ASU(SUST) :D

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 11960 Divisor Game Getting WA!!

Post by Imti » Fri Apr 29, 2011 5:16 pm

Hello,Im getting TLE in this problem.I precalculated result for every number from 1 to 1e6 and outputted in O(1) time.My working procedure is like:
1)Generate all prime number upto sqrt(1e6) using sieve
2)factorize each number from 1 to 1e6.Then I used the formula for a number n=p1^n*p2^m ,NOD(number_of_divisor)=(n+1)*(m+1)
3)on getting the NOD,compare it with previous one's NOD.If (current NOD>=previous NOD) then TBO(to_be_outputted)[current_num]=current_num else
TBO[current_num]=TBO[current_num-1]
Thats my algorithm.Im getting TLE on this.Please help anyone how to optimize my code?

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

Re: 11960 Divisor Game Getting WA!!

Post by robot » Fri Apr 29, 2011 7:46 pm

Imti can u send ur code?
ASU(SUST) :D

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

Re: 11960 Divisor Game Getting WA!!

Post by iriz7482 » Sat Apr 30, 2011 8:09 pm

hey Imti your algo is the same as mine. I remember it took nearly 2 seconds to precaculate all NOD of all number from 1 to 1e6, so you may not have enough time to output your result :D
Last edited by iriz7482 on Sun May 01, 2011 1:29 pm, edited 1 time in total.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 11960 Divisor Game Getting WA!!

Post by Imti » Sun May 01, 2011 10:28 am

This is my code.I just couldn't recall any better idea right now to solve the problem..

Code: Select all

//Code Removed After getting Accepted
'
Last edited by Imti on Sun May 01, 2011 4:56 pm, edited 1 time in total.

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

Re: 11960 Divisor Game Getting WA!!

Post by robot » Sun May 01, 2011 2:33 pm

Imti ur code is right, but ur fac() funtion has too much complexity. so change this method. and try prime factor efficiently.
use sqrt(N) for prime factor. I hope u will get Accepted...
ASU(SUST) :)

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

Re: 11960 Divisor Game Getting WA!!

Post by iriz7482 » Sun May 01, 2011 3:08 pm

after viewing Imti's code I fixed my output from O(n/2) to O(1) and got AC in 1.7 secs :lol: . Now I'm thinking another algo to decrease my running time :oops: .
Last edited by iriz7482 on Sun May 01, 2011 4:32 pm, edited 1 time in total.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 11960 Divisor Game Getting WA!!

Post by Imti » Sun May 01, 2011 4:15 pm

Thanks robot and iriz... for ur reply..I actually tried several method instead of my "fac()" function..but still getting TLE..would u(robot or iriz)please tell me more clearly about how can I improve my fac() function... :cry:
Last edited by Imti on Sun May 01, 2011 4:51 pm, edited 3 times in total.

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

Re: 11960 Divisor Game Getting WA!!

Post by iriz7482 » Sun May 01, 2011 4:28 pm

here is my NOD funtion

Code: Select all

long NOD(long n, long a[])
{
     long r=1, i=0, j;
     while(n>1)
     {
          if(isprime(n)) //if n is a prime number
          {
               r*=2;
               break;
          }
          while(n%a[i]!=0)
          i++;
          j=0;
          while(n%a[i]==0)
          {
               n/=a[i];
               j++;
          }
          r*=(j+1);
     }
     return r;
}
I store prime numbers from 2 to sqrt(n) in the array a[]. a[0]=2, a[1]=3, a[3]=5,.... :D
hope you get AC :P

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 11960 Divisor Game Getting WA!!

Post by Imti » Sun May 01, 2011 4:52 pm

Now,I got Accepted it with runtime of 0.364s.. :D ..I actually didn't change my fac() function..rather I used some already computed value there in fac() function which has reduced run time dramatically... :) ...Thanks robot and iriz72...... :D

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11960 Divisor Game Getting WA!!

Post by plamplam » Thu Aug 04, 2011 5:11 pm

Nice problem! It took me a while though to figure out how to output the result quickly. I got AC in 0.676 seconds although I later decreased my runtime to 0.020 :D
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 11960 Divisor Game Getting WA!!

Post by Imti » Sat Aug 06, 2011 9:19 pm

@plamplam
would u plz share the idea how you decreased ur runtime?I used O(1) outputting and kinda memoization.If u don't have any problem would u plz message me ur mail address...coz,I feel and think discussing and sharing is the best way to learn ... thanks in advance...:)

Post Reply

Return to “Volume 119 (11900-11999)”