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 ProblemsDigitalDisplayUsed as: Level One:
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 112 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. WildCardMatchUsed as: Level Two:
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:
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?
Now let us move through the cubespace 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 statespace becomes (i,j,k,x) P(i,j,k,x) // is the number of paths from coord (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. 
