ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1669. Universal Word

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.