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.

Author: 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: $\mathcal{O}(1)$ ~\mathcal{O}(1)~

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

Time complexity: Average case $\mathcal{O}(M)$ ~\mathcal{O}(M)~

To generate words when $N \le 10^3$ ~N \le 10^3~, we can first generate the single character words $(a, b, \dots, z)$ ~(a, b, \dots, z)~, followed by two character words consisting of the same letter $(aa, bb, \dots, zz)$ ~(aa, bb, \dots, zz)~, and so on until we generate enough words.

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

Time complexity: Average case $\mathcal{O}(M + N \log N)$ ~\mathcal{O}(M + N \log N)~

For the fourth subtask, we can randomly generate characters until the hash $K$ ~K~ is reached. Notice that particularly bad values of $S$ ~S~, such as $S=1$ ~S=1~ and $S=M-1$ ~S=M-1~ are not allowed as test data.

Time complexity: Average case $\mathcal{O}(M)$ ~\mathcal{O}(M)~

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

Time complexity: $\mathcal{O}(M + N \log N)$ ~\mathcal{O}(M + N \log N)~

To generate words when $N \le 10^5$ ~N \le 10^5~, we can use a binary idea. We can generate all possible combinations of a and b from length $1$ ~1~ to length $16$ ~16~.

To generate words when $N \le 10^6$ ~N \le 10^6~, we extend the binary idea to include all $26$ ~26~ characters. Thus, the length of the words varies from length $1$ ~1~ to length $5$ ~5~.

For the sixth and seventh subtask, generate the first $N-1$ ~N-1~ 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 $K$ ~K~. 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 $S \equiv 1 \pmod m$ ~S \equiv 1 \pmod m~ and $M \equiv 0 \pmod m$ ~M \equiv 0 \pmod m~ for a large enough $m$ ~m~, then at least $100$ ~100~ characters must be generated.

Time complexity: Average case $\mathcal{O}(N \log N + (M/X + X) \log X)$ , where $X$ ~X~ is the number of suffixes generated. Note that on average, $\mathcal{O}(N \log N + M/X)$ ~\mathcal{O}(N \log N + M/X)~ characters are generated.

Comments

There are no comments at the moment.