| ENG RUS | Timus Online Judge |
Обсуждение задачи 1782. Новое слово ДжекаInstouT94 Does the greedy solution work? // Задача 1782. Новое слово Джека 21 окт 2023 16:50 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? bsu.mmf.team A question [2] // Задача 1782. Новое слово Джека 16 окт 2010 00:58 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! TestKiller Re: A question [1] // Задача 1782. Новое слово Джека 31 авг 2011 18:10 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. Deepesson Re: A question // Задача 1782. Новое слово Джека 18 апр 2023 23:20 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 xurshid_n WA1 ?? // Задача 1782. Новое слово Джека 28 июл 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 [1] // Задача 1782. Новое слово Джека 9 окт 2010 13:54 Могли ли подстроки вида xyxyx (из условия задачи) встречаться в промежуточных словах, написанных Джеком до финального? id-mikle Re: Подстроки вида xyxyx // Задача 1782. Новое слово Джека 9 окт 2010 18:38 В таком случае плохая подстрока будет и в финальной строке Kornilov Peter Wrong answer 47 // Задача 1782. Новое слово Джека 9 окт 2010 16:51 Do you have any ideas why?
|