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^{4})

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

## 3 comments :

Mike Mirzayanov also has a space in its handle :)

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.

I haven't solved it yet.

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

Post a Comment