10590 - Boxes of Chocolates Again

Red Scorpion · Post by **Red Scorpion** » Wed Dec 31, 2003 7:15 am

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 · Post by **Andrey Mokhov** » Wed Dec 31, 2003 9:18 am

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

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

Red Scorpion · Post by **Red Scorpion** » Wed Dec 31, 2003 2:56 pm

Hi, all.

My equation is:

Code: Select all

cutted

should I reduce the paramter into one ?

Happy new year.

Thanks.

Whinii F. · Post by **Whinii F.** » Thu Jan 01, 2004 7:37 am

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".

Ghost77 dimen · Post by **Ghost77 dimen** » Thu Jan 01, 2004 7:56 am

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 · Post by **Red Scorpion** » Thu Jan 01, 2004 10:19 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 · Post by **windows2k** » Thu Jan 01, 2004 11:59 am

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]

Ghost77 dimen · Post by **Ghost77 dimen** » Thu Jan 01, 2004 2:59 pm

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 · Post by **Noim** » Fri Jan 02, 2004 2:06 pm

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

Andrey Mokhov · Post by **Andrey Mokhov** » Sat Jan 03, 2004 10:46 am

That's what I meant!

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

Noim · Post by **Noim** » Sat Jan 03, 2004 5:11 pm

Andrey Mokhov,

that's really funny.
any way i thank to you for your hints ...

shamim · Post by **shamim** » Sun Jan 04, 2004 7:12 am

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 · Post by **Andrey Mokhov** » Sun Jan 04, 2004 9:52 am

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 · Post by **Alexander Kozlov** » Thu Jan 08, 2004 5:00 pm

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.

OJ Board

10590 - Boxes of Chocolates Again

10590 - Boxes of Chocolates Again

10590 Wrong answer