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.

Read More

TopCoder SRM 557: GreatFairyWar and IncubatorEasy

SRM 557

Explanation for division 1 Easy and match recap. Explanation for div2 easy and div2 medium.

Div2 Easy: GreatFairyWar (250 points)

Link to problem statement

You have way too large hp. You are battling against N fairies, indexed from 0 to N-1 which you must kill in the given order (First kill 0, then 1, ...). The i-th fairy has hp[i] hit points and will do dmg[i] damage per second while she is alive (meaning that in each second, the fairy will remove dmg[i] from your hit points). Your damage per second is 1, which means that in each second you reduce 1 hp from the fairy you are currently killing. What is the total number of hit points you will lose before the last fairy finally dies?.

Let us try with fairy 0: fairy 0 has hp[0] hitpoints, and you can only reduce one per second, which means that you need hp[0] seconds before the fairy dies.

During each of those hp[0] seconds, all the fairies will use their attacks on you. If each fairy attacks you, the total damage you will receive each second is equal to the sum of all the dps[i]. This happens during hp[0] seconds, so while fairy 0 is alive, you will receive a total of hp[0] * (sum of all dps[i]) damage.

After fairy 0 dies, there are only fairies 1 to n-1 left. The logic shall be the same: Fairy 1 will be alive for hp[1] seconds. During each of those seconds you will receive attacks from each fairy (except fairy 0), totaling to (sum of (dps[1], dps[2], ... dps[n-1]). The total damage you will receive while killing fairy 1 is: hp[1] * (sum of all dps[i] minus dps[0].

Repeat and you shall see, for each fairy i add hp[i]*(sum of dps[j] starting with j=i). This can be easily implemented with two for loops - one nested inside of another.

How about we simplify the code a bit, it is not necessary, but it makes the code look more awesome. If we did the main loop in reverse, and first calculated the damage done to you while killing fairy n-1, then fairy n-2, and so and so until fairy 0, we can then calculate the appropriate sum by using the sum used in the previous step. Something like this:.

The low constraints on the number of fairies (at most 30) was probably there to avoid overflow bugs.

int minHP(vector <int> dps, vector <int> hp) 
{ 
    int sum = 0, lose = 0; 
    // For each fairy i (go in reverse). 
    for (int i= hp.size() - 1; i >= 0; i--) { 
        // Calculate the sum of dps from j=i to j=n-1: 
        // just add dps[i] to the sum from j=i+1 to j=n-1: 
         
        sum += dps[i]; 
         
        // The damage inflicted while killing fairy i is : 
        lose += hp[i] * sum; 
    } 
    // And done! 
    return lose; 
} 

Div2 Medium: IncubatorEasy (550 points)

Link to problem statement

We got a group of at most girls. Some girls love other girls and/or themselves. Love is not necessarily symmetric. You have the ability to give any girls a magical super power (Turn the girl magical) any time you want. Once a girl is magical she will cast a protection spell on all the girls she loves. Also, whenever a girl receives a protection spell, she will also cast the protection spell on all the girls she loves. Thus when you set a girl magical, you may create a chain reaction of many girls casting protection on many other girls and so and so (it is even possible that the girl you made magical ends up protected after all of this).

The objective is to maximize the number of girls that are magical but not protected.

In effect, the objective of the game is to select the sub-set of girls that you will make magical. Then simulate all the process, all girls that are magical or protected cast the spell on the girls they love. Until there are no changes possible. Finally, count the number of girls that are magical but not protected. Return the maximum number you find.

That is most likely the intended approach. The number of girls has a small limit (10). There are going to be at most 2¹⁰ sub-sets of girls you can pick. So, as long as you do the simulation part fast enough, the execution time should not be a problem.

Simulate this

The simulation part. Here is both a proof to show that it can be done in O(n^3) and also a suggestion to simplify the code a bit. How about we ask ourselves (If this girl was made magical or protected, what is the resulting set of girls that will eventually becomes protected because of this?). If girl i is made magical or protected these are the girls that will become protected because of that:

• Girls loved by girl i.
• Girls loved by girls loved by girl i.
• Girls loved by girls loved by girls loved by girl i.

An easier way to see this is that, girls that are loved by girls that are loved by i, are actually indirectly or (much better) transitively loved by girl i. What we have to do here is turn the [love] relation into a transitive relation. By that , we will have to make the transitive closure.. In effect, we will turn the love matrix, into a matrix that gives, for each i, a list of girls that are loved directly or indirectly by i. The list of girls that will eventually become protected if girl i becomes magical or protected.

In order to make the transitive closure, we can use the very easy Floyd-Warshall algorithm. It works like this: For each girl k, find pairs (i,j). If girl k can act as a love intermediary between i and j, then i and j become connected. See more details at the code section of the wikipedia article or at the code at the end of this post.

Bruteforce this

A important thing to mention is how to use brute force to find all 2ⁿ sets of girls to make magical. You could use backtracking., but to be honest, in programming contests, we do not use that to generate all sub-sets. Instead, we use bitmasks!. It is the power of binary numbers! Read this tutorial by bmerry for more info.

Code

So much to mention. Note how the complexity is: O(n³ + 2ⁿ*n²). For n=10, this is actually pretty fast.

int maxMagicalGirls(vector <string> love) 
{ 
    // Let us use Floyd-Warshall to turn the love[][] matrix 
    // into its transitive closure: 
    int n = love.size(); 
    for (int k=0; k<n; k++) { 
        for (int i=0; i<n; i++) { 
            for (int j=0; j<n; j++) { 
                if ( love[i][k]=='Y' && love[k][j]=='Y' ) { 
                    love[i][j] = 'Y'; 
                } 
            } 
        } 
    } 
    // now love[i][j] is 'Y' if making i protected or magical 
    // will imply that j becomes protected. 
    int best = 0; 
    // Use the bitmask called mask, to generate all subsets 
    // of the n girls: 
    for (int mask=0; mask<(1<<n); mask++) { 
        int protMask = 0; 
        // For each girl: 
        for (int i=0; i<n; i++) { 
            if ( mask & (1<<i)) { // If she belongs to the subset 
                // Find all the girls that (according to the transitive closure) 
                //  will become protected because of i. 
                for (int j=0; j<n; j++) { 
                    if ( love[i][j]=='Y' ) { 
                        // Then add the girl to the protected subset. 
                        protMask |= (1 << j); 
                    } 
                } 
            } 
        } 
        // We got a set of magical girls, and the set of girls that become 
        //  protected after that. Who are the girls that are magical but  
        //  not protected? Just the subtraction between the two sets. 
        //  or the intersection between magical and the complement of protected 
        int sub = (mask &~ protMask); 
        // __builtin_popcount(sub) returns the number of 1 bits (elements) 
        //  so that is the number of girls that are magical and not protected 
        best = std::max( best, __builtin_popcount(sub) ); 
        // remember the best. 
    } 
    return best; 
} 

More to come.

I pretend to do div2 hard and div1 medium later. Perhaps If I am VERY motivated will do div1 hard as well.

Comments, corrections, rants, criticisms, etc

Feel free to comment, really.

Read More

Test SRM the 16th

http://apps.topcoder.com/forums/?module=Thread&threadID=764869&start=0

After a successful Test SRM on September 25, we are planning to have another one on next Tuesday (October 16th), at 11:00 EDT. It will be followed by a Test MM that starts next Wednesday (October 17th) at 13:00 EDT and lasts for 1 week.

For Test SRM, we again will reuse random problems from the period of SRM 200 -- SRM 400. We will either override the standard applet or I'll post connection link here later.

For Test MM, we will reuse the problem PolygonEstimation from the recent TCO'12 Championship Round. It will either use standard website interface or I'll post participation details here later.

Both rounds are not rated.

Let us fill this one up. It is much better to participate in an actual contest environment than to practice random problems in the arena. Even if you have seen the problems before, funny things happen and you might find them hard or interesting to solve again (has happened...).

Also, note that in the case of PolygonEstimation, it might actually be a interesting match. There is always room for improvement on the algorithms that the top places were using.

Read More

TopCoder SRM 557 - finally

SRM 557

Explanation for division 1 Easy and match recap. Explanations for div2 easy and div2 medium.

It feels like it has been ages since the last SRM. Here we go again.

It began with a bang. The 250 points problem reminds me a bit of a problem I wrote in the past, but I cannot remember its name. Something with black and white squares. They are very different problems, but I do remember that that problem was very tricky. This 250 points problem had like 8 examples, so I sort of felt it was going to have tricky written all over it. And decided to be careful rather than fast.

Div1 250: FoxAndMountainEasy

So, you start at height h0, is there is a sequence of n up and down moves such that:

• Each up move increases height by 1
• Each down move decreases height by 1. It is invalid to go bellow height 0.
• The given string history is a substring of the sequence of moves.
• The height after all of that stuff is hn

n is at most 100000. This problem gave me the feeling that it was initially intended for the TCO finals, but later they adapted it to SRM difficulty by reducing the constraints and adding plenty of examples.

The solution goes as follows: First process the history substring. After executing this series of moves, how much will be the netChange of the current height? (This is just equal to (number of Us) - (number of Ds). So if your current height is b before starting the sub-sequence of moves, the height after doing so will be b+netChange.

There is a catch though, if there are many D characters in the history sequence and not preceded by enough U characters, then the starting height before running the sequence, b, cannot be too small. b has to be large enough such that the current height while executing the subsequence is never bellow 0. (This can be calculated with a simple for loop - just simulate the movement starting at height 0, and remember the lowest height, if this lowest height is negative, then -lowest height is the minimum height value for b). We will call this required height before the subsequence - minStart.

After you have two things: netChange and minStart. We just need to do some extra things. There are (n - size(history)) moves left that we have to pick. Now here is the thing, the order of the moves does not matter a lot. We really only care about the height before the sub-sequence being at least minStart. Let us say that we are going to make u up moves, this means we will do d = (n - size(history) - u) down moves (in addition to the moves in history). Since we want the height before running the steps of the subsequence to be as large as possible, then it is better to first run all the u up moves before the sub-sequence and then all the d moves.

Due to the small constraints, we can just loop for a possible value of u between 0 and n-size(history). Then verify a couple of conditions: a) Is the height after running the first u moves at least minStart? . and b) Is the height after running all the moves, including the u up moves, the moves in history and the d down moves equal to exactly hn?. If you find a value of u for which the conditions are true, the result is YES.

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct FoxAndMountainEasy
{
    string possible(int n, int h0, int hn, string history)
    {
        int netChange = 0;
        int minStart = 0;
        for_each(ch, history) {
            // just simulate the movement, if ch=='U', increase
            netChange += ( (*ch == 'U') ? 1 : -1);
            // too low? remember this for minStart
            minStart = std::max(minStart, -netChange);
        }
        // Pick a value for u, the number of up moves done right at the start
        // and before the moves in the history string: 
        for (int u = 0; u <= n - history.size(); u++) {
            // the number of down moves to do later:
            int d = n - history.size() - u;
            // Do things work out?
            if ( (h0 + u >= minStart) && (h0 + u + netChange - d == hn) ) {
                return "YES";
            }
        }
        return "NO";
                 
    }
};

I took my time. Also , I made a couple of mistakes. It is a good thing the examples were so strong. (At first, I was first running all the up moves , then the down moves and finally the history moves. That is not correct.). I knew though that even with the strong examples, there were going to be many challenge opportunities. (And I also was not sure I was not missing a corner case).

Happened later

Then I opened the 550 points problem. Tried many things but faced some dead ends. Went back to 250, trying to think of corner cases. Opened 1000 5 minutes before the end of the coding phase and it seemed interesting.

The challenge phase was interesting because some people had very different solutions , and some were extra clever (or perhaps too clever?). I knew many of those solutions were going to have bugs, but it is not really easy to read them.

I was lucky though, because I caught a solution with an obvious bug. It began by checking if (hn - h0) % 2 != n % 2 and returning "NO". This logic is correct, and perhaps the approach needed this extra check. But there is something very wrong about the languages like c++ and Java that we love so much. Some language designers thought it is a useful convention to make the % operator return a negative number if the dividend is also negative. In my opinion, this feature is never useful and almost always just a cause of bugs. Modular arithmetic works by stating -1 belongs to 1 modulo 2. So it does not make sense. This bug with % operator has caught me in the past, so this time I could sense it and gained 50 points. Then I tried to find more instances of that mistake, but other coders doing this parity check took better previsions (In some cases though, I am not sure if intentionally).

Comments / etc?

Feel free to post your own opinions and accounts. I liked this match. It was a bit tough. But it is good to be back at competition. I am tired of watching people compete.

Read More