TopCoder SRM 511

I solved Easy and Meidum. But I made careless mistake in Easy and got only 75pts by resubmission. My place was 135th and my rating stayed.

Rating: 2237 -> 2237 (+-0)

Link to TopCoder(login required)

250 Zoo

Cats' answers should be {0, 1, ..., C-1} and rabbits' answers should be {0, 1, ..., R-1} if there are at least one valid configurations. Then the answer to the problem is 1<<(min(R, C)+1 + (R==C?0:1)).

My code was dirty and not good...

Solution in C++ (in the contest)

class Zoo {
public:
  long long theCount(vector <int> answers) {
    sort(answers.begin(), answers.end());
    map<int, int> cnt;
    for(int i=0; i<(int)answers.size(); ++i)
      cnt[answers[i]]++;
    int a=-1;
    for(int i=0; ; ++i) {
      if(cnt[a+1]>=1) {
        a++;
        cnt[a]--;
      } else break;
    }
    int b=-1;
    for(int i=0; ; ++i) {
      if(cnt[b+1]>=1) {
        b++;
        cnt[b]--;
      } else break;
    }
    for(map<int, int>::iterator it=cnt.begin(); it!=cnt.end(); ++it)
      if(it->second >= 1)
        return 0;
    if(a==-1 || b==-1) return 2;
    if(a-b==1 || b-a==1) return 1ll<<max(a+1,b+1);
    return 1ll<<min(a+1,b+1);
  }
};

500 FiveHundredEleven

This problem can be solved by DP. The key idea is that, if we know the current value of the memory and the number of used cards, we can figure out what cards are unused. So the state is: dp[mem][n] := whether a player can win if the player starts the game from the state that memory's value equals to mem and n cards were used.

My implementation is memoized recursion.

Solution in C++ (in the contest)

class FiveHundredEleven {
public:
  int N;
  vector<int> C;
  int dp[51][512]; // ciel ga kateruka

  int rec(int used, int mask) {
    if(mask == 511)
      return 1;
    if(dp[used][mask] >= 0)
      return dp[used][mask];
    int& ret = dp[used][mask];

    vector<int> remain;
    int muda = 0;
    for(int i=0; i<N; ++i)
      if((C[i] | mask) == mask)
        muda++;
      else
        remain.push_back(C[i]);
    muda -= used;
    for(int i=0; i<muda; ++i)
      remain.push_back(0);

    for(int i=0; i<(int)remain.size(); ++i) {
      int u = remain[i];
      if(rec(used+1, mask|u) == 0)
        return ret = 1;
    }
    return ret = 0;
  }

  string theWinner(vector <int> cards) {
    int all = 0;
    for(int i=0; i<(int)cards.size(); ++i)
      all |= cards[i];
    if(all != 511)
      return cards.size()%2 ? "Fox Ciel" : "Toastman";

    for(int i=0; i<=50; ++i)
      for(int j=0; j<512; ++j)
        dp[i][j] = -1;

    N = cards.size();
    C = cards;
    return rec(0, 0) ? "Fox Ciel" : "Toastman";
  }
};