## 10590 - Boxes of Chocolates Again

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

Moderator: Board moderators

Red Scorpion
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]

Andrey Mokhov
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.

Whinii F.
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
JongMan @ Yonsei

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Hi, all.

My equation is:

Code: Select all

``cutted``
should I reduce the paramter into one ?

Happy new year.

Thanks.
Last edited by Red Scorpion on Thu Jan 01, 2004 10:22 am, edited 1 time in total.

Whinii F.
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".
Last edited by Whinii F. on Thu Jan 01, 2004 10:33 am, edited 1 time in total.
JongMan @ Yonsei

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
To: Red Scorpion

Mine is f(n,k)=f(n,k-1)+f(n-k,k)

Idea is that:

When you calculate f(n,k), what you have to know is only column k

and column k-1.

So don't waste memory to store the value of other columns.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
ooops, sorry I misstype the equation. the equation should be the same as ghost77 dimen.

PS: I think it is a spoiler so please remove it.

Best Regards,
RS

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
Ghost77 dimen wrote: Mine is f(n,k)=f(n,k-1)+f(n-k,k)
Mine is the same as you.
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();
}
``````
[/code]

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
To windows2k :

I don't know the good method, either.

Mine solved the problem around 5 seconds.

It can pass the online judge, but still can't pass the contest.

If you only want to pass the online judge, you can do as my previous

article, and optimize it.

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
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
__nOi.m....

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
That's what I meant!

But you've beaten me in the ranklist...

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Andrey Mokhov,
that's really funny.
any way i thank to you for your hints ...
__nOi.m....

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
I also discovered that formula in INTERNET, but i do not understand as to why it should work. Is the proof quite short? could someone provide me with the proof?

Thanks

Andrey Mokhov
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.

Alexander Kozlov
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.