970 - Particles

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

Moderator: Board moderators

Post Reply
User avatar
joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

970 - Particles

Post by joeluchoa » Sat Nov 04, 2006 9:14 pm

I've got TLE with DP, complexity O(n^3), in the reality n^3 * 9!
Can somebody explain a better solution?
Some hint, please!
http://acm.uva.es/problemset/usersnew.php?user=47903

All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:24-25]

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Nov 04, 2006 9:47 pm

I got 4.7 seconds, and my solution is also O(n^3) DP. It's just a bit optimized with bitmasks, and the innermost loop (which tries every possible split of a subinterval into two) breaks when it finds that all characters could be obtained on that interval.

User avatar
joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

Post by joeluchoa » Sun Nov 05, 2006 4:36 am

Thanks, i got AC now! :D
http://acm.uva.es/problemset/usersnew.php?user=47903

All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:24-25]

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

strict time limit..

Post by sohel » Mon Dec 04, 2006 1:34 pm

I think the time limit for this problem is too strict.
I got several TLEs before making some minor changes and managed to get AC. The changes that I made weren't that significant that would cause the time taken to come down drastically.

Changes included stuffs like converting int array to bool array and similar things like that.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Jul 01, 2007 4:10 am

I think the only way to get AC is to make sure that you use enough bit operations to make the runtime n^3, and NOT 27*n^3 or 9*n^3 or 3*n^3

Post Reply

Return to “Volume 9 (900-999)”