Jul 062010
 

There are no red coder from Indonesia who participate in this match, and there are only two yellow coders (felix_halim and handojo1). Me? I’m back to blue…

SRM 475, 300 point

RabbitStepping

The field size is at most 17, so we can solve this problem by bruteforce. We just need to try all possible initial combination and simulate the rabbit’s movement. To generate all possible initial combination, we can iterate from 0 to 2n-1 and work on its binary representation.

for ( int bit = 0; bit < (1 << n); bit++ ) {
  for ( int i = 0; i < n; i++ ) if ( bit & (1 << i) ) {
    // there's a rabbit at cell i
  }
}

Remember, the number of rabbit is r, so we should process only bit which has r hamming weight.

Hamming weight
Hamming weight of binary number is the digit sum of the binary representasion of a given number (the number of digit ‘1’ in its binary representation). For example, 11 in binary is 10112, so the hamming weight of 11 or h(11) is 3.

There are various method to calculate hamming weight.

int h(int n) {
  int ret = 0;
  while ( n != 0 ) {
    ret += n % 2;
    n  /= 2;
  }
  return ret;
}

or using bitwise operator…

int h(int n) {
  int ret = 0;
  while ( n != 0 ) {
    ret += (n & 1);
    n  >>= 1;
  }
  return ret;
}

The simplest one that I know is this:

int h(int n) {
  if ( n == 0 ) return 0;
  return 1 + h(n&(n-1));
}

The last one comes from an observation that n-1 will make the most right ‘1’ turn into ‘0’ and any digit that lies right to it become ‘1’. For example, 616 is 10011010002 and 615 is 10011001112. So n & (n-1) will erase one ‘1’ from n, ie. the right most one.

C/C++ also has this hamming weight (or population-count/popcount) implementation:

int x = __builtin_popcount(n);

I took only about 10-15 minutes to code this problem, but *damn* I spent more than 30 minutes to find bugs in my code T_T. By the time I submitted the solution, it was 15 minutes left before the contest end.

I didn’t manage to think any solution for 600pt, so I ended with 117.29 point till the end of the contest. Yeah, my rating goes down again (-11).

Here is my 300 code, the time complexity is O(2n * n * r):

#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
struct RabbitStepping { double getExpected(string field, int r); };
 
int h(int n) { return n ? 1+h(n&(n-1)) : 0; }
 
double RabbitStepping::getExpected(string field, int r) {
  double ret = 0.0;
  int n = field.size(), cnt = 0;
  REP(bit,1<<n) if ( h(bit) == r ) {
    cnt++;
    vector <int> move(r), prev(r);
    vector <int> pos;
    REP(i,n) if ( bit & (1 << i) ) pos.push_back(i);
    int s = n;
    while ( s > 2 ) {
      REP(i,pos.size()) if ( pos[i] != -1 ) {
        if ( pos[i] == 0 ) move[i] = 1;
        else if ( pos[i] == s - 1 ) move[i] = s - 2;
        else if ( pos[i] == s - 2 ) move[i] = s - 3;
        else if ( field[pos[i]] == 'W' ) move[i] = pos[i] - 1;
        else if ( field[pos[i]] == 'B' ) move[i] = pos[i] + 1;
        else if ( field[pos[i]] == 'R' && s == n ) move[i] = pos[i] - 1;
        else if ( field[pos[i]] == 'R' && s != n ) move[i] = prev[i];
      } else move[i] = -1;
      prev = pos;
      int rabbit[20] = {0};
      REP(i,move.size()) if ( move[i] != -1 ) rabbit[move[i]]++;
      REP(i,move.size()) if ( move[i] != -1 ) {
        if ( rabbit[move[i]] > 1 ) pos[i] = -1;
        else pos[i] = move[i];
      }
      s--;
    }
    REP(i,pos.size()) if ( pos[i] != -1 ) ret ++;
  }
 
  return ret / cnt;
}

fushar and agus.mw increases their rating and back to yellow, congratz to them 🙂

  One Response to “TopCoder SRM 475”

  1. Learned a lot from your blog. Thankyou!

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)