Tuesday, April 15, 2003 Match summary The top two scorers in DivisionI, Yarin and dgarthur were the same as in the recent TCCC final, but this time with Yarin as the winner. In third place came dary after a very impressive performance in only his second SRM! In DivisionII, PJYelton took a comfortable win after delivering 5 successful challenges. The difficulty level of the problem set was very good, with a good distribution of scores and submits. The ProblemsFarmFenceUsed as: DivisionII, Level 1:
Reference implementation: qsort ImplementationSince the area of the rectangular area must match crops exactly, we will have to loop through all possible rectangles of integral size. We only need to loop one side of the rectangle; the other side can be calculated by taking crops/first_side, assuming this value is an integer. This is true if crops%first_side==0 (if you're unsure about the % operator, you should check this out more carefully as it's a very useful operator!). It's possible to loop first_side from 1 to crops, but we actually only have to loop it to sqrt(crops). The reason is that once first_side is greater than sqrt(crops), the second side of the rectangle will be less than the first_side, and those rectangles we have already checked! For each rectangle, we sum up the sides and check if this is better than the best found so far. MedianOfThreeUsed as: DivisionII, Level 2:
Reference implementation: cnettel ImplementationThe easiest way to find all 3number combinations is to have three nested loops: for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) for(int k=j+1;k<n;k++) One can also use recursion, but when the number (in this case 3) elements are fixed and sufficiently small (3 or 4), having several nested forloops is usually better. Once we have the 3number combinations, to find the median we can either apply several ifstatements or we can put the 3 numbers in an array, sort the array and pick the middle element. The latter method is definitely shorter to code, if using the built in sort function in your programming language. LambChopUsed as: DivisionII, Level 3: Used as: DivisionI, Level 2:
Reference implementation: Yarin ImplementationCard simulation games occurs frequently in TopCoder competitions. They usually have one thing in common if you want so solve them: Following the instructions precisely and do not try to be clever by doing things in a different order than what is stated. Each game is run independently (or almost so, you need to know who starts pulling a card from the previous game). For each game, we can keep an array of booleans marking if a player is lamb or not. For simplicity we also keep a counter of how many players are not lambs. We of course also need to know who the current player is (at the very start of the method we initialize this to 0) and the value of the counter, which we set to 1 at the start of a round. The easiest, and less errorprone, way to do the inner loop of the problem is to not loop over all cards but to have an infinite loop (while (true) ) that is jumped out of when that round is over. Inside this loop we check if the rightmost digit of the counter (counter modulo 10; one can also convert the number to a string and check the last character) is the same as the card value. If this is so, we mark the player as lamb and decrease the number of players left, in other case we increase the counter. After this we check if we have run out of cards, and if so take the appropriate action (increase the score of all remaining players by one). Otherwise we check if there's only one player left, in which case he gets his score increase by the total number of players. If the game still goes on, we find out who is next in turn, making sure we don't select a player who is lamb. The most common error in this problem is that people first checked if there was only one player left, then if there are no cards left. This won't work if the final card reduced the number of players from 2 to 1, in which case you would award the last player with too much. Another possible error was to compare the card value with counter instead of the last digit of it. Both these errors would have been caught if you tried all examples. Now when it's so easy to check all examples quickly, one should always check them all! If you get the wrong answer, there's really no point of submitting as this will only give your opponents a chance of 50 extra points. VigesimalUsed as: DivisionI, Level 1:
Reference implementation: Yarin ImplementationThis problem consists of two separate sub problems: convert a number to base 20 (vigesimal) and sort those numbers using a given sorting order. Converting numbers to other bases is something most programmers have done before, although I'm sure not that many had converted a number to base 20 before... Still, the method is the same as ever: we find the last digit by doing modulo 20, then divide by 20 and take modulo 20 again to find the second last digit etc, until there are no more digits left (the value is 0). This method is, if I remember correctly, taught early in high school math. We just have to make sure we convert 0 to "0", and not ""! This happens automatically if we have a do { ... } while (value>0); loop instead of while (value>0) { ... }. If you don't know how to specify your own sorting operator to your programming language sorting function, that's something you should learn. In this problem, a vigesimal value is before another value if it's shorter or if its rightmost different digit is less. The latter can be checked by looping through all digits (in base 20) from the right and halt on the first different digit. FlipFlopUsed as: DivisionI, Level 3:
Reference implementation: Yarin (practice room) ImplementationThe first thing to realize is that you never have to do a color switch more than two times on a square. If you do a colorswitch 3 times, it's the same thing as doing it 0 times etc. Thus there are 3^{n*m} combinations of switches that are relevant, which is way too much since n*m can be 100. The trick is to only consider all relevant switches on the first row. There are at most 3^{10} = 59049 such combinations, which is feasible. The nice thing now is that on all remaining rows, the number of colorswitches for each square is forced: we don't have to try switch it 0, 1 or 2 times, because there is only one possibility if we are to color all squares blue! Assume the squares look like this after we have tested one combination of colorswitches on the first row: BGBRB RBRBR BRGRB BGRBB RBBRG We will not do any more colorswitches on the first (since we will try those combinations later on anyway). So the only way to now affect the squares in the first row that are not B, is to colorswitch the square in the row below. Since the first row above is BGBRB, in order to turn that to BBBBB we must color switch, in row 2, column 2 one time and column 4 two times. Any other color switch in row 2 will make the squares in row 0 to be something other than BBBBB. When doing this color switches, we have changed the colors of the squares in row 2 and row 3 as well. Now we can repeat this procedure: the only way to fix those squares in row 2 that are not B is to colorswitch the squares beneath those in row 3 etc. This procedure is repeated through all rows; row y1 tells us how to color switch row y. Once we have looped through all rows, we just check that the final row also turned up BBBBB. Since there is no row after the last row, if the last row is not BBBBB right away then there's no way to fix this. If the last row is BBBBB, we check if the number of color switches we did is less than the best so far, and then update this value. One can also solve this problem using recursion, working row by row, column by column. If the current square is x,y, then the only pruning you have to do is make sure the square at x1,y1 is B (or if x=0, check square n1,y2). This will actually be the same thing as the solution described above, but requires less code. My practice room solution uses this method. It's also possible to find a solution by solving a linear system equation in modulus 3. The drawback with this is that I'm not sure how you actually find the smallest solution. Some people solved this problem quite fast. One reason for that is most likely because they've seen this kind of problems before, as similar problems have occurred in other programming competitions before. For a more general analysis of the problem, one can check out the following link: Turning the Lights Out in Three Dimensions. 
