An amazon week

On Wednesday, TopCoder SRM 703 - the first TopCoder round after the TCO - took place (problems, results, top 5 on the left). Endagorion has claimed the victory thanks for an amazingly fast solution for the 1000 - he submitted it in just over 7 minutes! It turns out that a similar problem has appeared before, and he could reuse most of the code. Nevertheless, congratulations on the flawless execution!

Codeforces Round 385 on Saturday has gathered 8 nutella-rated participants, including the top 3 (problems, results, top 5 on the left, analysis). Tourist has guaranteed himself the first place in just over an hour, but couldn't solve everything because of extremely tricky geometric problem D. Congratulations on the win!

Here's problem E which has propelled him to the top, in a slightly simplified form: you are given n words with total length up to m, and need to check whether there exists a cyclic string that has at least two different decompositions into those words, in O(nm) time. For example, for a set {"aa", "aba", "ba", "bab"} the cyclic string "ababa"="babaa" has two decompositions: "aba" + "ba", and "bab" + "aa".

Finally, Open Cup 2016-17 Grand Prix of Peterhof has (probably?) wrapped up 2016 for many ACM ICPC teams (results, top 5 on the left). Problem E was the most unusual and thus the most creative: you needed to give a checkmate to a lone king on a 8x8 chessboard using just one piece: the amazon, that can move both as a queen and as a knight. To makes things harder, you are playing blindfolded and do not know the king's position or moves. More precisely, you are given the initial position of the amazon, and need to output such sequence of at most 50 moves that the king that starts in any position that is not checked by the amazon and makes any legal moves will eventually be checkmated at some point in this sequence, and will not be stalemated before that. Can you figure out how to do it? How short can such sequence of moves be if the amazon starts at a1?

Thanks for reading, and check back next week!