Match Editorial

SRM 158 had a well balanced set, with almost no confusion issues. Division 1 saw ZorbaTHut easily taking first place, with the highest score on the level 3, and a good 50 points ahead of Yarin, without the help of challenges. Newbie coder gevak edged out DimaGer by 20 points to win division 2, and got a nice 1815 debut rating. gevak also got the high score for his level 3 solution. Also of note, raquib pulled off 6 successful challenges in room 9, and radeye got 4 successful challenges in room 4, all with the same test case.

The Problems

Value	250
Submission Rate	191 / 210 (90.95%)
Success Rate	187 / 191 (97.91%)
High Score	Sleeve for 245.55 points (3 mins 50 secs)
Average Score	192.56 (for 187 correct submissions)

Since there are only 4 valid tire configurations, this problem can be solved with one loop. First, we write a function to rotate a tire set for 1 phase, and then we call the function on the initial value 4 times. If before the function, initial == current, then we return the current index of the loop. Otherwise, the initial tires will never equal the current tires, so return -1. Here is C++ code that will do this (assume the rotate function moves initial to the next phase):

int getCycle(string initial, string current)
{
  for(int i = 1; i <= 4; i++)
  {
    if(initial == current)
      return i;
    initial = rotate(initial);
  }
  return -1;
}

Value	500
Submission Rate	124 / 210 (59.05%)
Success Rate	82 / 124 (66.13%)
High Score	hilfiger for 480.66 points (5 mins 44 secs)
Average Score	317.11 (for 82 correct submissions)

Value	250
Submission Rate	144 / 146 (98.63%)
Success Rate	121 / 144 (84.03%)
High Score	b0b0b0b for 247.04 points (3 mins 7 secs)
Average Score	203.13 (for 121 correct submissions)

Unfortunately, not all of the languages have a function which can parse a number with an arbitrary base. In Java, you can use Integer.parseInt(), and in C++, you can use strtol(). However, I could not find an equivalent function for either C# or VB .net. .net does provide a function to parse a string in bases 2, 8, 10, or 16, but this will not help for any other base. Even so, converting bases is pretty straightforward. All you need to do is add the value associated with each character, and multiply by the base for every character parsed. The following C++ code does this:

int parseInt(string s, int base)
{
  int result = 0;
  for(int i = 0; i < s.length(); i++)
  {
    int v;
    if(s[i] >= '0' && s[i] <= '9')
      v = s[i] - '0';
    else
      v = s[i] - 'A' + 10;
    if(v >= base)
      return -1000;
    result *= base;
    result += v;
  }
  return result;
}

With the above function, you must check for -1000 to see if the base did not parse correctly. Alternatively, you can throw and catch an exception instead of returning -1000. So the easiest solution to the problem is to parse all the numbers for each of the bases from 2 to 20, and see which bases can parse the numbers properly, and for which the equation holds true.

As it turns out, if the addition of any digit happens to carry to the next digit, then the equation can only be valid for at most one base. If not, and the equation is valid mathematically, it is valid for all the bases which can parse the highest digit in the equation. For example, if the highest digit in such an equation is a 5, then the equation is valid for bases 6 and above.

Many people failed on the case "0+0=0" because they added a 1 to the resulting bases.

Value	1000
Submission Rate	33 / 210 (15.71%)
Success Rate	21 / 33 (63.64%)
High Score	gevak for 779.67 points (16 mins 4 secs)
Average Score	554.62 (for 21 correct submissions)

Most people will recognize the game that this question is based on (made popular by PopCap). The problem isn't concerned with the normal gameplay, but simply how many valid moves are left. To check if a move is valid, the best way is to swap two gems and see if the two gems just swapped are part of any horizontal or vertical line of 3 or more gems of the same type. To do this, see how many gems above and below the gem in question are the same, and see how many gems to the right and left are the same. If either of these adds up to 2, then you have a valid move.

To avoid duplicating moves, you only need to swap gems with others to the right of it or below it. However, you must remember to do all the gems, even the ones just above or to the left of the lower right corner.

Value	500
Submission Rate	96 / 146 (65.75%)
Success Rate	56 / 96 (58.33%)
High Score	radeye for 472.57 points (6 mins 55 secs)
Average Score	351.20 (for 56 correct submissions)

At first glance, one might be inclined to do some sort of optimization, or use a greedy solution. But with only 20 stamp pads, the brute force solution will only take 2^20 or 1 million iterations, executing in well under 8 seconds. One method is to loop from 1 to 2^pads.length and use each bit in the mask to determine whether a pad is included or not. The second is to use a recursive function, deciding on whether to include a pad or not, and recursivly calling for the next pad.

The second part of the solution is to determine which colors are satisfied by the stamps. Since we only care about at most 25 colors, we can use a bitmask to represent the colors from wishlist that have been purchased. If, after setting all the bits for the colors purchased, the bitmask includes all the bits in the wishlist, we minimize a pad count. If no combinations set all the bits, then we must return -1.

Value	1000
Submission Rate	13 / 146 (8.90%)
Success Rate	8 / 13 (61.54%)
High Score	ZorbaTHut for 650.43 points (23 mins 41 secs)
Average Score	534.83 (for 8 correct submissions)

Based on a well known amphibious game, this problem involves using a breadth first search to find the best path on a moving grid. First we note that there are two portions to the state of the board, the character position, and the position of all the pads. Since there are only 4 possible descriptions of a row of pads, and each pattern is 5 characters long, the position of the pads can be saved by storing the offset into the pattern that the current rows start with. This gives us a trivial maximum of 20x21x5x5x5x5, or 262,500 states. This is well within the boundary for timeout. However, we can prove that there are actually only 5 different board states, which reduces the number of states to 20x21x5, or 2100 states (we'll prove this later).

So for a BFS, we need a queue, and a way to represent the state. Simply saving the time used and the x and y position in a structure, or creating a hash code based on the values is sufficient. The next tricky part is to determine how the character moves. After every move, we must check to see that the character landed on a hoverpad, and after the move, check to see that the character did not get carried off the side of the board. The position of the hoverpads can be determined by some modulo math and the final position can be determined by simply adding the speed to the x coordinate. If the character lands safely, we add this new state to the queue and continue only if the state has not yet been encountered. Note that we also must check the case where the character does not jump.

To prove there are only 5 board states, we first derive an equation which gives us the offset into the pattern that any given row starts with. This offset is
(((-t * speed) % 5) + 5) % 5
Now, notice that if t is divisible by 5, then (-t * speed) will always be divisible by 5, and therefore ((-t * speed) % 5) will always be 0, making the whole equation 0. Therefore, all rows will be offset to 0 every 5 seconds, regardless of speed. Since every pattern starts out at offset 0, this means the patterns all loop every 5 seconds, and we can only have at most 5 board states.

Other solutions used a maximum time to limit the running of the solution. Since there were only 20x21 board locations, limiting the time to 10000 seconds works and is the solution ZorbaTHut used.