## Editorial for TLE '16 Contest 4 P6 - Essay Writing

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: d

For the first subtask, we can output any lowercase letter. This subtask was intended to award participants who read all of the problems.

Time complexity:

For the second subtask, we can randomly generate characters until the hash is reached.

Time complexity: Average case

To generate words when , we can first generate the single character words , followed by two character words consisting of the same letter , and so on until we generate enough words.

For the third subtask, generate the first words, then randomly generate characters until the hash is reached. To prevent collisions, the last word should be longer than the first words.

Time complexity: Average case

For the fourth subtask, we can randomly generate characters until the hash is reached. Notice that particularly bad values of , such as and are not allowed as test data.

Time complexity: Average case

For the fifth subtask, things start to get more interesting. First, generate the words, and ensure that the last word is longer than all other words. Then all possible hashes can be reached by using a DFS/BFS approach. Afterwards, print the sequence of letters that lead to the hash .

Time complexity:

To generate words when , we can use a binary idea. We can generate all possible combinations of a and b from length to length .

To generate words when , we extend the binary idea by including all characters instead of just two characters. Thus, the length of the words varies from length to length .

For the sixth and seventh subtask, generate the first words and ensure that the last word is the longest word. This leaves slightly over 7.4 MB for the sixth subtask, and slightly over 2.2 MB for the seventh subtask.

Now, a meet-in-the-middle attack can be used to get a hash of . First, compute many suffixes that are short enough to be used. Then generate random characters until a suffix results in the correct hash value. It is not guaranteed that a naive implementation can pass all of the corner cases. For example, if and for a large enough , the smallest working suffix can be at least letters long.

Time complexity: Average case , where is the number of suffixes generated. Note that on average, characters are generated.