10590 - Boxes of Chocolates Again
Moderator: Board moderators
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
10590 - Boxes of Chocolates Again
I know the recurence equation to solve this problem, but since n is very big (n<=5000), I can't precalculate the result.
Is this problem need an explicit equation?
Regards,
RS[/b]
Is this problem need an explicit equation?
Regards,
RS[/b]
-
- Experienced poster
- Posts: 128
- Joined: Fri Nov 15, 2002 7:45 am
- Location: Kyrgyzstan
Hello, Scorpion!
Just small hint: there is still recurrence to find Pn (not a single formula) but you need only O(n) memory to calculate and hold all the values of Pn. You can find such brilliant recurrence in internet.
Look for something like Pentagonal formula of Euler - not sure I wrote it correctly - I just tried to translate it from Russian.
Happy new year!
Bye.
Andrey.
Just small hint: there is still recurrence to find Pn (not a single formula) but you need only O(n) memory to calculate and hold all the values of Pn. You can find such brilliant recurrence in internet.
Look for something like Pentagonal formula of Euler - not sure I wrote it correctly - I just tried to translate it from Russian.
![:wink:](./images/smilies/icon_wink.gif)
Happy new year!
![:D](./images/smilies/icon_biggrin.gif)
Bye.
Andrey.
-
- Experienced poster
- Posts: 151
- Joined: Wed Aug 21, 2002 12:07 am
- Location: Seoul, Korea
- Contact:
I'm wondering, are these kind of problems required to solve for contestants in the contest environment? This is only applying well-known formula. (Of course knowledges in math are essential with ICPC too, but..)
RS:
You can eliminate a dimension in your recurrence, and do DP with O(N) space complexity. I got AC with this, but my time is about 9 sec.
(Considering the time limit was 4 in the real contest)
Happy new year, everybody![:P](./images/smilies/icon_razz.gif)
RS:
You can eliminate a dimension in your recurrence, and do DP with O(N) space complexity. I got AC with this, but my time is about 9 sec.
![:-?](./images/smilies/icon_confused.gif)
Happy new year, everybody
![:P](./images/smilies/icon_razz.gif)
JongMan @ Yonsei
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
Hi, all.
My equation is:
should I reduce the paramter into one ?
Happy new year.
Thanks.
My equation is:
Code: Select all
cutted
Happy new year.
Thanks.
Last edited by Red Scorpion on Thu Jan 01, 2004 10:22 am, edited 1 time in total.
-
- Experienced poster
- Posts: 151
- Joined: Wed Aug 21, 2002 12:07 am
- Location: Seoul, Korea
- Contact:
Hmm, different from mine. Mine is
C[a, b] = number of ways to partition b with elements upto a.
[spoiler removed.. is it really a spoiler?]
I think it's quite trivial and it will not be hard to eliminate dimension "a".
C[a, b] = number of ways to partition b with elements upto a.
[spoiler removed.. is it really a spoiler?]
I think it's quite trivial and it will not be hard to eliminate dimension "a".
Last edited by Whinii F. on Thu Jan 01, 2004 10:33 am, edited 1 time in total.
JongMan @ Yonsei
-
- Learning poster
- Posts: 67
- Joined: Sun Sep 22, 2002 5:40 am
- Location: Taiwan
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
Mine is the same as you.Ghost77 dimen wrote: Mine is f(n,k)=f(n,k-1)+f(n-k,k)
But still get TLE.
any good method is speed up?
I first calc all possible solution. like this
Code: Select all
void init() {}
int main()
{
init();
while(read n) print(n);
}
-
- Learning poster
- Posts: 67
- Joined: Sun Sep 22, 2002 5:40 am
- Location: Taiwan
hi all,
after reading topics of Andrey Mokhov posted in this page earlier ,i manage to solve this problem with faster time ( 0.252 sec) . i searched in the internet for the pentagonal formula of Eular. and i got a series there, which is useful for soving this problem
the sereis is like that:
P(n) = P(n-1)+ P (n-2) - P (n-5) - P(n-7) + ...
here we have to make another series like : 1, 2, 5, 7.... (Euler formula) wich can be genarated pairwisely by adding first ( then second then...) Natural number and first (then second then ...) Odd number with last value simultaneosly . and the inistial position the value is 0.
This may work to minimize the time.
thanks
after reading topics of Andrey Mokhov posted in this page earlier ,i manage to solve this problem with faster time ( 0.252 sec) . i searched in the internet for the pentagonal formula of Eular. and i got a series there, which is useful for soving this problem
the sereis is like that:
P(n) = P(n-1)+ P (n-2) - P (n-5) - P(n-7) + ...
here we have to make another series like : 1, 2, 5, 7.... (Euler formula) wich can be genarated pairwisely by adding first ( then second then...) Natural number and first (then second then ...) Odd number with last value simultaneosly . and the inistial position the value is 0.
This may work to minimize the time.
thanks
__nOi.m....
-
- Experienced poster
- Posts: 128
- Joined: Fri Nov 15, 2002 7:45 am
- Location: Kyrgyzstan
-
- Experienced poster
- Posts: 128
- Joined: Fri Nov 15, 2002 7:45 am
- Location: Kyrgyzstan
The proof is not quite easy. But you can find it in the 'Net also. Go to http://mathworld.wolfram.com - it is the best site of math to my mind. There are lots of interesting mathematical facts. I don't remember if there are proofs but there must be links to pages where you can find them.
Good luck!
Andrey.
Good luck!
Andrey.
-
- New poster
- Posts: 23
- Joined: Sun Jun 15, 2003 4:45 pm
- Location: Ukraine
10590 Wrong answer
Dear friends!
For this input
0
1
2
3
4
5
10
45
100
567
1000
1348
2000
my program produces this output
1
1
2
3
5
7
42
89134
190569292
83983162210640880002321
24061467864032622473692149727991
8421598515143296812402544776496284973
4720819175619413888601432406799959512200344166
Is it correct? I got WA.
Thanks in advance.
For this input
0
1
2
3
4
5
10
45
100
567
1000
1348
2000
my program produces this output
1
1
2
3
5
7
42
89134
190569292
83983162210640880002321
24061467864032622473692149727991
8421598515143296812402544776496284973
4720819175619413888601432406799959512200344166
Is it correct? I got WA.
Thanks in advance.