## 10880 - Colin and Ryan

Moderator: Board moderators

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

### Re: Help me...

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.

scott1991
New poster
Posts: 28
Joined: Fri Dec 07, 2007 11:41 pm
Hi. I have TLE too...this is my code:

Code: Select all

``Ac now!!``
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.
Last edited by scott1991 on Sat Mar 08, 2008 2:08 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
There can be cases like...

Input:

Code: Select all

``````1
2000000000 2``````
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.

scott1991
New poster
Posts: 28
Joined: Fri Dec 07, 2007 11:41 pm
this is my new code but i'm getting wa...anyone know why? cheers.

Code: Select all

``AC now!!``
Last edited by scott1991 on Sat Mar 08, 2008 2:08 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the case. (I mentioned this already)

Input:

Code: Select all

``````1
36 0``````
Output:

Code: Select all

``Case #1: 1 2 3 4 6 9 12 18 36``
Hope it helps.

scott1991
New poster
Posts: 28
Joined: Fri Dec 07, 2007 11:41 pm
thanks jan.. AC now

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Again TLE...

How I could reduce time limit hear...!

Code: Select all

``REMOVED``
Last edited by Obaida on Wed Mar 19, 2008 11:20 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### WA...

But I got Wa.. again and again... I send you the code in private msg..
try_try_try_try_&&&_try@try.com
This may be the address of success.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

### Re: WA...

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.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### No..

Did you meant for this input....

Code: Select all

``````1
36 0
``````
I think my output is correct.

Code: Select all

``Case #1: 1 2 3 4 6 9 12 18 36``
try_try_try_try_&&&_try@try.com
This may be the address of success.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

Code: Select all

``````1
100 50
``````

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Ok..

OH... I made a silly mistake...!
I really become mad when I get WA...
Then easy problems become heard...
Though i got WA...
try_try_try_try_&&&_try@try.com
This may be the address of success.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Thanks

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..
try_try_try_try_&&&_try@try.com
This may be the address of success.

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re:

Jan,
Jan wrote:Hope these help.
Thanks for sharing these.
Check input and AC output for over 7,500 problems on uDebug!