Match Editorial
SRM 295
Wednesday, March 29, 2006

Match summary

Being the second money match in a row, SRM 295 attracted 864 participants with 380 competing in division 1 and 484 in division 2. In division 1 SnapDragon took the lead 75.57 points ahead of the second placed Tomek who was followed closely by Ying, Eryx and WSX, all within one challenge. This is SnapDragon's 40th SRM victory! Congratulations! In division 2 it was a close race but in the end need4speed took the lead, followed by FreePeter and amiune.

# The Problems

PaperRockScisQuals
Used as: Division Two - Level One:
 Value 300 Submission Rate 360 / 450 (80.00%) Success Rate 181 / 360 (50.28%) High Score LS8464 for 299.15 points (1 mins 31 secs) Average Score 202.86 (for 181 correct submissions)

The solution for this problem is a straightforward simulation. The trick is implementing 2 completely different scoring systems, one to score individual head-to-head games, and one to rank the players. Scoring games is simple, just follow the rules in the problem statement and transform them in a bunch of if-s. Ranking the players however can be done a bit more cleaner than suggested in the problem statement. Instead of using 0, 0.5 and 1 point, you can use 0,1 and 2 points instead, since it will not change the order of players, but is easier to implement. Another thing worth noticing here is that, with the problem value of 300 points it is wise to spend a few moments proofreading your code than to make a fast, but flawed submission. For a clean implementation check FreePeter's code in the arena.

BuildBridge
Used as: Division Two - Level Two:
 Value 500 Submission Rate 264 / 450 (58.67%) Success Rate 217 / 264 (82.20%) High Score letusplay for 498.21 points (1 mins 42 secs) Average Score 357.18 (for 217 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 321 / 361 (88.92%) Success Rate 308 / 321 (95.95%) High Score antimatter for 249.33 points (1 mins 28 secs) Average Score 196.47 (for 308 correct submissions)

This problem was a bit more pen&paper oriented because once you figure out the correct solution, implementing it is quite easy. The basic idea is that if we already have a stack of N cards, we can use that stack to create a new stack, sized N+1 by sliding a card under the old stack. The center of mass of the stack of N cards is known to hold N times the mass of a single card, so the resulting center of mass for N+1 cards is 1/(2*(N+1)) of card lengths right from the edge of the new card.

This idea was hinted in the problem statement, with detailed explanation of calculating the center of mass of 3 cards. Now that we can calculate the extension for any number of cards, due to small input we can simply iteratively add cards until we reach the required extension. To simplify the problem, the biggest testcase was given in the examples. This idea comes down to the following code:

```public int howManyCards(int d, int l){
int ret = 0;
double n = 0.0;
double x = 2.0 * d / l;
for (ret = 1; ; ++ret) {
n += 1.0 / ret;
if ( n - x > -1e-12 ) break;
}
return ret;
}
```

JimmyLightning
Used as: Division Two - Level Three:
 Value 1050 Submission Rate 55 / 450 (12.22%) Success Rate 6 / 55 (10.91%) High Score johann for 817.52 points (16 mins 8 secs) Average Score 613.42 (for 6 correct submissions)
Used as: Division One - Level Two:
 Value 500 Submission Rate 257 / 361 (71.19%) Success Rate 117 / 257 (45.53%) High Score krijgertje for 471.11 points (7 mins 7 secs) Average Score 328.36 (for 117 correct submissions)

In division 2 this problem was worth 1050 points, and with a good reason. Even though the algorithm is a simple knapsack, there were tricks all around. Rooms are numbered starting from 1, Jimmy must leave before the door closes, more than one diamond type per room...
The basic solution is DP, more precisely - knapsack. If diamond X(V T R) can be stolen at time N then the value for N is equal to (V + (value for N - T)).

Of all such possible values for N, we choose the largest and proceed to N + 1. Now all we need to do is determine if diamond X can be stolen at time N. We do this by checking weather N is STRICTLY smaller than all door times from room 1 to room R.
Here is the part of the code that does the actual calculation (array d is of type diamond where time is the last time it can be stolen at, diff is the time required to steal it and value is the diamonds value):

```int[] s = new int[1001];
s[0] = 1;
for (int t = 1; t < 1001; ++t) {
s[t] = s[t - 1];
for (int i = 0; i < d.length; ++i)
if ((t < d[i].time) &&
(t - d[i].diff > -1) &&
(s[t] < s[ t - d[i].diff ] + d[i].value)) {
s[t] = s[ t - d[i].diff ] + d[i].value;
}
}
return s[1000] - 1;
}

```

For clean implementations in C++ check antimatter's solution, and for C# check Petr's.

TribbloTrouble
Used as: Division One - Level Three:
 Value 1000 Submission Rate 82 / 361 (22.71%) Success Rate 15 / 82 (18.29%) High Score SnapDragon for 634.03 points (24 mins 50 secs) Average Score 497.49 (for 15 correct submissions)

The most common error coders did on this problem was to try a DP solution. The problem with DP solution is that the code can form loops of 'W'-s, and this is incorrectly handled. The correct approach was simulation. However, the straightforward simulation that moves the tribbles square by square will fail because there can be loops 2500 steps long and you would need to iterate 72000 times to get enough precision (barely, check testcase 40.). This will by far exceed the 2 second time limit. What you need to notice at this point is that only objects 'S', 'W' and 'T' affect the returned value, so instead of square by square you can move tribbles object by object. This gives us at most 25 objects that can be reached from the starting point (testcase 7 is an example of this). This can be safely iterated well above the limit needed to reach 1E-9.
The code for this problem is a bit too long to be placed completely within the summary, however my code has been uploaded in the practice room for your convenience. One implementation detail you will notice is that instead of 25 objects I split each object into 4 objects corresponding to 4 cardinal directions the tribble can move in, thus getting 100 objects max.
For all you math lovers out there, there is also a solution involving linear equations. See lovro's solution in the practice room.

By ivankovic
TopCoder Member