970 - Particles

joeluchoa · 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!

mf · 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.

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

Thanks, i got AC now!

sohel · 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 · 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

OJ Board

970 - Particles

970 - Particles

strict time limit..