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 1782. Jack's New Word

A question
Posted by bsu.mmf.team 16 Oct 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!
Re: A question
Posted by TestKiller 31 Aug 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.
Re: A question
Posted by Deepesson 18 Apr 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