SRM 553

I posted stuff to the TCO blog: http://community.topcoder.com/tco12/happened-in-srm-553/

More things to say:

• I did not really want div1 250 to be so tricky. In fact, the second-last example is supposed to detect overflow. Apparently, it only detects overflow in the specific solution I was trying, a different kind of overflow was not detectable, sorry.
• I was expecting this to be an awful problem set (Except for div1 hard). But it seems reception was mostly positive. Ok...
• I was very happily writing that TCO blog post, then I noticed that the handle tag script I wrote was failing. I then remembered that profile pages were updated... Lucky me it actually did not take me a lot of time to update my script. If you used it, you can get the update from its post.

Nice codes for the problems:

Div2 250

A good balance is to iterate for the number of platypuses (or platypy, platypeople? whatever).

int minimumAnimals(int webbedFeet, int duckBills, int beaverTails) 
{ 
    for (int p=0; p<=duckBills && p<=beaverTails; p++) { 
        int d = duckBills - p; //number of ducks 
        int b = beaverTails - p; //number of beavers 
        // verify 
        if (p*4 + d*2 + b*4 == webbedFeet) { 
            return p+d+b; 
        } 
    } 
    // this is not reached, but in the judge solution I use it to verify 
    // that the test case passes constraints... 
    return -1; 
} 
 

It needs at most 500 iterations. Crude bruteforce shall work too, unless you do a good work in making it very unoptimized.

This also works:

return webbedFeet / 2 - beaverTails;

Why does it work? Well, try simplifying the equations derived from the first code and you shall see, eventually.

Div2 500 / Div1 250

Again, I really like Petr's solution. rng_58 was the first to try something like that. This is a very concise version:

const int INF = 2000000000; 
int simulate(vector<int> program, int x) 
{ 
    // x determines what integer to replace -1 with. 
    stack<int> S; 
    // this way return S.top() will always return something 
    S.push(0); 
    for (int i=0; i<program.size(); i++) { 
        int p = ( (program[i]==-1) ? x : program[i] ); 
        if (p == 0) { 
            if (S.size() > 1) { 
                int a = S.top(); S.pop(); 
                int b = S.top(); S.pop(); 
                // INF prevents overflow (I just dislike 
                //  typing long long that much) 
                S.push( (a > INF - b)? INF : (a+b) ); 
            } //Else there is nothing to do. 
        } else { 
            S.push(p); 
        } 
    } 
    return S.top(); 
} 
int findMissing(vector <int> program, int wantedResult) 
{ 
    if (simulate(program, 0) == wantedResult) { 
        // If 0 works, it is the result. 
        return 0; 
    } 
    int a = simulate(program, 1); 
    int x = wantedResult - a + 1; 
    int b = simulate(program, 2); 
    // The equation is : a - 1 + x = wantedResult 
     
    // If they are equal the result is constant and cannot 
    // be changed. If x <= 0, then there is no valid result 
    // (Using x = 0 is not possible, because 0 has a special meaning) 
    return ( (a == b) || (x <= 0) )? -1 : x; 
} 

Div2 1000:

It is a polynomial time dp. O(n⁴)

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++) 
struct SafeRemoval 
{ 
    vector<int> modsum[4]; 
    int finish; 
     
    int dp[51][51][51][51]; 
     
