Member Search 
Tuesday, May 6, 2003 Match summary Last night's problems were a good mix, with some dynamic programming, some simulation, and a couple relatively straightforward number problems. The set seemed to be pretty wellbalanced also. Despite a rather wordy div 1 medium /div 2 hard problem, the submission percentages were all pretty well in line with the averages. SnapDragon and Yarin were neck and neck during the challenge phase, and Yarin could have won the round if he had gotten one more challenge. But, in the end SnapDragon was able to hold on for the win, thanks to Yarin's resubmission of the 600 point problem. In division 2, shadowless was able to narrowly edge out first timer andlehay for the win. The ProblemsDitherCounterUsed as: DivisionII, Level 1:
ImplementationDespite all of its fancy talk about bitmaps and dithering, this problem really has very little to do with any of that. To solve it, you simply have to go through each character in the given String[] (vector<string>) and see if that character is in dithered. Count how many such characters exist, and return that number. Exercise MachineUsed as: DivisionII, Level 2:
ImplementationThis problem seems a little bit nonsensical at first glance. After all, what sort of exercise machine would be programmed in the manner described. However, the writer assured me that he has seen exercise machines that have wacky behavior along these lines. So, to solve this, you can loop over either seconds, or over percentages. Either way, you can get one from the other, and then determine if they are both exact or not. Here is how you would do it if looping over percentages, if s is the total number of seconds that the workout lasts: int ret = 0; for(int i = 1; i<100; i++){ if((s*i)%100==0)ret++; }It also turns out that the answer is always gcd(s,100)1. This is a lot harder to come up with, but much easier to code. I'll leave the proof as an exercise to the reader. As a hint of where to start, consider the case where gcd(s,100) = 2. In this case, the only number the display shows is 50%. Once you see this, it isn't too hard to work up to the general case. VendingMachine Used as: DivisionII, Level 3: Used as: DivisionI, Level 2:
Implementation
Despite the length of this problem, it is actually relatively simple to code. Basically, you just have to follow all of the instructions to the letter,
and you will be fine. Used as: DivisionI, Level 1:
ImplementationUnderstanding how the division operator works is key to many problems, both in TopCoder and the realworld. In this problem we want to first find the percentage of the total point that each person has  truncated down to the nearest percentage. An easy way to do this after you've calculated the total number of points is percent[i] = (100 * points[i])/totalPoints. Then, you add up all the percentages, and find the number of percentage points that are left over, 100  totalPercentage. Since the number of percentage points left over is relatively small, you can loop over them all and assign them one at a time, keeping track of who has already got one. One thing to note is that there will never be more percentage points left over than there are people. This is because when you truncate, you are removing less than one percentage point from each person. So, the total number of percentage points must be less than the number of people. HillHikeUsed as: DivisionI, Level 3:
Implementation
This is a good dynamic programming problem, and can be solved with either a number of nested loops, or with memoized recursion. As with all DP problems,
the trick is to come up with the correct recurrence. After that, it is relatively straightforward. So, the recursion:
Now, the question is how to evaluate f(h,d,lm,max). Clearly, since the path goes strictly from lower horizontal distances to higher ones, f(h,d,lm,max) depends only on f(*,d1,*,*), where *'s can represent any value. Also, since you can only move up one, down one, or stay at the same level, f(h,d,lm,max) = f(h1,d1,*,*) + f(h,d1,*,*) + f(h+1,d1,*,*). Now, there are two cases when considering whether or not the maximum height has been reached. If the height being considered, h, is the maximum height, then we have something like f(h,d,lm,true) = f(h1,d1,*,true) + f(h1,d1,*,false) + f(h,d1,*,true), and f(h,d,lm,false) = 0. Otherwise, if h is not the maximum height, then f(h,d,lm,max) = f(h1,d1,*,max) + f(h,d1,*,max) + f(h+1,d1,*,max), for max either true or false. Now, for the hard part: what to do about the landmarks. First we must observe that we should always assume that a landmark occurs as early as possible along a path. In other words, if considering whether or not a path is valid, a greedy approach to placing landmarks is always best. This means that, if we have placed lm landmarks, and the next landmark to be placed is at height h, then we can assume that the landmark was placed there, and move on to the next landmark. This allows us to finish our recurrence, with 4 cases:
Now, armed with this recurrence, we can implement it something like this (thanks to schveiguy for his pretty code). Note that while it is somewhat hidden, this code actually does implement the above recurrence: typedef long long int64; struct HillHike { int64 numPaths(int distance, int maxHeight, vector<int> landmarks) { int64 cache1[2][52][51]; int64 cache2[2][52][51]; memset(cache1, 0, sizeof(cache1)); cache1[0][0][0] = 1; landmarks.push_back(1); for(int i = 1; i < distance; i++){ memset(cache2, 0, sizeof(cache1)); for(int j = 1; j <= maxHeight; j++){ int ni = (j == maxHeight ? 1 : 0); for(int k = 0; k < landmarks.size(); k++) for(int d = 1; d <= 1; d++){ int lm = (j == landmarks[k] ? k + 1 : k); cache2[ni][j][lm] += cache1[0][j + d][k]; cache2[1][j][lm] += cache1[1][j + d][k]; } } memcpy(cache1, cache2, sizeof(cache1)); } return cache1[1][1][landmarks.size()1]; } }; 
