Match Editorial

The Problems

Value	250
Submission Rate	75 / 175 (42.86%)
Success Rate	58 / 75 (77.33%)
High Score	Yi Zhang for 244.56 points

Reference implementation: see below

Implementation

The hardest part of the problem is maybe to understand the formulas. We want to maximize the product p * q, where p = a - b * q and p and q must both be non-negative integers. As usual with Div-II level 1 problems, it's enough to test all valid values of p and q, calculate the product, and check if it's better than the previous best known result. It's more natural to have q as the loop index, as for every integer q we get an integer p from the given formula. We must also not forget the tiebreaker - if we find that p * q is the same as some previous best result, we should select the highest p.

Value	550
Submission Rate	69 / 175 (39.43%)
Success Rate	37 / 69 (53.62%)
High Score	Karshikinpa for 502.96 points

Reference implementation: see below

Implementation

The easiest way to not screw this one up is to avoid using the less-than and greater-than operators when comparing the points. The only essential check we need is to determine whether two points are equal (i.e. the angles are the same). This is the case if, and only if, the difference between the two angles is a multiple of 360. That is, if the difference modulo 360 is 0.

Having realized that, all we have to do is walk around the circle, increasing the current position with 1 until we've reached the end. After every increase, loop through all points and check if we stand at any of them using the equality check mentioned above. If we find out that we stand at a point, append the name of the point to a list of visited points (an initially empty string). We never have to worry about including the same point several times since we will never walk around the circle more than one revolution.

Most of the failed submissions seems to be related to people adjusting the angles so they are between 0 and 359 inclusive, but then failing the wrap-around during the actual walk. Another pitfall is that doing a simple x % 360 will not work because if x is negative, x % 360 is also negative (or 0). This can be worked around by doing something like ((x % 360) + 360) % 360, but that's a bit ugly...

Value	1050
Submission Rate	46 / 175 (26.29%)
Success Rate	24 / 46 (52.17%)
High Score	Yi Zhang for 963.20 points

Value	300
Submission Rate	75 / 100 (75.00%)
Success Rate	73 / 75 (97.33%)
High Score	ZorbaTHut for 293.33 points

Reference implementation: see below

Implementation

Given an amount, and in what sector the amount is spent, we should determine the total amount of money that is spent again. This is a recursive process, so it's natural to think of a recursive solution. We are assured that the recursion will terminate because not all money are "recycled". The number of recursive calls will not be too many, because for every call at least some money will not be reused, so the complexity is O(N).

If not for the fact that the initial amount should not be counted, the actual implementation could have been a recursive solution in one line, something rarely seen.

Value	600
Submission Rate	37 / 100 (37.00%)
Success Rate	15 / 37 (40.54%)
High Score	Yarin for 569.87 points

Reference implementation: see below

Implementation

This is a geometry problem that can be solved algebraically; however that will include solving some tricky equations requiring more math knowledge than I possess. But the problem statement kindly stated the intended approach: binary search. A lower limit of the height is, of course, 0, and an upper limit is storageRoof. By iteratively selecting the midpoint between the lower and upper limit, finding out whether it's too high or too low, we adjust the endpoints accordingly. We should repeat this process until the precision becomes good enough. A small trick here is to just repeat the process a fixed number of times, say 1000. After that, the range, which was originally at most 30000, is 30000*2^-1000, a very small number.

To determine whether the height is too low or too high, we use Pythagoras formula and the formula for similar triangles:

                         /|  -|
                        / |   |
    storageRoof        /  |   |
               \      /   |   |
                \/\  /    |   |
                /   /|    |   |-----extHt
               /   / |-x  |   |
                \ /__|____|  -|

                  |__||___|
                   |   |
                   y  livingWidth

x is the height that we binary search. In the figure above, the following two formulas are valid:

(1) y = sqrt(storageRoof*storageRoof-x*x)
(2) x/y = extHt/(y+livingWidth)

If x is less than the correct height (there is only one unique answer), the left hand side of (2) will be less than the right hand side. If so, we set the lower limit for the binary search to x, otherwise we change the upper limit.

The answer should then be rounded appropriately. As a C++ coder, this is no problem as sprintf automatically rounds correctly. The only thing you have to watch out for is that if the answer is less than 1, the output should start with the decimal point and not a zero.

Value	950
Submission Rate	17 / 100 (17.00%)
Success Rate	7 / 17 (41.18%)
High Score	Yarin for 750.72 points

Reference implementation: see below

Implementation