    // modsum[i][x] returns the sum of the x largest numbers that are = i modulo 4 
    int rec(int n0, int n1, int n2, int n3) 
    { 
        int & res = dp[n0][n1][n2][n3]; 
        if (res == -1) { 
            res = 0; 
             
            int total = modsum[0][n0] + modsum[1][n1]  
                      + modsum[2][n2] + modsum[3][n3]; 
                       
            // The finishing state is when there are (finish) numbers left. 
            // ( finish = n - k ) 
            if (finish == n0 + n1 + n2 + n3) { 
                //base case: 
                res = total; 
            } else { 
                // remove a number that is: 0 mod 4 
                if ( (n0 > 0) && (total % 4 != 0) ) { 
                    res = std::max(res, rec(n0-1, n1, n2, n3) ); 
                } 
                // remove a number that is: 1 mod 4 
                if ( (n1 > 0) && (total % 4 != 1) ) { 
                    res = std::max(res, rec(n0, n1-1, n2, n3) ); 
                } 
                // remove a number that is: 2 mod 4 
                if ( (n2 > 0) && (total % 4 != 2) ) { 
                    res = std::max(res, rec(n0, n1, n2-1, n3) ); 
                } 
                // remove a number that is: 3 mod 4 
                if ( (n3 > 0) && (total % 4 != 3) ) { 
                    res = std::max(res, rec(n0, n1, n2, n3-1) ); 
                } 
 
            } 
        } 
        return res; 
    } 
     
    int removeThem(vector <int> seq, int k) 
    { 
        finish = seq.size() -  k; 
        // sort in reverse! 
        sort(seq.rbegin(), seq.rend()); 
        for (int i=0; i<4; i++) { 
            modsum[i].push_back(0); 
        } 
        // Make the sums: 
        for_each(q, seq) { 
            modsum[*q % 4].push_back(*q + *modsum[*q % 4].rbegin() ); 
        } 
        memset(dp, -1, sizeof(dp)); 
         
        // We initially have all the numbers: 
        int res = rec( modsum[0].size()-1, modsum[1].size()-1, 
                       modsum[2].size()-1, modsum[3].size()-1); 
 
        // 0 is a good invalid value. It is impossible for a valid result 
        // to be 0, because k is strictly less than n. 
        return ( (res==0) ? -1 : res ); 
    } 
}; 

The first version of the problem had n<=30 and the modulo was not fixed to 4. It was a variable m that could be at most 10. The idea is the same, but encoding the dp state is not as easy. Just use a map or hash table to use whole vector as key.

Div1 500

This problem is very evil implemenation-wise. I cannot provide less messy code than what you can already see submitted. Sorry.

SRM 552: An end to FoxPaintingBalls

After the failure of yesterday, I decided to take a look back to this problem.

