Match Editorial

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

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 real-life 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*(1-0.2-cost/100). Next, consider that your profit with the new salesman will be x*(1-commission/100-cost/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*(1-0.2-cost/100)/(1-commission/100-cost/100)

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 well-studied 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;