|
|
My idea is to reverse the operations of adding characters and doubling a string. I have an iterative algorithm in O(n * log(n)). At each iteration, I count dp - the length of the maximum substring ending with index i, obtained by the doubling operation. Then I look for the maximum among the maximum substrings and truncate the current string to leave this substring. But this is a greedy solution. Is it possible to come up with a counterexample to it? In my AC solution I didn't use the fact that "there is no substrings in the form xyxyx" anywhere. My program even assumes the answer in this problem can be "-1", but I guess there are no such testcases in this problem because of this advanced condition. So, could anybody tell me how this fact helps to simplify the solution? Or, maybe, anybody can prove or deny my hypotesis about "-1"? Thanks in advance! Well, I must admit the fact, that I didn't even notice this strange condition when I was trying to solve this problem, and now, I have passed all tests with simply using Depth First Search. In fact, if this condition holds, let x be 0 or 1 and let y be a null string, so there could not exist a substring with 3 consequent, and same characters. This could do good to the simplification of saying the word. So I guess that, when using this condition, we could not generate any "No solution" cases, so that solutions should exist. So, when using DFS, one could find some acceptable construction of the word easily. Yeah... I also don't understand a couple thing of the statement: Why they are restricting the answer to only 100 moves. Why they aren't asking the minimum number of operations. And finally, why there's the xyxyx restriction. I managed to find the minimum number of operations in O(N log N), so really, the statement just doesn't make any sense to me... I enjoyed the problem though Hi! My program got output for test1 (011010011): 5 back 0 double double double front 1 --------------------------------------- ''-> 0 -> 01 -> 0110 -> 01101001 -> 011010011 It's right? Upd: I found bug in my program, and fixed it, AC! Edited by author 28.07.2012 17:59 Могли ли подстроки вида xyxyx (из условия задачи) встречаться в промежуточных словах, написанных Джеком до финального? В таком случае плохая подстрока будет и в финальной строке Do you have any ideas why? |
|
|