Page 3 of 4
Re: Help me...
Posted: Fri Mar 07, 2008 8:08 pm
by emotional blind
Obaida wrote:What I need to to hear.... Is my algorithm wrong or Something wrong with my code please help me..... I am getting TLE...
your algorithm is wrong and inefficient.
try to find out all divisors of C-R, which are greater than R.
I used O(sqrt(C-R)) algorithm to avoid TLE.
to avoid wrong answer, consider the case where C=R.
and problem description explicitly says
Do not print trailing spaces.
you should consider this also.
Posted: Fri Mar 07, 2008 11:19 pm
by scott1991
Hi. I have TLE too...this is my code:
i get all the test cases right along with all those i have tested from these pages...can anyone help me speed my program up? thanks.
Posted: Sat Mar 08, 2008 11:39 am
by Jan
There can be cases like...
Input:
Output:
Code: Select all
Case #1: 3 6 9 18 27 37 54 74 81 111 162 222 333 666 999 1998 2997 5994 333667 667334 1001001 2002002 3003003 6006006 9009009 12345679 18018018 24691358 27027027 37037037 54054054 74074074 111111111 222222222 333333333 666666666 999999999 1999999998
Warning Spoiler:
Suppose the given numbers are a,b. We have to find all divisors of a-b which are greater than b.
Method 1:
1. Let x=a-b
2. At first, prime factorize x.
3. Then you can find all divisors. Print the divisors that are greater than b.
Method 2:
1. Let x=a-b
2. for i = 1 to sqrt(x)
a. if(x%i==0)
b. then i is a divisor
c. and x/i is a divisor, too
d. So, save both of them
3. Sort the divisors and print the divisors that are greater than b. Be careful about duplicates.
Hope these help.
Posted: Sat Mar 08, 2008 12:55 pm
by scott1991
this is my new code but i'm getting wa...anyone know why? cheers.
Posted: Sat Mar 08, 2008 1:30 pm
by Jan
Try the case. (I mentioned this already)
Input:
Output:
Hope it helps.
Posted: Sat Mar 08, 2008 2:08 pm
by scott1991
thanks jan.. AC now
Again TLE...
Posted: Tue Mar 18, 2008 11:28 am
by Obaida
How I could reduce time limit hear...!
Posted: Wed Mar 19, 2008 10:06 am
by emotional blind
Obaida,
To generate all divisors of n, there is a better way than O(n) solution.
For every divisors m less than sqrt(n) there n/m will also be a divisor of n, which will be greater than n.
for example if you findout all divisors of 24. you need to try only upto floor( sqrt(24) ) = 4.
1. 1 is a divisors so 24/1 = 24 will also a divisor
2. 2 is a divisor so 24/2=12 will also a divisor
3. 3 is a divisor so 24/3=8 will also a divisor
4. 4 is a divisor so 24/4 = 6 will also a divisor
so divisors of 24 are,
1, 2, 3, 4, 6, 8, 12, 24.
I think this example will help you. Best of luck.
WA...
Posted: Wed Mar 19, 2008 12:56 pm
by Obaida
But I got Wa.. again and again... I send you the code in private msg..
Re: WA...
Posted: Wed Mar 19, 2008 2:08 pm
by emotional blind
Obaida wrote:But I got Wa.. again and again... I send you the code in private msg..
Most probably you did a common mistake.
you checked m>b but you didn't check whether n/m >b or not.
No..
Posted: Thu Mar 20, 2008 5:46 am
by Obaida
Did you meant for this input....
I think my output is correct.
Posted: Thu Mar 20, 2008 10:53 am
by emotional blind
Ok..
Posted: Thu Mar 20, 2008 11:49 am
by Obaida
OH... I made a silly mistake...!
I really become mad when I get WA...
Then easy problems become heard...
Though i got WA...
Thanks
Posted: Thu Mar 20, 2008 12:40 pm
by Obaida
After a grate war between me and WA... finally I got Acc..
Thank you emotional blind to help me to find out my mistake....
You are a good helper..
Re:
Posted: Tue Jul 01, 2014 1:18 pm
by uDebug
Jan,
Jan wrote:Hope these help.
Thanks for sharing these.