SRM 554

I posted something about SRM 554 TCO blog. Extra comments:

I had quite a silly luck this time. I do not why, but I took very long in the 250 points one. Probably because I went from the general case to the specific case instead of the opposite. So I was just about to solve the problem finding the union of three arithmetic sequences, until I started doing an extra analysis to notice that many of the intersections are not possible.

Pretty code for that problem:

int find(int redCount, int redHeight, int blueCount, int blueHeight) 
{ 
    return  
         + min(redCount, blueCount) 
         + 1 + min(redCount-1, blueCount) 
         + 1 + min(redCount, blueCount-1) 
         - (redHeight == blueHeight) * (min(redCount, blueCount) ); 
} 

For div1 500, I messed up even more spectacularly. I reached the conclusion of the condition that was necessary to reach the optimal result (but I did not think to prove that it is also sufficient, knowing that it was also sufficient would have saved me a lot of problems). The problem is that after that, I used a dynamic programming approach. I took some time to code it, until I found that I was failing the last example (Which does not make sense, because the condition IS necessary). I did a quick fix by adding a dimension to the dp. The quick fix was not necessary, but it passed the examples so I submitted the problem.

Then I noticed that I had too many dimensions and my approach could be too slow (It was n⁶ in theory, but maybe it runs faster). I tried some random test cases, until I found one that was not timing out, but instead breaking an assertion I added while debugging the first bug. It turns out that I was sorting an array after I make the copy that was in use by the dynamic programing algorithm. So, I fixed that bug, which fixed the assertion, but now, as I suspected, was timing out. I figured that maybe that lame bug was the one that caused my initial solution to fail. There was only 1 minute left. Somehow, I managed to get rid of the extra dimension in the dp, pass examples and re-submit before the end of the coding phase.

Challenge phase was more about feeling very nervous. I felt the approach was right, but overcomplicated , so there was plenty of room for failure. At the end I passed. (yay)

Here is pretty code for it:

vector<int> find(vector<int> heights) 
{ 
    int n = heights.size(); 
    vector<int> res(n, 0), used(n, false); 
    used[0] = true;  
    //res[0] = 0 is always possible. 
    // Yes, it is always possible to choose any arbitrary first element and still 
    // follow the condition (non-increasing and then non-decreasing) 
    // 
    for (int i=1; i<n; i++) { 
        for (int j=n-1; j>=0; j--) { 
            if (! used[j]) { 
                if (heights[j] <= heights[ res[i-1] ] ) { 
                    //this is always fine. 
                    // If an element j exists such that: 
                    //   heights[j] < heights[res[i-1]) 
                    // 
                    // It means that the next case was never reached. Thus it is 
                    // still possible to do it. 
                    // 
                    // if heights[j] = heights[res[i-1]], then it can count as 
                    // either of the cases and also fine. 
                    res[i] = j; 
                } else { 
                    // If the new element is greater, then it must forcefully be 
                    // equal to the minimum of the remaining elements so that the 
                    // rest of the elements are placed in non-decreasing order.  
                    bool can = true; 
                    for (int k=0; k<n; k++) { 
                        can &= (used[k] || (heights[k] >= heights[j]) ); 
                    } 
                    if (can) { 
                        res[i] = j; 
                    } 
                } 
            } 
        } 
        used[res[i]] = true; 
    } 
    return res; 
} 
 

As you can see, Figuring out (and proving) that the condition is not only necessary but also sufficient allows a VERY simple approach.

Div2 1000 was cute. Here is code for it too:

const int MOD = 1234567891; 
#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++) 
struct TheBrickTowerHardDivTwo 
{ 
    int pow5[5]; 
    int mem[8][48][5*5*5*5]; 
     
    // I encode each state as a single number in base 5. 
    // (I added a fifth color that is a wildcard. So that the top-most row 
    // in a dp can add any colors without decreasing K). 
    // 
    // The transition array saves all the possible transitions from a state 
    // of colors to another AND the value we have to decrease from K. 
    // It is sorted non-decreasingly by the value to decrease from K, so that 
    // we can stop when K would get less than 0. 
    vector<pair<int,int> > transition[5*5*5*5]; 
     
     
    int rec(int K, int H, int state) 
    { 
        int &res = mem[K][H][state]; 
        if (res == -1) { 
            if (H==0) { 
                res = 1; //empty 
            } else { 
                long long tem = 0; 
                // Iterate through the list of transitions, try the transition 
                for_each(q, transition[state]) { 
                    int nk = K - q->first; 
                    if (nk >= 0) { 
                        tem += rec(nk, H-1, q->second); 
                    } else { 
                        break; 
                    } 
                } 
                res = (int)( tem % MOD); 
            } 
        } 
        return res; 
    } 
     
    int find(int C, int K, int H) 
    { 
        pow5[0] = 1; 
        for (int i=1; i<=4; i++) { 
            pow5[i] = 5*pow5[i-1]; 
        } 
        memset(mem, -1, sizeof(mem)); 
         
        // make the transitions 
        for (int state=0; state<pow5[4]; state++) { 
            for (int newstate=0; newstate < pow5[4]; newstate++) { 
                bool valid = true; 
                int krem = 0; 
                for (int i=0; i<4; i++) { 
                    int x = (newstate / pow5[i])%5; 
                    // use only C colors... 
                    valid &= ( x < C); 
                    // sharing face with the above brick 
                    if ( (state/pow5[i]) % 5 == x) { 
                        krem++; 
                    } 
                    // We represent the colors in this way. 
                    // [0][1] 
                    // [3][2] 
                    // This means that a cube is adjacent to the next and previouis 
                    // index. Which translates to us needing to check index (i+1)%4 
                    int y = (newstate / pow5[ (i+1) % 4 ]) % 5; 
                    if (y == x) { 
                        krem ++; 
                    } 
                } 
                if (valid && (krem <= K) ) { 
                    transition[state].push_back( make_pair(krem, newstate) ); 
                } 
            } 
            sort(transition[state].begin(), transition[state].end()); 
        } 
        long long res = 0; 
        for (int i=1; i<=H; i++) { 
            res += rec(K, i, pow5[4] - 1 ); 
        } 
        return (int)(res % MOD); 
    } 
}; 
 

Read More

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.

Read More

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...

Read More

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.

Read More

About algorithm work environments

Posted this in TCO blog:

About algorithm work environments

Read More