JOIN
 Match Editorials
TCHS SRM 6
Monday, July 10, 2006

Match summary

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

DigitalDisplay
Used as: Level One:
 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.

WildCardMatch
Used as: Level Two:
 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) ```
See MB__'s solution for a similar approach, but in reverse order.

BracketMaze
Used as: Level Three:
 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);
}
```
All solutions used this approach. Once we got the recurrence we store it in a table, to make sure the same (i,j,k,x) state is never calculated twice. See Burunduk3's solution for an implementation of this.

By myprasanna
TopCoder Member