970 - Particles
Posted: 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!
Can somebody explain a better solution?
Some hint, please!
Page 1 of 1
Posted: 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.
Posted: Sun Nov 05, 2006 4:36 am
Thanks, i got AC now! 
strict time limit..
Posted: 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.
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.
Posted: 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