This match seemed a bit harder than usual. The 275 points problem was definitely a more complicated dynamic programming than is usual for the easy slot. It was good though.
Div1 easy: For 275 the one about stamps
There are cells indexed from 0 to n-1. Some (or all) cells have a requirement to be colored red, green or blue. In order to color the cells. First pick a stamp length L, with a cost of stampCost*L. Then paint contiguous group of L cells using that stamp with the same color. Each time you push the stamp, it costs pushCost. You cannot use two or more different colors to paint the same cell. What is the minimum cost? The maximum value of n is 50. The cost values are at most 100000.
Things to consider: First of all, there is always a result. You can always pick L=1. Then the cost is: stampCost + n*pushCost. This also allows us to confirm that the result always fits a 32 bits integer.
Another thing, the maximum useful value of L is 50. With at most 50 possible values of L to try, we can just iterate through each of them, find if it is possible to use that length and then calculate the minimum cost if that stamp length was used. Return the minimum cost you find.
Now let us solve the sub-problem when L is fixed. First add L*stampCost. Let us find the minimum number of pushes. Imagine that we have already decided how to color each of the cells that do not have a color requirement. What is the cost to make that pattern? This all depends on each group of contiguous cells of the same color. For example, to paint RRGGBBBBBRGBRRR, consider each group of contiguous cells of each color: RR, GG, BBBBB, ... etc. What is the minimum number of pushes for each of these groups? Note that when L is greater than the length of one of the groups, this is not possible. Then we imagine L=2 and RRRR, of course, we can just use two pushes. That is len / L. But what if the contiguous length is not a multiple of L? For RRRRR and L=2, you would need to do three stamps, and color one of the cells twice. You will verify that the result in case of len not being a multiple of L is always len/L rounded.
But how can we choose the colors for the cells that can have any color? There might be a way that does not involve dynamic programming. But I can only prove the dynamic programming approach to be correct. Have a function f(p, lastColor, lastLength) that finds the minimum cost of painting cells above index p given that the last color we painted is (lastColor) and the current length of contiguous cells of that color is lastLength. In each step, you can decide one of the three colors. Altering lastColor and lastLength if necessary.
Implementing was not easy as it is not your easiest dp to code. It was also 7:00 AM. I am not that good at 7:00 AM. So I took some long time debugging my solution.
I was lucky though, during the challenge phase I expected there to be failed solutions. I opened the solution of the blue coder that had the most score. And it seemed strange. I think the approach itself might be correct, but it was not doing memoization or anything to avoid recursing too much. It was a time out case. There were large example cases, but I think some of the aspects of this solution were cutting the execution time in those cases. But a string of n * characters was too much. I was very lucky to find a solution that timed out.
Code:
const int INF = numeric_limits<int>::max();
struct Stamp
{
string desiredColor;
int pushCost, L;
int dp[51][4][51];
// When iterating through colors we go from 0 to 2, but then we got to
// do some input translation...
int toColorId(char ch)
{
switch(ch) {
case 'R': return 0;
case 'G': return 1;
case 'B': return 2;
}
return 3;
}
// What is the minimum cost to paint a group of length contiguous cells?
int getCost(int length)
{
if ( (length < L) && (length > 0) ) {
return INF;
} else {
return pushCost * ( (length / L) + (length % L != 0) );
}
}
int rec(int p, int last, int lastLength)
{
int &res = dp[p][last][lastLength];
if (res == -1) {
res = INF;
if (p == desiredColor.size()) {
// base case, all cells were painted, calculate the last cost
res = getCost( lastLength );
} else {
// pick one color, that matches desiredColor[p]
// remember the best result we find.
for (int c=0; c<3; c++) {
int r = toColorId(desiredColor[p]);
if ( (r == 3 ) || (r == c)) {
if (c == last) {
//continue this sequence.
res = std::min(res, rec(p+1, c, lastLength + 1) );
} else {
//do the change
int x = rec(p+1, c, 1);
int y = getCost(lastLength);
// careful with overflows.
if ( (x < INF) && (y < INF) && (x < INF - y) ) {
res = std::min(res, x + y);
}
}
}
}
}
}
return res;
}
int getMinimumCost(string desiredColor, int stampCost, int pushCost)
{
// Save some variables:
this->desiredColor = desiredColor;
this->pushCost = pushCost;
int n = desiredColor.size();
// Try each possible value of L. Remember the best result:
int minCost = INF;
for (int L=1; L<=n; L++) {
//reset the dp.
memset(dp, -1, sizeof(dp));
this->L = L;
// call the dp.
int x = rec(0,3,0);
int y = stampCost * L;
if (x < INF) {
minCost = std::min(minCost, x + y );
}
}
return minCost;
}
};
Funny thing, while adding comments to that code, I figured that there is a dp that is a bit easier. You just need a recurrence f(t), the minimum cost to color the first t cells. Then pick a group of the last x contiguous cells. If they are all * or the same color, then call getCost(x) and then recurse to f(t - x).
Div1 550: The one with triangles
A complicated one. O(n^3) should be fine. I think the key is to first pick the pair (P,Q), from there you can calculate (using slopes) the allowed red points. Then you have to count the number of ways to pick red points following a large inequality. I think it is possible. But when I noticed I had nothing and there were only 4 minutes left, I preffered to double check the 275 and try to think of ways to find mistakes in it.
No comments :
Post a Comment