Wednesday, August 6, 2003 Match summary 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 ProblemsTireRotationUsed as: Division Two  Level One:
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; }BaseMystery Used as: Division Two  Level Two: Used as: Division One  Level One:
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. GemsUsed as: Division Two  Level Three:
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. StampPadsUsed as: Division One  Level Two:
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. JumperUsed as: Division One  Level Three:
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 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. 
