Tuesday, October 30, 2012

SRM 559: Just wow

This one was tough. I know ad hoc 250s are great. And I love them. I also liked this problem a lot. But it felt way too much for 250.

The good thing is that I managed to mostly avoid an ad hoc solution. Instead, mine relies on inclusion-exclusion magic.

Div1 "Easy": The one with knights

You have a (possibly large) chess board. Your knight can move from cell (x,y) to cells (x+a,y+b), (x+a,y-b), (x-a,y+b), (x-a,y-b), (x+b,y+a), (x+b,y-a), (x-b,y+a) and (x-b,y-a). If the cell does not exist, the move is invalid. Return the total number of cells from which there are exactly k moves. The values are from 1 to 109. a and b are never the same. Also, 2*max(a,b) is always less than min(number of columns, number of rows).

That last constraint was something very suspicious. I guessed that this constraint reduces the number of corner cases. When the people behind these contests reduce the number of corner cases, it can only mean that the problem is very complicated...

And it was. At first I thought to just solve the problem. There are 9 special cases. Some are easy It is impossible to have cells with (k=0, k=1, K=5, k=7) valid moves (In realty, k=0 and k=1 should be possible if not for the suspicious constraint). It is not completely obvious, but K=3 is possible. I thought that this was going to be a corner case, but nope.

Eventually, I returned to my senses and figured that finding a formula for each of the 4 remaining cases would have been crazy and bug-prone. There got to be a better way. Good thing I could think of it. But the time I wasted trying to think of the formulas and then debugging the solution (which turned out to be very long) gave me a very low score and no time to solve the medium-difficulty problem.

Here is the solution anyway: Let us define a move as (dx,dy) so that you move from cell (x,y) to (x+dx, y+dy). It is simple to know the number of cells in which this move is valid. There are 2*dx invalid rows and 2*dy invalid columns. So just multiply the number of remaining rows and columns and find the result.

Let us count the number of cells from which two specific moves (dx1, dy1) and (dx2, dy2) are valid. (And possibly other moves). This is a bit harder. But indeed, you can find the rectangle of cells from which these moves (but not necessarily only these moves) are valid.

For any subset of the 8 available moves, the number of cells from which all of the moves in the subset are valid are also a rectangle, and thus we can calculate this value for each subset of moves. Let us use bit masks to represent these sets. Now let us store the results in an array valid[mask] that for each mask (subset of moves) returns the total number of cells in which all of the moves in the bit mask are valid).

Now, if we wanted to find the total number of cells from which exactly k moves are valid. We would just need to find all subsets that have exactly k and sum their valid[mask]. Right?... NO!. You have not been paying attention. Because valid[mask] may include cells from which other moves are valid.

Thus what we want to somehow create is another array called exactly[mask] that gives us the number of cells from which the only moves allowed are those in the bit mask.

The key

The key is to observe that valid[255] = exactly[255]. In other words, since there are only 8 moves. Then all the cells valid[255] are also the cells from which the only valid moves are the 8 ones (note that 255 is the subset that contains all 8 moves).

And that is cool. Because we can now calculate the results of exactly[mask] for all masks that have exactly 7 bits. Yeah! Imagine a subset of moves that lacks exactly one moves in that case, valid[mask] will return all the cells that allow those 7 moves. This includes all the cells that allow the 8 moves AND the cells that allow only the 7 moves. We can find exactly[mask] with a simple subtraction.

In fact, for every bit mask mask. exactly[mask] is equal to valid[mask] minus sum(exactly[mask2]) for each mask2 of which mask1 is a proper subset of. You can build exactly[] using this method. Then sum all the values of exactly[mask] for all masks that have exactly k elements (1 bits).

Solution

typedef long long int64; 
#define long int64

struct HyperKnight
{
long countCells(int a, int b, int numRows, int numColumns, int k)
{
// The 8 moves:
long dx[8] = {a,a,-a,-a,b,b,-b,-b};
long dy[8] = {b,-b,b,-b,a,-a,a,-a};

long exactly[256];
long result = 0;

// We visit the masks from highest to smallest, this way we
// can guarantee that all subsets with more elements than the
// current one have already been solved.
for (int mask = 255; mask >= 0; mask--) {
long valid = 0;
// valid : How many cells allow the moves in mask?
// (and possibly other moves)

// In the explanation valid is an array, but we do not really
// need to remember all its values, just valid[mask].

int n = 0;
// Find the rectangle of such cells:
long left = 0, right = 0, up = 0, down = 0;
for (int i=0; i<8; i++) {
// For each move that belongs to the mask subset:
if (mask & (1<<i)) {
n++;
// update the rectangle's dimensions
if (dx[i] < 0) {
left = std::max(left, -dx[i]);
} else {
right = std::max(right, dx[i]);
}
if (dy[i] < 0) {
up = std::max(up, -dy[i]);
} else {
down = std::max(down, dy[i]);
}
}

}
// Area of the rectangle
valid = (numRows - left - right) * (numColumns - up - down);
// if we make sure to set valid = 0 when the moves are too large
// this makes the solution work even without the special constraint

exactly[mask] = valid;

// For each subset with more elements than this one.
// (mask must be a proper subset of mask2):
for (int mask2 = mask + 1; mask2 < 256; mask2++) {
if ( (mask & mask2) == mask ) {
// remove the cells that allow more moves than mask.
exactly[mask] -= exactly[mask2];
}
}
// n is the number of moves in the mask.
// now exactly[mask] contains the number of cells from which the ONLY
// valid moves are those in the mask:
if (n == k) {
result += exactly[mask];
}
}
return result;
}
};
#undef long

