Match summary

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

SalaryCalculator

Used as: Division Two - Level One:

Value 250

Submission Rate 447 / 458 (97.60%)

Success Rate 407 / 447 (91.05%)

High Score Mloody2000 for 249.16 points (1 mins 39 secs)

Average Score 226.47 (for 407 correct submissions)

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 200 hours is sufficient, we can simply divide salary by his P1 rate to calculate the hours required.
If he needs to work more than 200 hours, we calculate the salary he needs to earn after the initial 200 hours, and divide that by his P2 rate. Don't forget to add back the 200 hours he's already worked.

if salary ≤ P1 * 200
    return salary / P1
else
    return (salary - P1 * 200) / P2 + 200

RGBStreet

Used as: Division Two - Level Two:

Value 500

Submission Rate 297 / 458 (64.85%)

Success Rate 232 / 297 (78.11%)

High Score dymu for 480.17 points (5 mins 49 secs)

Average Score 361.79 (for 232 correct submissions)

With the largest possible input, there are only 3*2¹⁹ 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 bestCost

To 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:

Value 1000

Submission Rate 118 / 458 (25.76%)

Success Rate 8 / 118 (6.78%)

High Score zhanluwang for 703.91 points (20 mins 18 secs)

Average Score 478.81 (for 8 correct submissions)

Used as: Division One - Level Two:

Value 500

Submission Rate 280 / 403 (69.48%)

Success Rate 114 / 280 (40.71%)

High Score Eryx for 490.95 points (3 mins 52 secs)

Average Score 309.52 (for 114 correct submissions)

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 error-prone your solution would be.

Browsing solutions, 3 basic approaches are apparent:

1. Testing each potential X, calculating the function value, and totalling up the number of Xs for which f(X) ≤ P.

2. Recognizing that f(X) was linear on each section between values of A. Calculate how many values of X led to f(X) ≤ P on each section using basic algebra.

3. Recognizing that f(X) was decreasing and then increasing (unimodal), and that finding a minimum value was trivial. Then using binary search or other simple technique to find the end points for which f(X) ≤ P.

I'll deal with each of these approaches in turn:

1. Testing each potential X

This approach was doomed to fail simply based on the problem constraints. There are up to 2 billion feasible values of X to test, and calculating f(X) that many times will exceed the 2 second time limit.

2. Segmenting f(X) into linear sections

This approach had merit, and many contestants used it. It was reasonably slow to implement and had numerous corner cases and complications which had to be handled with care.

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.

Off-by-one 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 mishagam's solution.

3. Recognizing that f(X) was decreasing and then increasing (unimodal)

This approach was the quickest to implement and the least error prone. It recognized that the function was measuring the total distance in 1-space between X and each point in A. There are some very useful properties of this function:
- 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 Eryx's macros, the heart of his solution does exactly this in about 6 lines of code, very elegantly. For future reference, I can strongly recommend overcoming your fear of Eryx's macros - there's frequently the most beautiful solutions buried under them.

FenceRepairing

Used as: Division One - Level One:

Value 300

Submission Rate 357 / 403 (88.59%)

Success Rate 249 / 357 (69.75%)

High Score ACRush for 297.01 points (2 mins 51 secs)

Average Score 248.83 (for 249 correct submissions)

Non-standard 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 i-1 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 i-1)

Psuedocode for the DP implementation:

for (i=1;i≤N;i++)
    c[i]=infinity
    if board[i]=='.'
        c[i]=c[i-1]
    for (j=0;j<i;j++)
        c[i]=min(c[i],c[j]+sqrt(i-j))

return c[N]

NewMoneySystem

Used as: Division One - Level Three:

Value 1000

Submission Rate 88 / 403 (21.84%)

Success Rate 72 / 88 (81.82%)

High Score tomek for 960.18 points (5 mins 50 secs)

Average Score 682.04 (for 72 correct submissions)

A reasonably easy "hard" problem saw many experienced coders cash in with 900+ scores. Some key insights helped simplify this problem.

1. We should always use the bare minimum of each small denomination. This is easily shown by considering 2 consecutive denominations of value v and a*v. (a must be between 2 and 5, in the problem constraints). Assume that you have x notes of value v, where x≥a. In this case, you could simply exchange a notes of value v for a single note of value a*v, lowering the number of notes.
2. The problem can be broken in sub-problems, each with a lower N and K. The first denomination is always 1. After we have decided on the value of the second denomination, call it d, we immediately know that all other denominations will be multiples of d. Because of the property above we will have exactly N%d notes of value 1. Since we know this, the remaining problem is:
- Allocate N-(N%d) using K-1 denominations, where the smallest denomination is d.
Every denomination hereafter will be a multiple of d, and this allows us to solve an identical problem by dividing all those values by d:
- Allocate N/d using K-1 denominations where the smallest denomination is once again 1.

With these two insights, the problem becomes very simple to implement using a recursive function. We need to take care to implement memoization, because otherwise the number of recursive calls will be 4^K, which will timeout for any significant values of K. Even though the maximum N is 10¹⁸, each recursion reduces N logarithmically - meaning that the state space is small enough to store and memoize. However, the sparseness of the values of N (being spread from 0 to 10¹⁸) means that memoization cannot be done using an array, but must be implemented using a map or hashtable.

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,K-1)
    map[N,K]=iBest
    return iBest

By HiltonLange
TopCoder Member