11480 - Jimmy's Balls

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

Moderator: Board moderators

Post Reply
wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

11480 - Jimmy's Balls

Post by wahaha » Wed Aug 06, 2008 6:49 am

can somebody tell me how to solve this problem?

i think it is a Combinatorics problem, what we want to solve is there are how many a,b,c such that a+b+c=n and a<b<c.

but it is out of my ability.

:oops:

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

Re: 11480 - Jimmy's Balls

Post by f74956227 » Wed Aug 06, 2008 8:02 am

I think you can run a brute force method to find the valu :D
and you can find the formular f[n] = f[n-1] ... (just think yourself :P )
electron

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

Re: 11480 - Jimmy's Balls

Post by emotional blind » Wed Aug 06, 2008 8:39 am

wahaha,
There is O(1) solution. If it is hard for you, then you can try O(n) solution.

Just iterate over number of red balls, for k red balls, try to find out kmax, and kmin,
here kmax = maximum number of blue ball you can have when number of red ball is k
and kmin = minimum number of blue ball you can have when number of red ball is k

then just add kmax-kmin, for every k.

Hope this idea will help you.
thanks.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11480 - Jimmy's Balls

Post by sohel » Wed Aug 06, 2008 12:39 pm

f74956227 wrote:you can find the formular f[n] = f[n-1] ... (just think yourself :P )
Are you saying there is a recurrence relation? Could you please explain that?

wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

Re: 11480 - Jimmy's Balls

Post by wahaha » Wed Aug 06, 2008 2:45 pm

emotional blind wrote:wahaha,
There is O(1) solution. If it is hard for you, then you can try O(n) solution.

Just iterate over number of red balls, for k red balls, try to find out kmax, and kmin,
here kmax = maximum number of blue ball you can have when number of red ball is k
and kmin = minimum number of blue ball you can have when number of red ball is k

then just add kmax-kmin, for every k.

Hope this idea will help you.
thanks.

thx a lot , i got AC . :D

what i think before is doubt that O(n) will get tle, and i didn't write it.
it seems that there are too little test cases.

i want to know the O(1) solution. :o

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11480 - Jimmy's Balls

Post by andmej » Wed Aug 06, 2008 3:37 pm

During the contest I used an O(n lg n) solution using binary search and it ran in less than a second :)
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Re: 11480 - Jimmy's Balls

Post by hamedv » Sat Aug 09, 2008 5:20 am

i think the answer for n is round((n-3)^2/12)
if it's spoiler tell me to delete it?

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11480 - Jimmy's Balls

Post by kbr_iut » Thu Aug 14, 2008 6:15 am

hamedv wrote
i think the answer for n is round((n-3)^2/12)
if it's spoiler tell me to delete it?
i dont think ur method could work.I just wrote and saw the output is simply different when n=100,,I didnt check for other values.
wahaha wrote
i want to know the O(1) solution.
I looked deeply and finally got the O(1) solution. its easy.if u look over the sample input and output u can urself find it.
here it is.
let p=n/6; //n is the number of balls
m=n%6
if(!m)num=((sum of 1 to p-1)*6+1)
else num==((sum of 1 to p-1)*6+1)+(m-1)*p+(p-1)//if m>0
and now num is the number of combination.
I got AC by this method.Its cool.
Last edited by kbr_iut on Thu Aug 14, 2008 7:27 pm, edited 3 times in total.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

rajib_sust
New poster
Posts: 16
Joined: Sun Mar 02, 2008 10:34 am
Location: SUST , Sylhet, Bangladesh

Re: 11480 - Jimmy's Balls

Post by rajib_sust » Thu Aug 14, 2008 7:09 pm

you can apply brute force process. just see the figure think about loop.
than try to understand the process

you will find good soution.

:roll:
life is beautiful like coding

rajib_sust
New poster
Posts: 16
Joined: Sun Mar 02, 2008 10:34 am
Location: SUST , Sylhet, Bangladesh

Re: 11480 - Jimmy's Balls

Post by rajib_sust » Fri Aug 15, 2008 10:45 pm

wahaha wrote:can somebody tell me how to solve this problem?

i think it is a Combinatorics problem, what we want to solve is there are how many a,b,c such that a+b+c=n and a<b<c.

but it is out of my ability.

:oops:

u can solve it using looping. if u using 2 loop it will take TLE
so i us one loop and reduce other in equational form
it more efficient and run time near 0.010

Rajib , sust
life is beautiful like coding

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

Re: 11480 - Jimmy's Balls

Post by Obaida » Sat Dec 20, 2008 3:44 pm

Why why why????????
m wa!!!! :x

Code: Select all

Thanks it's really a cool problem!
Last edited by Obaida on Sun Dec 21, 2008 7:14 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11480 - Jimmy's Balls

Post by kbr_iut » Sat Dec 20, 2008 6:29 pm

the output for n=1000010 is

Code: Select all

Case 1: 83334500004
which cant be covered within the range of long
try to use long long.
surely u will get AC.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

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

Re: 11480 - Jimmy's Balls

Post by plamplam » Thu Oct 27, 2011 11:52 pm

by kbr_iut » Thu Aug 14, 2008 10:15 am
hamedv wrote
i think the answer for n is round((n-3)^2/12)
if it's spoiler tell me to delete it?
i dont think ur method could work.I just wrote and saw the output is simply different when n=100,,I didnt check for other values.
Well...that actually works...@kbr_iut if your output is different when n = 100, then you must be mistaken and not him.
But I agree this was really a super cool fun problem.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Post Reply

Return to “Volume 114 (11400-11499)”