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 ProblemsPaperRockScisQualsUsed as: Division Two  Level One:
The solution for this problem is a straightforward simulation. The trick is implementing 2 completely different scoring systems, one to score individual headtohead 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 ifs. 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. BuildBridgeUsed as: Division Two  Level Two: Used as: Division One  Level One:
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 > 1e12 ) break; } return ret; }Those of you that would like to learn more about this problem can do so here. JimmyLightning Used as: Division Two  Level Three: Used as: Division One  Level Two:
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...
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. 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:
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 1E9. TopCoder Member 
