"I still don't understand how could you find the Trolls so fast," repeated the fairy for the second time.
"I've got some help," replied Alice.
"Some help? I have not seen anyone with you. Do you practice magic?"
"No, not at all. Do you see this laptop ...it's connected to the Internet though an infrared port and my phone. I've just stated the problem on some web-page and many people came to help me."
"The inter... what? An infrared 'port'? Harboring infrared ships perhaps? Sorry lass, I just understand what a phone is but I never heard of that inter-thingummy or a web-page," complained the fairy.
She was hovering few inches over the ground and was still for a moment as if to excuse her ignorance of the powers technological with the display of her powers beyond technological. Then she asked again:
"Still, I don't understand. No matter who had helped you how could you find the Trolls in mere 7 guesses in such a large forest as the last one was?"
"The first step was to sort out all sequences that didn't have unique number of repetitions in the forest. You've said that no other sequence in the forest repeated exactly the same number of times as the Troll did. This excluded the most possibilities leaving only 83 candidates for the Troll sequence. Now in the second step we could easily use binary search on this 83 candidates to find the Troll. We had to get the answer in at most 7 questions."
"Oh, Alice, binary search, Internet, number of repetitions ...you are talking enigma to me."
Yeah, but hopefully not to you! Alice was right. Both the stated problems were solvable within 10 questions (C1 within 4 and C2 within 7). The only thing to do was to sort out all sequences that repeated in the forest the same number of times as some other sequence (if 'cat' and 'dog' repeated 5 times in the forest then neither 'cat' nor 'dog' could be a Troll - see problem description). This could be done in several ways. The easiest is to count the number of appearances for each sequence in the forest and then write this sequence to a field in an array corresponding to that number of appearances. If there are two or more sequences written in one field of that array it means that these sequences have the same number of repetitions and therefor are not Trolls. We have to do this for all sequences that means we have to consider sequences beginning on the i-th letter of the forest and ending on the j-th for all i, j from 1 to "size of forest" where i < j. Schematically:
for i := 1 to size_of_forest
for j := i+1 to size_of_forest
seq := sequence from the forest beginning on the i-th and
ending on the j-th letter
rep := number of repetitions of the sequence seq
increase repArray[rep] by one
store seq in seqArray[rep]
for i := 1 to size_of_forest
if repArray[i]/i = 1 then seqArray[i] is a valid Troll sequence
(dividing by i since we counted all sequences i times)
no other sequence is a valid Troll sequence
This program would run for a long time. We have to add some optimizations. The easy one: if we find the sequence seq only once in the forest for some i and j then we don't have to search through the forest after we have increased j by one. There will be exactly one repetition of this longer sequence in the forest.
This optimization is enough to solve the C2 problem on a good computer within minutes.
The sample program that is appended to this description is more optimized. It solves the C2 problem on a good computer within seconds. The idea: we remember the locations of the sequence seq found in the forest and as we increase j by one the only candidates that have to be tested for the appearance of the (by 1) longer sequence are those stored locations of the original one. Now we should have a list of all possible Trolls. In C1 this list would contain the 'fox' the 'wolf' and some one letter sequences. It's a good thought that either 'fox' or 'wolf' would be the correct answer. Most of you guessed 'fox' but the correct answer was 'wolf'. We will have more problems with C2 where the list will contain 83 possible Trolls. The best is to use binary search: we will sort the list according to the number of repetitions and ask the fairy if the sequence in the middle of this list is the Troll. If the fairy answers yes then we have got the Troll. Else the hint of the fairy (more/fewer) will exclude half of the candidates. This can be repeated till we hit the Troll or only one candidate is left. This can be done in 7 guesses for as much as 127 candidates.
We hope that you liked this rather untypical problem.