Match Editorial

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

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.

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)

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;
}

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)

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;
}

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.