Thursday, November 2, 2006 Match summaryThis 9pm EST SRM attracted many long established Topcoder members, but had slightly below average numbers for a money SRM. It would appear as if it were a great opportunity to win a little bit of cash, but the high number of targets competing made it a tricky proposition.Division 1 was once again the scene for some recordbreaking scores, as the targets cashed in on a relatively simple 1000 point problem. The tricky 500 also led to ample opportunity for challenges. Unsurprisingly, the top 3 were comprised of tomek, Eryx and Petr  all targets who got over 900 points of the hard problem. tomek's fantastic 960 points, as well as 2 challenges, was good enough for a solid win and another spot on the Top 10 highest match totals. zhuzeyuan and John Dethridge finished 4th and 5th, both with 800+ scores on the hard and an excellent challenge phase. Special congratulations to zhuzeyuan for racing to achieve target status in a mere 15 competitions! Division 2 was dominated by newcomer zhanluwang, who completed all problems within 33 minutes, and even managed 2 successful challenges on his first SRM. Charizard, vinaysingh, Aesop and Yeung took second through fifth places. In addition, the Topcoder College Tour was visiting SUNY Binghamton this week, introducing the competition to students who may not have competed before. oneeyedelf, argonide and Asocasno won themselves an iPod Nano, a 1GB flash drive and a $50 voucher from Amazon.com for their troubles. Aaah, to be young and studying again... The ProblemsSalaryCalculatorUsed as: Division Two  Level One: There are just 2 cases to be considered here, each of which can be solved with simple algebra. Either the worker can earn salary within his first 200 hours, or he cannot. To test whether 200 hours is sufficient, we merely ask if salary ≤ P1 * 200.
if salary ≤ P1 * 200 return salary / P1 else return (salary  P1 * 200) / P2 + 200RGBStreet Used as: Division Two  Level Two: With the largest possible input, there are only 3*2^{19} possible house color permutations. The first house can be any of the 3 colors, and each subsequent house can only be one of 2 colors  the color of the previous house is disallowed. This meant that you could use simple recursion to solve this problem within the runtime, quite appropriate for a Division 2 medium problem. The recursive function needed to know the color of the previous house, as well as what number house we were busy with. The function attempts to paint the current house each possible color, excluding the previously painted color. It adds the cost of painting the current house with the cost of painting the rest of the street. The base case was when we had run out of houses to paint, and it would return 0. Psuedocode follows: int minCost(int previousColor, int houseNum) if houseNum ≥ houseCount return 0 // we have reached the end of the street, no further painting necessary int bestCost = infinity if previousColor != 0 bestCost = min(bestCost,minCost(0,houseNum+1) + paintCost(0,houseNum)) if previousColor != 1 bestCost = min(bestCost,minCost(1,houseNum+1) + paintCost(1,houseNum)) if previousColor != 2 bestCost = min(bestCost,minCost(2,houseNum+1) + paintCost(2,houseNum)) return bestCostTo find the minimum cost for painting the entire street, you call the function with houseNum = 0, and previousColor = 1, which allows the first house to be painted any color. While this solution is sufficient given the small constraints, Division 2 coders wanting to take the next step should try learn to memoize the recursive function, or even implement the entire solution as dynamic programming. There is an excellent tutorial on how to make this improvement here. As a challenge, use either of these improvements to get your program solving cases with 50 houses, or 10 colors. ModularInequality Used as: Division Two  Level Three: Used as: Division One  Level Two: This problem, so simple to state, could be approached in a variety of different ways. Your level of insight decided which approach you took, and in turn, how errorprone your solution would be. Browsing solutions, 3 basic approaches are apparent:
Once A is sorted, it is possible to consider each set of possible X values from A[i] to A[i+1]. Since we now know for each value in A whether X>A[j], we can drop the absolutes from f(X) and express f(X) as a linear equation of the form: f(X) = MX + C Knowing the linear equation of f(X) on a section from A[i] to A[i+1], it is possible to calculate where f(X) crosses P (if at all), and calculate the number of X values in that section for which f(X) ≤ P. Offbyone errors and boundary conditions such as duplicate values in A caused this implementation to have a high failure rate. For an excellent and clean example, take a look
 While X lies to the left of the majority of the points in A, f(X) is decreasing.  While X has an equal number of points of A to its left and its right, f(X) is constant and equal to the minimum of f(X).  While X lies to the right of the majority of the points in A, f(X) is increasing. These properties are intuitive when one thinks about the function. As X increases by 1, it moves closer to each point of A that lies to its right, and gets further from each point of A that lies to its left. When X has an equal number of points of A to its left and right, a move to the left or right will move it towards and away from an equal number of points, leaving f(X) unchanged. What this allows us to do is to establish the minimum of f(X), which is at X=A[N/2] (where N is the number of elements in A), because of the 2nd property above. Once we have the X for which f(X) is a minimum, you can split f(X) into 2 halves  one decreasing and the other increasing, and use a simple binary search on each half of f(X) to find the furthest points at which f(X)≤P. If you skip over FenceRepairing Used as: Division One  Level One: Nonstandard points values tend to frighten experienced coders, but there was little cause for alarm on this 300 point problem. The input constraints allowed fences up to 2500 units long, which caused timeouts for careless coders and several members who forgot to give enough space in their storage array. The problem could be solved with either dynamic programming, or careful recursion with memoization, but they both have the same recurrence relation at their heart. The cheapest way to repair the first i boards was the minimum of:  The cheapest way to repair the first i1 boards, if board i was not broken.  The cheapest way to repair the first j boards, plus repairing the section from j+1 to i, inclusive. (For each j from 0 to i1) Psuedocode for the DP implementation: for (i=1;i≤N;i++) c[i]=infinity if board[i]=='.' c[i]=c[i1] for (j=0;j<i;j++) c[i]=min(c[i],c[j]+sqrt(ij)) return c[N]NewMoneySystem Used as: Division One  Level Three: A reasonably easy "hard" problem saw many experienced coders cash in with 900+ scores. Some key insights helped simplify this problem.
Pseudocode follows: long minNotes(long N, int K) if map[N,K] return map[N,K] if K==1 return N long iBest=infinity for (d=2;d≤5;d++) iBest=min(iBest,N%d + minNotes(N/d,K1) map[N,K]=iBest return iBest 
