Discussion @ 1669. Universal Word @ Timus Online Judge

How to avoid TLE

Posted by SevenEleven [Tartu U] 31 Dec 2008 16:02

Can M*N*2^(n) dp solution be improved, so that it passes all test? ( Probably it could be M*2^(n)), or it's wrong and I have to think on completely new solution?

Re: How to avoid TLE

Posted by vav[14] 5 Jan 2009 19:28

Yes. It can be easily optimized to O(N*log|S|*2^N).(|S| - is the length of the word). But even O(N*|S|*2^N) solution can pass all tests.

Re: How to avoid TLE

Posted by Alexander Georgiev 24 Feb 2009 03:50

Well, my n * s * 2^n solution didn't pass until I added a (as it turned out) curcial optimization.

Edited by author 27.07.2009 03:08

Re: How to avoid TLE

Posted by ConanKudo 1 Aug 2010 16:58

My solution is s*2^n ... it runs extremely fast with a very short code :)

Edited by author 01.08.2010 16:59

Edited by author 01.08.2010 16:59

Re: How to avoid TLE

Posted by Oracle[Lviv NU] 20 Aug 2011 19:56

N*2^N exists.

Discussion of Problem 1669. Universal Word