Match Editorials

The High Schools matches are heating up, with quite a lot of registrants and yet another match with a reasonably hard medium. It gave the choice for some competitors to skip the 600 to strike the hard.

Zuza started off strong -- with two quick submits on the easy and the medium, while he raced to finish the hard -- but when his medium failed the challenge went to tomekkulczynski. Weiqi ended second and Burunduk3 came in third. The 600 and the 900 point problems were brutal, and most coders ended up with fairly low success rates.

The Problems

Value	250
Submission Rate	113 / 117 (96.58%)
Success Rate	77 / 113 (68.14%)
High Score	Zuza for 247.10 points (3 mins 5 secs)
Average Score	212.87 (for 77 correct submissions)

For this problem, it was enough to generate all 6 permutations and check if the numbers were within the range specified by the question. Many lost a lot of time trying to rely upon the next_permutation to do this, without noting that it doesn't repeat identical permutations. Eventually they struggled to get it patched and working.

        Alternatively a much simple approach exists:
        - If some was greater than 59, just return 0.
        - Count the number of numbers that fit within the 1-12 range. 

The answer was just twice this count, because the minutes and the seconds place were identical in bounds. So if a number could fit into minute's place, it could fit second's place as well. Hence counting how many numbers fit into hours would suffice, and the answer is just twice this. See Zuza's solution for a clear implementation of this.

Value	600
Submission Rate	69 / 117 (58.97%)
Success Rate	27 / 69 (39.13%)
High Score	jerzy.kozera for 588.88 points (3 mins 55 secs)
Average Score	457.09 (for 27 correct submissions)

This problem involves dynamic programming. A closely related algorithm is Edit Distance, though the knowledge of that problem was not required here.

        Let P be the pattern string and F be the file string.
        Let M(a,b) := minimal modifications of P[a... end] to match F[b ... end]

        if P[a] matches F[b] ( means P[a] can equal F[b] (or) F[b] is a '?' )
        then M(a,b) := M(a+1, b+1)
        otherwise
        M(a,b) := minimal of the following three:
        - Add a character which equals F[b], (one cost for adding the character)
        1 + M(a,b+1)
        - Remove the P[a]'th character, so that we look only into P[a+1 ... end] now.
        1 + M(a+1,b)
        - Modify P[a] to equal F[b], now we look only in P[a+1 .. end] and F[a+1 ... end]
        1 + M(a+1,b+1) 

Value	900
Submission Rate	48 / 117 (41.03%)
Success Rate	17 / 48 (35.42%)
High Score	Burunduk3 for 776.65 points (11 mins 42 secs)
Average Score	523.29 (for 17 correct submissions)

Again this one involved dynamic programming. In such problems we aim to minimise the total number of states that come into picture. Suppose you are given a string, how will you find if its a valid paranthesized expression?

Let x be the number of pending open parantheses, as you scan left to right through the string. When you encounter a '(', you increment x and when you see a ')', you decrement it. Expression is only valid if x is non-negative at every stage, and x was zero at the end.

Now let us move through the cube-space freely along the given directions. A cube point contains three parameters: (i,j,k). As we move we generate a string that needs to be valid. As noted above, adding one more parameter (x) is enough to assert this. So now the state-space becomes (i,j,k,x)

The following pseudo-code describes the recurrence involved.

    P(i,j,k,x) // is the number of paths from co-ord (i,j,k) to (N,N,N). There are currently x opening paranthesis
    pending to be closed.
    {
    if( (i,j,k) out of grid ) return 0;

    if( (i,j,k) equals (N,N,N) ) {
    if( x == 0 ) return 1;
    else return 0;
    }

    // Process the current character
    if( Maze(i,j,k) == '(' ) ++x;
    if( Maze(i,j,k) == ')' ) --x;

    // has it gone invalid ?
    if( x <0 ) return 0;

    // take all three directions.
    return P(i+1,j,k,x) + P(i,j+1,k,x) + P(i,j,k+1,x);
    }