
Match Editorial 
SRM 129Tuesday, January 14, 2003
The Problems
Revenue
Used as: DivisionII, Level 1:
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 nonnegative integers. As usual with DivII 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.
Circles
Used as: DivisionII, Level 2:
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 lessthan and greaterthan 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 wraparound 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...
Multiplier
Used as: DivisionII, Level 3:
Value  1050 
Submission Rate  46 / 175 (26.29%) 
Success Rate  24 / 46 (52.17%) 
High Score  Yi Zhang for 963.20 points 
Used as: DivisionI, Level 1:
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.
LeanTo
Used as: DivisionI, Level 2:
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*storageRoofx*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.
StripMine
Used as: DivisionI, Level 3:
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
Revenue
class Revenue {
public:
int bestPrice(int a, int b) {
int best=0,bestp=0;
for(int q=0;q<=a;q++) {
int p=ab*q;
if (p<=0) continue;
if (p*q>best  (p*q==best && p>bestp)) {
best=p*q;
bestp=p;
}
}
return bestp;
}
};
Circles
#include <string>
#include <vector>
using namespace std;
class Circles {
public:
string visit(int start, int finish, vector <int> points) {
string visited="";
while ((startfinish)%360) {
for(int i=0;i<points.size();i++)
if (!((points[i]start)%360))
visited+=char('A'+i);
start++;
}
return visited;
}
};
Multiplier
#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;
}
};
LeanTo
#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*storageRoofx*x);
(x/c<extHt/(c+livingWidth)?lo:hi)=x;
}
char s[10];
sprintf(s,"%0.4lf",x);
return s+(s[0]=='0');
}
};
StripMine
#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 (i1) 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(hj)>3) continue; // Too steep
int v=tbl[i+1][h][kh]+dig[h][i];
best>?=v;
}
tbl[i][j][k]=best;
}
return tbl[0][0][limit];
}
};