Match Editorial

The top two scorers in Division-I, 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 Division-II, 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 Problems

Value	300
Submission Rate	165 / 182 (95.38%)
Success Rate	104 / 165 (63.03%)
High Score	lordduke for 295.83 points

Reference implementation: qsort

Implementation

Since 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.

Value	550
Submission Rate	131 / 182 (71.98%)
Success Rate	110 / 131 (83.97%)
High Score	jwjchap for 538.69 points

Reference implementation: cnettel

Implementation

The easiest way to find all 3-number 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 for-loops is usually better.

Once we have the 3-number combinations, to find the median we can either apply several if-statements 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.

Value	1000
Submission Rate	57 / 182 (31.32%)
Success Rate	33 / 57 (57.89%)
High Score	Parchandri for 698.74 points

Value	500
Submission Rate	105 / 125 (84.00%)
Success Rate	94 / 105 (89.52%)
High Score	Yarin for 452.48 points

Reference implementation: Yarin

Implementation

Card 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 error-prone, 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.

Value	250
Submission Rate	119 / 125 (95.20%)
Success Rate	93 / 119 (78.15%)
High Score	Yarin for 244.93 points

Reference implementation: Yarin

Implementation

This 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.

Value	1050
Submission Rate	19 / 125 (15.20%)
Success Rate	13 / 19 (68.42%)
High Score	dary for 837.80 points

Reference implementation: Yarin (practice room)

Implementation

The 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 color-switch 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¹⁰ = 59049 such combinations, which is feasible. The nice thing now is that on all remaining rows, the number of color-switches 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 color-switches on the first row:

BGBRB
RBRBR
BRGRB
BGRBB
RBBRG

We will not do any more color-switches 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 color-switch 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 color-switch the squares beneath those in row 3 etc. This procedure is repeated through all rows; row y-1 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 x-1,y-1 is B (or if x=0, check square n-1,y-2). 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.