Div1 medium

By the time I finished my 250, I did not really have much time to try to code a solution. But I think it is easy to just fix the root and the depth of the tree. Then count the number of ways to have those given root and depth following the conditions. This root shall have one or two children. One child should have exactly (depth-1) depth and be full. The other can have (depth) depth and not be full (but to the right). These are all similar subproblems. Implementation is probably messy.

Opinions / etc?

I liked the match, I just wish I solved 250 faster. What about you?

Friday, October 19, 2012

SRM 558: Tough

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.

Thursday, October 18, 2012

Yesterday's Test SRM

It seems clear to me that the admins have a system that can generate random SRM problem sets for unrated SRMs. I wish this could become a system that organizes daily test SRMs at stock schedules. I think that once the idea catches on we could expect around 50 to 100 coders in each "practice SRM".

They would be a bit better than allowing virtual contests in that you still do not know exactly what problems to expect. If you play along and avoid cheating (yourself). They are great practice for real SRMs. Since they will have room assignments of their own, then we can even have a challenge phase. Since I played along and avoided loading old code, yesterday's test SRM felt a lot like a real SRM (with a very bad problem (see bellow), but still)

Div1 Easy: Hotel (SRM 357)

Link to problem statement

KawigiEdit would tell me I already solved this problem and asked me to load a file. I of course said no. It did not matter though, since it was a generic dynamic programming problem so having solved it in the past was not really a big advantage (all of these problems tend to be a blur in your memory of solving problems).

There are n cities (at most 20). For each city i, cost[i] is the cost to get customers[i] from that city. You can get any multiple of cost[i] customers from city i. What is the minimum cost you need to pay to get at least minCustomers customers in total? This means that you do not need to get exactly minCustomers but any value of customers greater than or equal to that. (In fact, it may be possible that it is cheaper to get an amount of customers greater than minCustomers than it is to get exactly minCustomers).

