Need help with USACO problem

[mlvahe]

I can't find any algorithm to solve this problem. Can you help me with ideas.

I am at section 1.4.1 and can't move on.

[TAKEN FROM USACO TRAINING GATEWAY]

Cryptcowgraphy
Brian Dean
The cows of Farmer Brown and Farmer John are planning a coordinated escape from their respective farms and have devised a method of encryption to protect their written communications.

Specifically, if one cow has a message, say, "International Olympiad in Informatics", it is altered by inserting the letters C, O, and W, in random location in the message, such that C appears before O, which appears before W. Then the cows take the part of the message between C and O, and the part between O and W, and swap them. Here are two examples:

International Olympiad in Informatics
->
CnOIWternational Olympiad in Informatics

International Olympiad in Informatics
->
International Cin InformaticsOOlympiad W

To make matters more difficult, the cows can apply their encryption scheme several times, by again encrypting the string that results from the previous encryption. One night, Farmer John's cows receive such a multiply-encrypted message. Write a program to compute whether or not the non-encrypted original message could have been the string:

Begin the Escape execution at the Break of Dawn

PROGRAM NAME: cryptcow
INPUT FORMAT
A single line (with both upper and lower case) with no more than 75 characters that represents the encrypted message.
SAMPLE INPUT (file cryptcow.in)
Begin the EscCution at the BreOape execWak of Dawn

OUTPUT FORMAT
Two integers on a single line. The first integer is 1 if the message decodes as an escape message; 0 otherwise. The second integer specifies the number of encryptions that were applied (or 0 if the first integer was 0).
SAMPLE OUTPUT (file cryptcow.out)
1 1

[Alessandro]

I'm blocked by that problem, too. I wish someone can give us some advice...

'bye

[Andrey Mokhov]

Hi!

There is no way to solve this but backtracking. And it doesn't give TLE only because the tests are very simple. I saw judge solution. It is also very inefficient and hanged for hours on my hard tests. So don't think much. Try to write simple brute force and hope for AC.

Good luck!
Andrey.

[Alessandro]

I finally solved Cryptcow. It wasn't so hard.

Let's start with a string containing a C, a O and a W; you can easily decrypt it and obtain a new string. If the remaining string hasn't the three letters above, just see if it matches the original string, otherwise continue decrypting.

Given the initial string, just try to decrypt it with every C combined with every O combined with every W. You obtain a new string: repeat all until you can't decrypt anymore.

If the message is completely encrypted, you have 9!^3 possible ways to check. This solution space is just too big, so you have got to prune the search. These are the advices:

1. You can't decrypt a string with the C after the O, or the O after the W.

2. Search every letters C,O and W in an encrypted string; the leftmost of these letters must be a C, and the rightmost a W, otherwise the string isn't a valid encrypted string.

3. The Cs, the Os and the Ws divide the string in multiple substrings; if the string is a valid encryption, these substring must be contained in the original message. With strstr(), contained in string.h, try if every substring of the string is contained in the correct message; if not, it isn't a valid encrypted string.

4. The leftmost part of any encrypted string, until the first C, must match the original correct message exactly.

So, just try to decrypt every possible string starting from the input, obtaining other strings that can be decrypted. Don't consider unvalid strings.

Consider to perform low-level optimizations, too. I declared some variables used by the functions as globals to avoid reallocation of those variables.

[little joey]

I fully agree with Andrey. In one word: disgusting.

One more tip: handle the 'W's backwards (from the end of the string to the front). This reduced the runtime for case 8 by a factor 5 and pulled my code below the runtime limit. Pure coincidental, but it worked...