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.