## Thursday, August 23, 2012

### 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(n4)

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++) struct SafeRemoval {     vector<int> modsum;     int finish;          int dp;          // 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[n0] + modsum[n1]                        + modsum[n2] + modsum[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.size()-1, modsum.size()-1,                        modsum.size()-1, modsum.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. Mike Mirzayanov also has a space in its handle :) Tuananh93 said...

Hi vexorian, I'm tuananh93 (on topcoder).
Thank you for an interesting problem set.

I'm writing an editorial for srm 553 but I stucked with the div1 hard.
Even when the solution of writer is really short.
Can you give me some hints. vexorian said...

I haven't solved it yet.

Usually you can ask rng_58 for more help for it if there are no other sources.