Fear not. Let us name a function f(k, t) that gives the minimum cost to get at least k customers using only the t first cities. (The answer to the real problem is f(minCustomers, n).

For a base case, what happens when t=0? This means that there are no cities from which we can get any customer. A value of k greater than 0 is impossible. (Since we are minimizing, let us put a fake large value as the result - infinity). If k=0, then the minimum cost is 0. In fact, whenever k=0, the minimum cost is 0.

Let us now assume t > 0. Then there is at least one city. Let us take city (t-1). We can decide how many times we get customers from this city. Let us say we choose j for the number of times. Then we will get j * customers[t-1] customers with a cost of j * cost[i]. Then we can make decisions for the remaining cities (decrement t). The necessary number of customers, k is reduced by j * customers[t-1]. Thus the minimum cost (if choosing j) is: f(k - j * customers[t-1], t - 1) + j*cost[t-1]. Note that the new value of k might be negative, in that case we have more customers than needed, but that is really the same as if we had k=0 (We no longer need any more customers). We can just iterate through all the possible values of j and find the minimum cost possible.

That recurrence relation can be memoized or turned into iterative dynamic programming. Like this:

int marketCost(int minCustomers, vector <int> customers, vector <int> cost)
{
    const int INF = 10000000;
    int n = customers.size();
    int dp[1001][21];
    
    for (int t=0; t<=n; t++) {
        dp[0][t] = 0;
        for (int k=1; k<=minCustomers; k++) {
            dp[k][t] = INF;
            if (t > 0) { //The base case is when t=0, else we iterate for j
                // The valid values of j are 0, 1, ... and up to the first
                // value of j that causes k - customers[t-1]*(j-1) to be
                // negative or 0
                for (int j=0; k - customers[t-1]*(j-1) <= k; j++) {
                    // If the new k is less than 0, set it to 0.
                    int nk = std::max(0, c - j*customers[t-1]);
                    // remember the minimum
                    dp[k][t] = std::min(dp[k][t], dp[nk][t-1] + j*cost[t-1]);
                }
            }
        }
    }
    // final result!
    return dp[minCustomers][n];
}

Div1 medium: RPGRobot (SRM 201)

Link to statement

Err. I usually try to sum up the problem statement in a quick paragraph. The reason is that Topcoder has the draconic idea to only let registered users read their problem statements. But in this case, I have no choice but to ask people to read that problem statement. It is way too long and complicated for me to reproduce quickly.

I did not solve this problem before. That is not an issue though, because this problem was more about implementation and parsing the problem statement and the input.

I actually found hilarious and funny that old timmey problem writers thought that defining a grammar was clearer than explaining the input. Or that a problem that needed these explanations was a good idea.

Anyway... Since the coordiantes that we can return are at most 24x24 = 576. And the number of moves is at most 16 (Try it). Then we can use simple simulation. For each of the coordinates inside the map, simulate all the moves and verify that the story checks out. For each position, get the list of allowed directions, and compare it with the provided list of allowed directions. Any inconsistency means the starting position was not valid.

But what will happen to you after implementing that idea, is that you will fail many of the 9001 example cases. What is going on? You probably missed a couple of traps from the statement.

First of all, the robot can actually go outside of the map. That is no big deal. Except that the walls outside the map are unknown - They could be anything we need them to be. In effect, when a wall position is outside the map, then it can be counted as a wall if the list of directions provided by the robot says so and also the opposite, if the list of directions provided says there is no wall, we can consider there not to be a wall either.

Many ways to deal with this little issue. The best approach is to simply ignore a direction if the direction's wall position is outside the map. Also note that the problem statement clarifies that the moves will be self-consistent. That is very important, because that means that we do not need to do any extra work outside the map, just simulate the movement.

Many implementation issues regarding how to simulate the movement around the map. Use your usual array of direction vectors, but check against (x + dx[i], y + dy[i]) for the walls but move to (x + 2*dx[i], y + 2*dy[i]) for the position. You will need to know how to parse stuff in your language too...

struct RPGRobot
{
    // We will encode each entry of the movements string in this string.
    // Note that the first "move" is really only the info of allowed directions.
    struct move
    {
        char movedTo;
        string allowed;
    };
    vector<move> moves;
    
    // Returns the state of the wall at a given position.
    // If the wall is outside the map, the status is unknown: '?'.
    // If there is no wall, the direction is allowed: 'Y'
    // Else we cannot move: 'N'.
    char couldIt(const vector<string> map, int x, int y) {
        if ( x >= map[0].size() || y >= map.size() || x < 0 || y < 0) {
            return '?';
        } else {
            return ( (map[y][x] == ' ') ? 'Y' : 'N' );
        }
    }
   
    bool sim(vector<string> & map, int x, int y)
    {
        /* The simulation... */
        // Direction vectors
        const int dx[4] = {0,0,-1,1};
        const int dy[4] = {-1,1,0,0};
        // name each direction...
        const char* dn = "NSWE";
        
        // Remember what each direction name means...
        int did[256];
        for (int i=0; i<4; i++) {
            did[dn[i]] = i;
        }

        for (int i=0; i<moves.size(); i++) {
            if (i != 0) { // perform move (No move is performed in the first entry)
                int d = did[ moves[i].movedTo];

                // move two coordinates towards that direction
                x += dx[d] * 2;
                y += dy[d] * 2;
            }
            // Check if the allowed directions from this position are consistent
            // with the input provided:
            for (int d=0; d<4; d++) {
                // the wall is only one coordinate towards the direction
                int nx = x + dx[d];
                int ny = y + dy[d];
                // couldIt returns the state of the wall, right?
                char c = (couldIt(map, nx, ny));
                if (c != '?') { //ignore if the state of the wall is unknown
                    // should this direction be allowed? Or not?
                    bool should = false;
                    for (int k=0; k<moves[i].allowed.size(); k++) {
                        should |= (moves[i].allowed[k] == dn[d]);
                    }
                    // Consistent?
                    if ( should != (c=='Y') ) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    
    // Turn that movements string into a vector of structs...
    void parseMoves(string& movements)
    {
        // No easy way to split by commas in c++, we will have to do it manually
        int last = 0;
        for (int i=0; i <= movements.size(); i++) {
            if ( (i==movements.size()) || (movements[i] == ',') ) {
                string x = movements.substr(last, i - last);
                move tm;
                if (last == 0) {
                    tm.movedTo = '-';
                    tm.allowed = x;
                } else {
                    // istringstream is good at spliting by spaces.
                    istringstream st( x) ;
                    st >> tm.movedTo >> tm.allowed;
                }
                moves.push_back(tm);
                last = i+1;
            }
        }
    }


};

Div1 Hard: RadarGuns (SRM 372)

I remembered this problem too well. I skipped it. It was the problem in which I first tried to do min-cost matching. There are issues with the practice rooms, so I will not say anything else.

Actually, we have editorials for these problems, you know.

The random number gods were evil this time, because the combination of the super implementation medium plus the hard that can be solved by pasting min-cost-flow code is not a great one.