|
|
| Show all threads Hide all threads Show all messages Hide all messages | | Does the greedy solution work? | InstouT94 | 1782. Jack's New Word | 21 Oct 2023 16:50 | 1 | 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? | | A question | bsu.mmf.team | 1782. Jack's New Word | 18 Apr 2023 23:20 | 3 | 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 | | WA1 ?? | xurshid_n | 1782. Jack's New Word | 28 Jul 2012 17:11 | 1 | WA1 ?? xurshid_n 28 Jul 2012 17:11 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 | Куплю мопед! | 1782. Jack's New Word | 9 Oct 2010 18:38 | 2 | Могли ли подстроки вида xyxyx (из условия задачи) встречаться в промежуточных словах, написанных Джеком до финального? В таком случае плохая подстрока будет и в финальной строке | | Wrong answer 47 | Kornilov Peter | 1782. Jack's New Word | 9 Oct 2010 16:51 | 1 | Do you have any ideas why? |
|
|
|
