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.