
Match Editorial 
2004 TopCoder Collegiate Challenge
Qualification Problem Set 3February 2324, 2004
Summary
TopCoder's highest rated member, tomek, competed in this problem set, but ended up a little bit slower than Wernie, who took 1^{st} place by less than 10 points. bmerry was a close 3^{rd}, less than 50 points out of 1^{st} place, and the best new comer was freestyler in 14^{th}.
The Problems
Commission
Used as: Division One  Level One:
Value

250

Submission Rate

123 / 132 (93.18%)

Success Rate

117 / 123 (95.12%)

High Score

haha for 246.43 points (2 mins 44 secs)

Average Score

199.39 (for 117 correct submissions)

This problem was actually inspired by a reallife scenario involving a furniture company. Basically, you want to know how much a cheaper salesman will have to sell in order to for you to make the same profit as you currently do with your expensive salesman. Your current salesman sells $sales goods, cost% of which go to your overhead, and 20% of which go towards his commission. The new salesman works for a lower commission, so he doesn't need to sell quite as much for you to make the same profit. While you could have used some sort of numerical search technique (binary search, for instance), if you work with the terms a bit, there is a relatively simple closed form solutions that most coders found without trouble. First, find out how much profit you currently make: sales*(10.2cost/100). Next, consider that your profit with the new salesman will be x*(1commission/100cost/100), for some x, which represents the return value. Now, you simply need to set these two equations to be equal and do the algebra to get x = sales*(10.2cost/100)/(1commission/100cost/100)
Scale
Used as: Division One  Level Two:
Value

650

Submission Rate

65 / 132 (49.24%)

Success Rate

44 / 65 (67.69%)

High Score

Wernie for 520.08 points (12 mins 0 secs)

Average Score

357.65 (for 44 correct submissions)

Image scaling is a pretty wellstudied algorithm, and there are lots of different ways to do it. The method used in this problem is not very commonly used, as more advanced interpolation techniques are generally preferred.
The algorithm to solve this problem was hinted at in the problem statement. Basically, you first scale the image up so that width of the image is divisible by both the original width and the scaled width. You do the same thing for the height. You could find the least common multiple of the two widths, but that help you in the worst case, so you might as well just use the prduct of the two widths as the width in your scaled up image. Hence, in the problem statement, when we scaled an image from 2x2 to 3x3, we first made a 6x6 image. In the worst case, this will give you an image with 20 million pixels, which is quite manageable, so long as you use only one or two bytes per pixel. Once you have the larger image, you can scale it back down to the required dimensions by dividing up into a number of blocks, each one the same size as the original image. Hence, when we go from 2x2 to 3x3, our blocks are 2x2. If we take the average value of the pixels in a block, and round it, we get the value for one pixel in the return:
char[][] b = new char[image.length*y][image[0].length()*x];
for(int i = 0; i<b.length; i++)for(int j = 0; j<b[0].length; j++)
b[i][j] = image[i/y].charAt(j/x);
String[] ret = new String[y];
Arrays.fill(ret,"");
for(int i = 0; i<y; i++)for(int j = 0; j<x; j++){
double tot = 0;
for(int k = 0; k<image.length; k++)for(int l =0 ; l<image[0].length(); l++){
tot += b[i*image.length+k][j*image[0].length()+l];
}
ret[i] += (char)Math.round(tot/image.length/image[0].length());
}
return ret;
If we needed to, we could solve this without explicitly making the scaled up image. Our loops end up being basically the same, and our runtime is still O(N^4) (where N is the size of the largest dimension), but we use a lot less memory. Basically, we note that when we look up
b[i*image.length+k][j*image[0].length()+l] in the above code, we could instead have looked up the value in the original image simply by dividing the two coordinates by x and y, respectively:
image[(i*image.length+k)/y].charAt((j*image[0].length()+l)/x). We can also improve our runtime significantly if we want to be really clever. Rather than considering a larger, scaled up image, we can calculate exactly which pixels in the original image have an effect on a particular pixel in the new image. Say we are considering pixel (i,j) in the scaled image. That pixel falls in the region from
(i1,j1) to
(i,j) in the scaled image, and if you do out the math, you'll find that it falls in the region
((i1)*width/y,(j1)*height/y) to
(i*width/y,j*height/y), where width and heigh correspond to the original image. Now, we can go to the original image and iterate over all pixels that are at least partly in this region, and calculate how much of each one is in the region. The runtime for this is a little harder to calculate, but it works out to O(N^2), a significant improvement. See mathijs' solution for an implementation of this.
By
lbackstrom
TopCoder Member