International Olympiad in Informatics (IOI): How can I solve question 4 of ZIO 2011? (see link in question details)

<failed miserably at using latex on quora, sorry if you dont get my answer, try to figure it out yourself> So let me explain the reconstruction of my solution. First note that your last column of the matrix, your input, has exactly each of the [math]a_i[/math] exactly once. ie. The column itself is a permutation of your desired binary sequence. Secondly, it is important to note that we are not asked the exact binary sequence that generated the whole matrix but only the top most row in sorted matrix, ie. lexicographically the lowest cyclically shifted sequence that is possible. Third major observation is that we can always reonstruct the first column of the sorted matrix. By simply sorting the digits in your provided last column. Fourth important observation is that any two consecutive columns, when taken together, contain a list of all possible bigrams (ie. 2 digit strings) that are part of your desired binary sequence. Similarly, any k consecutive columns taken together contain a list of all k-substrings of the desired sequence. Fifth and the last, but not the least major observation is that in the sorted matrix, taking the first k columns of the matrix together, gives a sorted list of k-substrings of desired binary string. So for example in the first case given (last column = 10111100) We know length of answer string (let us call it [math]A[/math]) is 8 Let [math]C_i[/math] denote ith column. then we know [math] C_8 = 1,0,1,1,1,1,0,0 [/math] by observation 3, we thus know that [math] C_1 = 0,0,0,1,1,1,1,1 [/math] Now these two columns (cyclically consecutive) have a list of all bigrams in the sequence, the same list which would be present with the first two columns together. [math] C_8 = 1,0,1,1,1,1,0,0 [/math] [math] C_1 = 0,0,0,1,1,1,1,1 [/math] [math] C_8 C_1 = 10,00,10,11,11,11,01,01 [/math] we know [math] C_1 C_2 [/math] also contains same elements, but in sorted fashion thus [math] C_1 C_2 = 00,01,01,10,10,11,11,11 [/math] [math] \Rightarrow C_2 = 0,1,1,0,0,1,1,1 [/math] now similarly look for trigrams in [math] C_8 C_1 C_2 [/math], to get [math] C_1 C_2 C_3 [/math] by sorting, and deducing [math] C_3 [/math]; deducing  [math] C_4 [/math] from 4-grams of [math] C_8 C_1 C_2 C_3 [/math]; and so on... till you get the first row. This is, if done, naively, something like a cubic algorithm, probably, I never analyzed it as such. But its pretty easy when you filling the matrix with pen and paper. Note: If anyone ever figures out how to use multiline matrices using LaTeX in Quora text editor, please, I beg of you, let me know...