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[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 :

Ashar Fuadi said...

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.