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.