Page 1 of 2

10590 - Boxes of Chocolates Again

Posted: Wed Dec 31, 2003 7:15 am
by Red Scorpion
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]

Posted: Wed Dec 31, 2003 9:18 am
by Andrey Mokhov
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. :wink:

Happy new year! :D

Bye.
Andrey.

Posted: Wed Dec 31, 2003 2:10 pm
by Whinii F.
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

Posted: Wed Dec 31, 2003 2:56 pm
by Red Scorpion
Hi, all.

My equation is:

Code: Select all

cutted
should I reduce the paramter into one ?

Happy new year.

Thanks.

Posted: Thu Jan 01, 2004 7:37 am
by Whinii F.
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".

Posted: Thu Jan 01, 2004 7:56 am
by Ghost77 dimen
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.

Posted: Thu Jan 01, 2004 10:19 am
by Red Scorpion
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

Posted: Thu Jan 01, 2004 11:59 am
by windows2k
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();
      while(read n) print(n);
}
[/code]

Posted: Thu Jan 01, 2004 2:59 pm
by Ghost77 dimen
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.

Posted: Fri Jan 02, 2004 2:06 pm
by Noim
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

Posted: Sat Jan 03, 2004 10:46 am
by Andrey Mokhov
That's what I meant! :D

But you've beaten me in the ranklist... :-? :-?
:cry: :cry: :cry: :cry:

Posted: Sat Jan 03, 2004 5:11 pm
by Noim
Andrey Mokhov,
:lol: that's really funny.
any way i thank to you for your hints ... :lol:

Posted: Sun Jan 04, 2004 7:12 am
by shamim
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

Posted: Sun Jan 04, 2004 9:52 am
by Andrey Mokhov
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.

10590 Wrong answer

Posted: Thu Jan 08, 2004 5:00 pm
by Alexander Kozlov
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.