The trick here is to realize that to decide the optimal digging depth at a certain column, we are only dependent on three parameters: the current column, the depth we dug at the last column (this sets a valid range for the current column) and how many more squares we may excavate. It's not necessary to know the depth of even more previous columns.

We can define a recursive function based on this, all according to the style explained by radeye in his excellent feature article about functional programming, and then evaluate the function using dynamic programming (caching the results) so it doesn't grow exponential. Given the three parameters, the function should return the maximum amount we can earn by digging this column and the remaining columns under the given constraints.

To evaluate the function, we test all valid digging depths for the current column (and make sure we can excavate this many more squares!) based on the previous column. On the first column and last column, the only valid digging depths is 0 to 3, inclusive, otherwise we loop from the last columns depth - 3 to the last columns depth + 3 (inclusive). For each of these heights, we sum up the earnings of this column (can be precalced for every column) and add with the result of the recursive call that takes care of the remaining columns.

Personally I think it's easiest (fastest!) to implement a recursive solution with caching, which is what I did in the actual contest, but afterwards I often change it to an iterative solution. The only difference is that the iterative solution evaluates the recursive function in the correct order, starting at the "bottom" and going up. An iterative solution is usually both faster and cleaner. The reference implementation below is an iterative solution; for a recursive solution, see my submission in the actual contest.

Reference Implementations

class Revenue {
    public:
    int bestPrice(int a, int b) {
        int best=0,bestp=0;
        for(int q=0;q<=a;q++) {
            int p=a-b*q;
            if (p<=0) continue;
            if (p*q>best || (p*q==best && p>bestp)) {
                best=p*q;
                bestp=p;
            }
        }
        return bestp;
    }
};

#include <string>
#include <vector>

using namespace std;

class Circles {
    public:
    string visit(int start, int finish, vector <int> points) {
        string visited="";
        while ((start-finish)%360) {
            for(int i=0;i<points.size();i++)
                if (!((points[i]-start)%360))
                    visited+=char('A'+i);
            start++;
        }
        return visited;
    }
};

#include <vector>

using namespace std;

class Multiplier {
    public:

    // a>0: this is amount spent on goods

    // a<0: this is amount spent on services (negated)

    int doit(int a, vector <int> &p)
    {
        return a>0?
            a+doit(a*p[0]/100,p)+doit(-a*p[1]/100,p):
            a<0?-a+doit(-a*p[2]/100,p)+doit(a*p[3]/100,p):
            0;
    }

    int spending(int amount, vector <int> percent)
    {
        return doit(amount,percent)-amount;
    }
};

#include <cmath>
#include <string>

using namespace std;

class LeanTo {
    public:
    string height(int extHt, int livingWidth, int storageRoof) {
        double lo=0.0,hi=storageRoof,c,x;
        for(int i=0;i<1000;i++) {
            x=(lo+hi)/2.0;
            c=sqrt(storageRoof*storageRoof-x*x);
            (x/c<extHt/(c+livingWidth)?lo:hi)=x;
        }
        char s[10];
        sprintf(s,"%0.4lf",x);
        return s+(s[0]=='0');
    }
};

#include <string>
#include <vector>

using namespace std;

class StripMine {
    public:
    int maxProfit(int limit, vector <string> report) {
        int depth=report.size(),width=report[0].size();

        // First calculate the profit of digging a

        // certain depth at a certain column

        int dig[depth+1][width];
        for(int i=0;i<width;i++) {
            dig[0][i]=0;
            for(int j=0;j<depth;j++)
                dig[j+1][i]=dig[j][i]+int(report[j][i]-'A')-3;
        }

        // Then calculate the max profit using induction over the remaining

        // columns, the height of the next column and the number of more

        // squares we can excavate
        int tbl[width+1][depth+1][limit+1];

        for(int i=width;i>=0;i--)
            for(int j=0;j<=depth;j++)
                for(int k=0;k<=limit;k++) {
                    // Last column (i-1) was at depth j and

                    // we have k more squares to excavate

                    if (i==width) {
                        tbl[i][j][k]=j>3?-1000000:0;
                        continue;
                    }
                    int best=-1000000;                    
                    for(int h=0;h<=depth;h++) {
                        // Dig at height h in this column
                        if (h>k) break; 
// Can't dig this much

                        if (abs(h-j)>3) continue; // Too steep

                        int v=tbl[i+1][h][k-h]+dig[h][i];
                        best>?=v;
                    }
                    tbl[i][j][k]=best;
                }
        return tbl[0][0][limit];
    }
};