Given N make "ball triangles" using balls of only 3 colors in a way that no balls of the same color touch. There are R, G and B red, green and blue balls (These variables are each at most 10¹⁸. What is the maximum number of valid triangles we can make?

A triangle of N=3:

  o
 o o
o o o

A valid way to pick the colors for the triangle:

  G
 R B 
B G R

In the last post I explained that if you pick a certain color to be color #1 (The color of the bottom left ball in the triangle, then the counts of colors #1, and #2 and #3 are always the same for a given value of N and we also know how to calculate them.

We know that in case N % 3 = 1, then x, the number of balls you need for color #1 is equal to y+1, where y is the number of balls you need for colors #2 and #3. When N % 3 != 1, then x = y .

Then the problem is to find the correct number of times you have to pick red, green or blue as color #1.

The solution I tried to code during the match was also explained in that post. Basically you try to do the simulation until the number of remaining balls of more than one color are the same, etc, etc etc. This code was VERY complicated, and full of corner cases, no wonder I made a mistake in implementing it, but I also found many other mistakes in my code. Including a complete bug: When two colors are equal, and you can't drop them in a way that three become equal, you have to subtract one color individually.

But there are better ways.

Formalize

I feel lame now. This is something I tend to include in many of the editorials I write. It can help A LOT to first define a problem formally. this is what I did not try to do yesterday, and this is what turns out to be the key to a simple solution.

Let us forget about the case when N%3 != 1, that one is simple because we can pick any color as color #1 without changing anything. Let us also treat N=1 separately as just returning R+G+B. What is left is the case where x = y+1. Let us focus on y.

Let X1 be the number of triangles in which we pick red as color #1. X2 the number of triangles in which we pick yellow as color #1, and X3 the number of triangles with blue as color #1.

We want to maximize z = X1 + X2 + X3, the total number of triangles we make.

When we pick red as color #1, we use y+1 available balls of color red, and y balls of the other colors. Extend this logic to blue and green:

Max z = X1 + X2 + X3

X1 * (y + 1) + X2 * y       + X3 * y       <= R
X1 * y       + X2 * (y + 1) + X3 * y       <= G
X1 * y       + X2 * y       + X3 * (y + 1) <= B

This is where the +1 difference comes into play, just develop the algebra a little:

(X1 + X2 * X3) * y + X1 <= R
(X1 + X2 * X3) * y + X2 <= G
(X1 + X2 * X3) * y + X3 <= B
->
             z * y + X1 <= R
             z * y + X2 <= G
             z * y + X3 <= B

These last three inequations are the key to solve the problem. Every time you increase z by one, then we use y balls of each color. After we make z triangles, then the values of X1, X2 and X3:

X1 < R - z*y
X2 < G - z*y
X3 < B - z*y

e.g.: R - z*y is the maximum number of times you could have used red as color #1. But notice that X1 + X2 + X3 = z, thus :

R - z*y + G - z*y + B - z*y >= z

If that condition does not fulfill, then the value we chose for z is impossible. We have therefore designed a way to find out if a given value of z is possible or not. We can also tell that if z = t is not possible, then z = t+1 is not possible either. And if z = t is possible, then z = t -1 is possible. We can just do a Binary search on the value of z.

typedef long long int64; 
#define long int64 
 
struct FoxPaintingBalls 
{ 
    //adds the number of balls of color 1 in row N to x  
    //and the number of balls of colors 2 or 3 to y.  
    void row(int N, long & x, long & y)  
    {  
        long z = (N - 1) / 3 + 1;  
        if (N % 3 == 1) {  
            x += z;              
            y += z - 1;  
        } else if (N % 3 == 2) {  
            x += z - 1;  
            y += z;  
        } else if (N % 3 == 0) {  
            x += z;  
            y += z;  
        }  
    }  
    long theMax(long R, long G, long B, int N)  
    {  
        long x = 0, y = 0;  
        // For multiples of 3, the balls are evenly distributed  
        // fix N to the closest multiple of 3 (downwards)  
        long t = N - N%3;  
        // total number of balls (Gauss)  
        t = (t * (t + 1)) / 2;  
        // divide evenly  
        x += t / 3;  
        y += t / 3;  
        //... the remaining 1 or 2 rows:  
        if (N % 3 == 1)  {   
            row(N, x, y);  
        } else if (N % 3 == 2) {  
            row(N-1, x, y);  
            row(N, x, y);  
        }  
         
        if (N % 3 != 1) { 
            // x = y 
            // it does not matter how we choose the colors: 
            long res = R / x; 
            res = std::min(res, G / x); 
            res = std::min(res, B / x); 
            return res; 
        } else if (N == 1) { 
            // Each ball makes one triangle. 
            return R + G + B; 
        } else { 
            // Binary search for z. 
            long lo = 0, hi = 1LL<<62; 
            // possible(lo) && !possible(hi) 
            while (lo + 1 < hi) { 
                long ha = hi - (hi - lo) / 2; 
                // this first condition verifies that the boundaries 
                // are not negative (z*y <= R) 
                // 
                bool good = ( (ha <= R/y) && (ha <= G/y) && (ha <= B/y) ); 
                // Now the condition from the analysis: 
                good &=  (R + G + B - 3*ha*y >= ha ); 
 
                if (good) {  //possible 
                    lo = ha; 
                } else {    // not possible 
                    hi = ha; 
                } 
            } 
            return lo; 
        } 
         
         
    } 
}; 
#undef long 

There is more

Of course, further analysis will show you that there is no need for the binary search, we can find the max value of z through simple division. Just turn each of the conditions we used into a bound:

long z = R / y; 
z = std::min(z, G / y); 
z = std::min(z, B / y); 
z = std::min(z, (R + G + B) / (3 * y + 1) ); 
return z; 

In fact, note that until the last line, that is the solution for the case when N % 3 != 1 as well. So we can basically replace everything with this log.

// after finding x and y: 
if (N == 1) { 
    return R + G + B; 
} 
long z = R / y; 
z = std::min(z, G / y); 
z = std::min(z, B / y); 
if (N % 3 == 1) { 
    z = std::min(z, (R + G + B) / (3 * y + 1) ); 
} 
return z; 
 

The logic to find x and y can also be simplified a lot...

SRM 552: Greed kills

What a match. I think the problem setters exagerated with the div1 250's difficulty. I would have kept the constraints of R,G and B small so dp was possible.

Div1 250

As far as I recall, there was only one problem in this match. Given N make "ball triangles" using balls of only 3 colors in a way that no balls of the same color touch. There are R, G and B red, green and blue balls. What is the maximum number of valid triangles we can make?

A triangle of N=3:

  o
 o o
o o o

A valid triangle:

  G
 R B 
B G R

Forced moves

This was the nice part of the problem, to figure out that once you pick a ball for the top-left corner, the remaining moves are basically forced.

Let us name the color of that first ball 1, then 2 and 3 are the remaining colors. After drawing balls a lot and failing to do it in paper, I started representing a triangle by a table-like structure:

    2
   13
  321
 2132 ...
13213

Once you pick the color for the top-left corner, the rest is basically forced, the relative positions of color 2 and 3 can change, but otherwise. The counts will be a forced thing.

Then we just need to find the formula, given N, how many balls of color 1 will there be, and how many balls of colors 2 and 3 (Note that those counts are the same).

I needed to draw and draw until the pattern is evident. Let us first consider only the rows. x denotes the number of balls of color 1 and y the balls of colors 2 and 3.

N	x	y
1	1	0
2	0	1
3	1	1
4	2	1
5	1	2
6	2	2

...

This pattern goes on. Now note that every 3 rows, the totals become equal. Eventually you can find an easy way to calculate the total x and y for all the rows. Only based on N%3.

Further analysis will reveal that the numbers of balls of each color are evenly distributed most of the time. The only exception is when N%3 = 1, in which case x will always be equal to y+1.

    //adds the number of balls of color 1 in row N to x 
    //and the number of balls of colors 2 or 3 to y. 
    void row(int N, long & x, long & y) 
    { 
        long z = (N - 1) / 3 + 1; 
        if (N % 3 == 1) { 
            x += z;             
            y += z - 1; 
        } else if (N % 3 == 2) { 
            x += z - 1; 
            y += z; 
        } else if (N % 3 == 0) { 
            x += z; 
            y += z; 
        } 
    } 
    long theMax(long R, long G, long B, int N) 
    { 
        long x = 0, y = 0; 
        // For multiples of 3, the balls are evenly distributed 
        // fix N to the closest multiple of 3 (downwards) 
        long t = N - N%3; 
        // total number of balls (Gauss) 
        t = (t * (t + 1)) / 2; 
        // divide evenly 
        x += t / 3; 
        y += t / 3; 
        //... the remaining 1 or 2 rows: 
        if (N % 3 == 1)  {  
            row(N, x, y); 
        } else if (N % 3 == 2) { 
            row(N-1, x, y); 
            row(N, x, y); 
        } 
 
        // 
 

What now?

This was the hard and evil part. (Even though the first part was already quite cool and interesting, this is why I think the problem would have been better if we were able to solve this with dp).

We now have to decide how many times use red, green and blue as color 1. The constraints are large so we will need some sort of greedy. This is one of the first way in which greed killed me. This greedy was very tricky to think of.

When x=y (which happens when N%3 != 1), this decision does not really matter. When N=1, then the result is R+G+B. Those are the simple cases.

The first tempting idea is to just sort the number of available balls. And always use the most available color as color 1. This fails examples. When R=G=B=100, you will notice it is better to alternate the colors.

Always alternating the colors is tempting but does not always work.

If the constraints were lower, the following simulation would work: While there are enough balls to make one triangle, pick the color with the most balls available, use it as color 1, subtract x from it and y from the other colors. Always repeat. This greedy algorithm will work, but it is not possible to implement it in its current form.

I hesitated a lot before trying to implement that logic in a way that would work in time (Find the number of times to drop maximum color until it becomes equal to another one. The problem is that then when there are three or two equal color you have to drop them in unison.) At the end I was running out of time, and decided to do it, after writing long and awful code that was most likely wrong, I tested the code and with 20 seconds left it passed examples. Sure, why not? I submitted it. Then I noticed a couple of obvious bugs in the code. Just now I learned that even after fixing those bug, there was still another big bug and then even after that big bug, there is still an error somewhere.

That is right, I am still not sure how to solve this. Well, I do know of a formula that seems to pass system tests, but right now I can't prove it.

Challenge phase

I knew I had 0 points, but I also knew that it was simply not possible for many people to solve this problem correctly. I already knew the examples were weak. I sort of imagined that people would try variations of alternating the colors, even when it is not the best idea.

I thought of a case, R = 10¹⁸, G = 5*10¹⁷, B = 25*10¹⁶, N=4. N=4 ensures that the choices matter.

After two successful challenges of two attempts, I felt greedy, and tried again. Third attempt was not that good. Fourth was not either. I actually dropped back to 0 points!. But I did not give up and challenged another one. Luckily this one failed. Then I got greedy again and stuck with 25 points. I really regret not stopping once I had 100 points. It would have been a decent score.

About algorithm work environments

Posted this in TCO blog:

About algorithm work environments

SRM551: slowness

Nothing like a TopCoder SRM with an ultra easy problem set to make you feel like a turtle. I solved both problems yet I am in position 230-th. (Starting to write this 5 minutes before the coding phase ends).

Div1 450 : The one with the wolves

Anyway, a wolf changes colors at night, when the wolf has a certain color, there is a list of available colors for it to change to. The wolf always picks the smallest color available. You are allowed to remove some of the possibilities to change from a color to another. What is the minimum number of removals you need so that a wolf starting at color 0 eventually reaches color N-1? (Does not have to stay in that color).

For some incredibly stupid reason, my old reflexes came back and I started with the medium problem. I really did not intend this to happen. This problem was so easy that I think I should have first warmed up on the division I 250 to be able to solve this one faster.

As my brain was just starting to function I was first lost on the idea that it was a maximum flow problem. Because in a way it asks you to cut roads. To the point that even when I thought of the cost function to make you go from a color to another, I decided to use min cost max flow instead of the obvious Dijkstra / or Floyd-Warshall. I would only discover my mistake after I made the code for the flow network...

Anyway, the wolf will always pick the smallest color available. It is always possible to force the wolf to pick any of the colors that are possible, you just need to remove the availability of the smaller colors. In order to force wolf color i to always turn into wolf color j, just remove all the available changes to colors of smaller value. This is the cost to move from color i to color j. You end up with a list of costs to move from each color to another. What is the cost to reach N-1 starting at 0? This is just a min-cost path problem. The paths are weighted. I just used Floyd-Warshall.

int getmin(vector <string> colormap) 
{ 
    int n = colormap.size(); 
    int cost[n][n]; 
    const int INF = 1<<20; 
    // Find the cost matrix 
    for (int i=0; i<n; i++) { 
        for (int j=0; j<n; j++) { 
           // infinite cost path means there is no path between the two colors 
            cost[i][j] = INF; 
            if (colormap[i][j] == 'Y') { 
                cost[i][j] = 0; 
                for (int k=0; k < j; k++) { 
                    cost[i][j] += (colormap[i][k] == 'Y'); 
                } 
            } 
        } 
    } 
    // Floyd-Warshall finds all minimum total costs, and is very simple to code: 
    for (int k=0; k<n; k++) { 
        for (int i=0; i<n; i++) { 
            for (int j=0; j<n; j++) { 
                cost[i][j] = std::min( cost[i][j], cost[i][k] + cost[k][j] ); 
            } 
        } 
    } 
    return ( (cost[0][n-1] == INF) ? -1 : cost[0][n-1]); 
} 

Div1 250 : The one with the string of colors

You are given a string, like "AABACAA", what is the maximum number of adjacent characters in a string you get by modifying the original one using at most maxSwaps swaps of adjacent characters?

A O(n⁵) algorithm: For each value of the number of adjacent characters. Try each possible starting index of the adjacent characters. For each of them, try the character of those. For each of them, find the minimum cost to have it that way.

The minimum cost can be found in O(n²), just find the starting point of the wanted letters used in the original string. Then you find the positions of the (spread) letters in the original string that have to be moved to the adjacent area.

It is much easier to do than explain.

Let us say that the X mark original positions of the characters we are interested in:

X.X....X.X

Somehow we want the final string to be "...XXXX...". What is the minimum cost? The first X in the string has to be the first X in the wanted area. That involves a distance and a cost. The second X has to be the second X and so and so. This is simple. The complication is when there are far more Xs than wanted:

X.X.X....X.X.X

If we still want ....XXXX..... , then we have to pick which of the original X is the first one.

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++) 
int maximumSpread(string chocolates, int maxSwaps) 
{ 
    //set some stuff up: 
    vector<char> colors; //available colors 
    {  
        set<char> chset(chocolates.begin(), chocolates.end()); 
        for_each(ch, chset) { 
            colors.push_back(*ch); 
        } 
    } 
    //  
    vector<int> cnt(256, 0); //number of times each color appears. 
    for_each(ch, chocolates) { 
        cnt[*ch] ++; 
    } 
    int n = chocolates.size(); 
     
    // For each possible spread: 
    for (int spread=n; spread > 1; spread--) { //O(n) 
 
        // for each starting index: 
        for (int start=0; start+spread <= n; start++) { //O(n*n) 
            // for each color :             
            for_each(ch, colors) {  //O(n*n*n) 
                if (cnt[*ch] >= spread ) { 
                    // for each starting index in the original string of that color: 
                    for (int o=0; o<n; o++) { //O(n*n*n*n) 
                        if ( chocolates[o] == *ch ) { 
                            int x = 0; 
                            int pos = o; 
                            int cost = 0; 
                            // find the costs to move each letter: 
                            while (pos < n && x < spread) {  //O(n*n*n*n*n) 
                                if ( chocolates[pos] == *ch ) { 
                                    cost += abs(start + x - pos); 
                                    x++; 
                                } 
                                pos++; 
                            } 
                            // the minimum cost is possible, return it 
                            if ( (cost <= maxSwaps) && (x == spread) ) { 
                                return spread; 
                            } 
                        } 
                    } 
                } 
            } 
        } 
    } 
    // 1 is always possible: 
    return 1; 
} 

This O(n⁵) solution can be easily improved to reduce the exponent, but that is not needed. For example, we can move the loop for o upwards and replace the color with it. In fact, this code is already O(n⁴) because there are O(n) valid pairs of (o, color).

The rest

I was severely dissappointed that everyone was solving both problems much faster. I don't like matches that are determined solely on speed. When the problems are this easy, speed tends to be almost indistinguishable from luck, imho.

I opened the 1000, but it seemed harder, and the targets who got plenty of time as solved the first two problems very fast did not solve it yet. So I instead tried to find possible mistakes in 250 and 450. But it seems that the example cases were very strong. Specially in 250. I thought that a common mistake would be to assume that the result adjacent area has to start at position that already includes the letter. This is not true, but it turns out the second example already catches that corner case.