10880 - Colin and Ryan

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

Moderator: Board moderators

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

Re: Help me...

Post by emotional blind » Fri Mar 07, 2008 8:08 pm

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

Post by scott1991 » Fri Mar 07, 2008 11:19 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Mar 08, 2008 11:39 am

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

Post by scott1991 » Sat Mar 08, 2008 12:55 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Mar 08, 2008 1:30 pm

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

Post by scott1991 » Sat Mar 08, 2008 2:08 pm

thanks jan.. AC now

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Again TLE...

Post by Obaida » Tue Mar 18, 2008 11:28 am

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.

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

Post by emotional blind » Wed Mar 19, 2008 10:06 am

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.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

WA...

Post by Obaida » Wed Mar 19, 2008 12:56 pm

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.

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

Re: WA...

Post by emotional blind » Wed Mar 19, 2008 2:08 pm

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
Location: (BUBT) Dhaka,Bagladesh.

No..

Post by Obaida » Thu Mar 20, 2008 5:46 am

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.

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

Post by emotional blind » Thu Mar 20, 2008 10:53 am

What about this input

Code: Select all

1
100 50

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Ok..

Post by Obaida » Thu Mar 20, 2008 11:49 am

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
Location: (BUBT) Dhaka,Bagladesh.

Thanks

Post by Obaida » Thu Mar 20, 2008 12:40 pm

After a grate war between me and WA... finally I got Acc.. :wink:
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.

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

Re:

Post by uDebug » Tue Jul 01, 2014 1:18 pm

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

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 108 (10800-10899)”