| Show all threads Hide all threads Show all messages Hide all messages |
| how to prove the answer is NO when k > 20 | panyong0202 | 1669. Universal Word | 30 Nov 2014 18:19 | 1 |
I have got ac by return NO when k > 20, but how to prove it? |
| What is algo? | IgorKoval(from Pskov) | 1669. Universal Word | 29 Sep 2013 16:23 | 2 |
simple DP:
int leftPos[char][pos] position of char which is left or equal of pos
int lastPos[mask] : for substring s[lastPos[mask]..s.length()-1] we can get all name of sportman with char which is in mask.
=) |
| test 70： n == 18 and answer is YES | Orthocenter | 1669. Universal Word | 8 Mar 2012 13:37 | 1 |
|
| How to avoid TLE | SevenEleven [Tartu U] | 1669. Universal Word | 20 Aug 2011 19:56 | 5 |
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?
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. 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 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 |
| Wonder what's the solutions which runs in 0.1 second? | Gandalf | 1669. Universal Word | 20 Feb 2010 18:29 | 1 |
|
| Wrong Answer #73 | Vanja Petrovic Tankovic | 1669. Universal Word | 3 May 2009 15:20 | 3 |
I don't print 'NO' if N is large, I check it normally, but I still get WA #73? Whats the trick with this test?
Is there a word that is 'YES' for N>18?
Edited by author 03.05.2009 00:44 My AC program assumes there is no string with N>18, so debug your code Thanks, I had a silly bug. |
| Time Limit Exceeded - Test #14 | Varun Sharma | 1669. Universal Word | 30 Apr 2009 09:29 | 1 |
Hi,
For large test cases like n = 18 etc, if the answer is Yes, does that mean that our program will need to test for all the 18 factorial possibilities ? That's like running the loop 10^16 times which is impossible within 3 seconds !
Thanks |
| Is n<=8??? (If the word has <300 letters) | Yulia | 1669. Universal Word | 2 Feb 2009 00:03 | 5 |
NO.
there are some pattern that satisfy for n>8
Edited by author 20.12.2008 20:49 Suppose secuence like abcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklmabcdefghjklm etc.. I have WA 70.
please tell me is there any test case where n == 18 && answer == "YES"? int test 70 n == 18 and answer is YES ;) |
| No subject | vav[14] | 1669. Universal Word | 26 Dec 2008 14:05 | 1 |
Edited by author 28.12.2008 21:37
Edited by author 28.12.2008 21:38 |
| New test (+) | Sandro (USU) | 1669. Universal Word | 21 Dec 2008 22:46 | 1 |
We analysed AC solutions of this problem from online contest and add new test. 3 solutions from contest output wrong answer on it. |
| wrong answer #8 | Cu-star | 1669. Universal Word | 21 Dec 2008 07:29 | 6 |
i don't know why WA in test 8.
please help thx very much
i can find the mistake.
but i don't know how to correct I have faced the same problem. The test 8 - WA.
On the test:
4
abcabcab
The algorithm answers
NO i correct it
for this problem it must answer YES.
i use another algorithm but got WA in test 28.
plz. help
thx. Why on the test:
4
abcabcab
The answer - YES?
In the example there is no letter d |
| when will these problems add to prob. set? | wFeral | 1669. Universal Word | 20 Dec 2008 19:38 | 2 |
|
| How many tests are there? | Marginean Ciprian | 1669. Universal Word | 20 Dec 2008 17:45 | 1 |
|
