11480  Jimmy's Balls
Moderator: Board moderators
11480  Jimmy's Balls
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.
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.
Re: 11480  Jimmy's Balls
I think you can run a brute force method to find the valu
and you can find the formular f[n] = f[n1] ... (just think yourself )
and you can find the formular f[n] = f[n1] ... (just think yourself )
electron
 emotional blind
 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
Re: 11480  Jimmy's Balls
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 kmaxkmin, for every k.
Hope this idea will help you.
thanks.
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 kmaxkmin, for every k.
Hope this idea will help you.
thanks.
Re: 11480  Jimmy's Balls
Are you saying there is a recurrence relation? Could you please explain that?f74956227 wrote:you can find the formular f[n] = f[n1] ... (just think yourself )
Re: 11480  Jimmy's Balls
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 kmaxkmin, for every k.
Hope this idea will help you.
thanks.
thx a lot , i got AC .
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.
Re: 11480  Jimmy's Balls
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
Are you dreaming right now?
http://www.dreamviews.com
Re: 11480  Jimmy's Balls
i think the answer for n is round((n3)^2/12)
if it's spoiler tell me to delete it?
if it's spoiler tell me to delete it?
 kbr_iut
 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, DHAKA, BANGLADESH
 Contact:
Re: 11480  Jimmy's Balls
hamedv wrote
wahaha wrote
here it is.
let p=n/6; //n is the number of balls
m=n%6
if(!m)num=((sum of 1 to p1)*6+1)
else num==((sum of 1 to p1)*6+1)+(m1)*p+(p1)//if m>0
and now num is the number of combination.
I got AC by this method.Its cool.
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.i think the answer for n is round((n3)^2/12)
if it's spoiler tell me to delete it?
wahaha wrote
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.i want to know the O(1) solution.
here it is.
let p=n/6; //n is the number of balls
m=n%6
if(!m)num=((sum of 1 to p1)*6+1)
else num==((sum of 1 to p1)*6+1)+(m1)*p+(p1)//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...............................
It is more tough to become a good person.
I am trying both...............................

 New poster
 Posts: 16
 Joined: Sun Mar 02, 2008 10:34 am
 Location: SUST , Sylhet, Bangladesh
Re: 11480  Jimmy's Balls
you can apply brute force process. just see the figure think about loop.
than try to understand the process
you will find good soution.
than try to understand the process
you will find good soution.
life is beautiful like coding

 New poster
 Posts: 16
 Joined: Sun Mar 02, 2008 10:34 am
 Location: SUST , Sylhet, Bangladesh
Re: 11480  Jimmy's Balls
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.
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
Re: 11480  Jimmy's Balls
Why why why????????
m wa!!!!
m wa!!!!
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.
This may be the address of success.
 kbr_iut
 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, DHAKA, BANGLADESH
 Contact:
Re: 11480  Jimmy's Balls
the output for n=1000010 is
which cant be covered within the range of long
try to use long long.
surely u will get AC.
Code: Select all
Case 1: 83334500004
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...............................
It is more tough to become a good person.
I am trying both...............................
Re: 11480  Jimmy's Balls
Well...that actually works...@kbr_iut if your output is different when n = 100, then you must be mistaken and not him.by kbr_iut » Thu Aug 14, 2008 10:15 am
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.hamedv wrote
i think the answer for n is round((n3)^2/12)
if it's spoiler tell me to delete it?
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