August 14, 2018 Editorial For TCO18 India Regional SRM

The TCO18 India Regional featured an SRM event. Or actually there were 2 SRMs –
the short one, lasting for 10 minutes, and the regular one, lasting 75 minutes + challenge phase. The objective of the first round was to warm up and get into the environment. It was intended mostly for participants new to Topcoder Arena.
I will cover 2 tasks here – from the regular round. The medium task from the full-sized SRM is already covered by maxwells_daemon, and the warm up task is not available anymore. I can say only that it was classical and can be solved using the Dynamic Programming. hmehta wanted a more complex set of tasks than the usual difficulty Regional rounds have. This was done to distinguish between the leaders more clearly. As a direct result, many scored zero.

SymmetricImage

In this task you are given a matrix, the question is to determine if it is symmetrical. The return has to be 0 for no symmetry, 1 for either horizontal or vertical symmetry, and 2 for both horizontal and vertical symmetry.
44 participants managed to solve the task and pass the system tests. As this is less than a half of the ones who opened the question, I find it necessary to provide the algorithm.
Let us check for the 2 types of symmetry independent one from the other. For instance, checking the horizontal symmetry is done as follows:

        boolean horizontal = true;
        for (int i = 0; i < image.length; i++) {
            for (int j = 0; j < image[i].length(); j++) {
                if (image[i].charAt(j) != image[image.length - 1 - i].charAt(j)) {
                    horizontal = false;
                }
            }
        }

As you can see, we set a Boolean flag indicating that there is a horizontal symmetry to true initially, assuming that there is a horizontal symmetry. This assumption is the key. Then, in the inner loop we validate this assumption. Incase it turned out to be wrong, we point that out in our Boolean flag.
There is no horizontal symmetry if and only if there is some cell so that its value does not match with its symmetrical cell. And the index of the symmetrical cell for a cell (i, j) is (n-1-i, j). No magic, by definition of symmetry we have S(x, y) = (-x,y). However, as our indexing starts with 0 not -n/2, the formula provided is correct.
You can write the code for the vertical symmetry as an exercise.
The final check is trivial – we have 2 Boolean flags and need to do some conditional statements on them.

Shuffler

This task has a rather complex statement. I ask you to read it first and spend a few minutes on thinking about this puzzle before reading further.
The main idea I used for this task was that you can generate the solution in iterative manner, letter by letter. This is due to the fact that with any order of the cards, you can get a concrete letter on top in 5+1=6 steps or less. The proof is similar as in Radix Sort.
Thus, we have reduced the task t a simpler one, namely to move the card indexed K into the first position. The order of the other cards does not matter, neither in the original configuration, not in the final. Additionally, it would be nice to have the sequence as short as possible.
I solved this simpler task by using Dynamic Programming (DP). The state of the DP is 1-dimensional. It is as simple as the possible index of the card with the wanted letter. For instance, if I want a letter B to appear on the top, and currently B is number 11, then I set DP[all] = ∞, DP[11] = 0. I populate the DP table until the DP[0] is eventually filled with a number.
The DP transition is just checking all 2 types of the operations allowed. I wrap the DP table mutation into an “infinite” outer loop to ensure that all the states are populated. The exit condition is that the DP[0] is filled with a finite integer.
Then I reconstruct the solution backwards. Finally, the R symbol is appended to the result to indicate that the next wanted letter is on top. Note that for reconstruction purposes I store an extra FROM table, that just remembers the previous DP state that we used to transition into the current one.
The next phase is just apply the next letter finding pattern to the original letter sequence. This is needed in order to be able to solve the puzzle for the next letter in the given input string.
See the complete code if you need additional explanation.
As an exercise you can write a recursive solution with memoization that solves the same task.

Final Notes

I personally liked the tasks given at the event, and the event in general. I asked Harshit to make the Easy task easier the next time though, so that mostly everyone ends up with a positive score.