TopCoder SRM 557 - finally

SRM 557

Explanation for division 1 Easy and match recap. Explanations for div2 easy and div2 medium.

It feels like it has been ages since the last SRM. Here we go again.

It began with a bang. The 250 points problem reminds me a bit of a problem I wrote in the past, but I cannot remember its name. Something with black and white squares. They are very different problems, but I do remember that that problem was very tricky. This 250 points problem had like 8 examples, so I sort of felt it was going to have tricky written all over it. And decided to be careful rather than fast.

Div1 250: FoxAndMountainEasy

So, you start at height h0, is there is a sequence of n up and down moves such that:

• Each up move increases height by 1
• Each down move decreases height by 1. It is invalid to go bellow height 0.
• The given string history is a substring of the sequence of moves.
• The height after all of that stuff is hn

n is at most 100000. This problem gave me the feeling that it was initially intended for the TCO finals, but later they adapted it to SRM difficulty by reducing the constraints and adding plenty of examples.

The solution goes as follows: First process the history substring. After executing this series of moves, how much will be the netChange of the current height? (This is just equal to (number of Us) - (number of Ds). So if your current height is b before starting the sub-sequence of moves, the height after doing so will be b+netChange.

There is a catch though, if there are many D characters in the history sequence and not preceded by enough U characters, then the starting height before running the sequence, b, cannot be too small. b has to be large enough such that the current height while executing the subsequence is never bellow 0. (This can be calculated with a simple for loop - just simulate the movement starting at height 0, and remember the lowest height, if this lowest height is negative, then -lowest height is the minimum height value for b). We will call this required height before the subsequence - minStart.

After you have two things: netChange and minStart. We just need to do some extra things. There are (n - size(history)) moves left that we have to pick. Now here is the thing, the order of the moves does not matter a lot. We really only care about the height before the sub-sequence being at least minStart. Let us say that we are going to make u up moves, this means we will do d = (n - size(history) - u) down moves (in addition to the moves in history). Since we want the height before running the steps of the subsequence to be as large as possible, then it is better to first run all the u up moves before the sub-sequence and then all the d moves.

Due to the small constraints, we can just loop for a possible value of u between 0 and n-size(history). Then verify a couple of conditions: a) Is the height after running the first u moves at least minStart? . and b) Is the height after running all the moves, including the u up moves, the moves in history and the d down moves equal to exactly hn?. If you find a value of u for which the conditions are true, the result is YES.

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct FoxAndMountainEasy
{
    string possible(int n, int h0, int hn, string history)
    {
        int netChange = 0;
        int minStart = 0;
        for_each(ch, history) {
            // just simulate the movement, if ch=='U', increase
            netChange += ( (*ch == 'U') ? 1 : -1);
            // too low? remember this for minStart
            minStart = std::max(minStart, -netChange);
        }
        // Pick a value for u, the number of up moves done right at the start
        // and before the moves in the history string: 
        for (int u = 0; u <= n - history.size(); u++) {
            // the number of down moves to do later:
            int d = n - history.size() - u;
            // Do things work out?
            if ( (h0 + u >= minStart) && (h0 + u + netChange - d == hn) ) {
                return "YES";
            }
        }
        return "NO";
                 
    }
};

I took my time. Also , I made a couple of mistakes. It is a good thing the examples were so strong. (At first, I was first running all the up moves , then the down moves and finally the history moves. That is not correct.). I knew though that even with the strong examples, there were going to be many challenge opportunities. (And I also was not sure I was not missing a corner case).

Happened later

Then I opened the 550 points problem. Tried many things but faced some dead ends. Went back to 250, trying to think of corner cases. Opened 1000 5 minutes before the end of the coding phase and it seemed interesting.

The challenge phase was interesting because some people had very different solutions , and some were extra clever (or perhaps too clever?). I knew many of those solutions were going to have bugs, but it is not really easy to read them.

I was lucky though, because I caught a solution with an obvious bug. It began by checking if (hn - h0) % 2 != n % 2 and returning "NO". This logic is correct, and perhaps the approach needed this extra check. But there is something very wrong about the languages like c++ and Java that we love so much. Some language designers thought it is a useful convention to make the % operator return a negative number if the dividend is also negative. In my opinion, this feature is never useful and almost always just a cause of bugs. Modular arithmetic works by stating -1 belongs to 1 modulo 2. So it does not make sense. This bug with % operator has caught me in the past, so this time I could sense it and gained 50 points. Then I tried to find more instances of that mistake, but other coders doing this parity check took better previsions (In some cases though, I am not sure if intentionally).

Comments / etc?

Feel free to post your own opinions and accounts. I liked this match. It was a bit tough. But it is good to be back at competition. I am tired of watching people compete.