Codeforces Round #253 (Div. 1) - A. Borya and Hanabi [Revisited]

Problem Statement:
http://codeforces.com/contest/442/problem/A

Summary:
A deck of cards, each card has a name (R, G, B, Y, W) and a value (1, 2, 3, 4, 5). Given an array of cards of unknown names and values, we can ask for hints to identify each of the cards. There are two types of hints: name hint or value hint. For example, when we ask a name hint 'R', all cards with name 'R' will be marked. Similarly, a value hint '2' will mark all cards with value '2'. What is the minimum number of hints needed so that we can identify all the cards exactly? (Note that some cards might be duplicated in the array).

Solution:
I have written about this problem previously (https://abitofcs.blogspot.sg/2015/01/codeforces-442a-borya-and-hanabi.html), however after solving this problem once again I learnt that it can be tackled from a different perspective using bitmap.

Imagine asking for a name hint 'R'. We will then know all the cards that have name 'R', although we might not know what values those card have. If for each of the card, we keep track of a bitmap value of the form RGBYW12345, we can set the bit on position 'R' to indicate this knowledge. Hence if we ask for 10 hints (maximum number of hints), we will be able to identify all cards based on the bitmap values. In fact, if there are no duplicate cards in the array, then if all the bitmap values are different, we can already identify all the cards. Furthermore, notice that the order of the hints do not matter because the final bitmaps from a given set of hints are always the same regardless on which hint is evaluated first.

The problem, however, allows for duplicated cards. Turns out, it is not an issue because duplicated cards will always have the same bitmap values. Therefore we can simply combine duplicated cards as one.

Below is the implementation:

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
int n;
int res = 9999;
int cnt[1200];
vector<int> cardlist;
int bmap[5][5];
void Check(int bm) {
  for(int i=0;i<5;++i){
    for(int j=0;j<5;++j){
      bmap[i][j]=0;
    }
  }
  bool duplicate = false;
  int hints = 0;
  for (int k=0;k<10;++k){
    if (!(bm & (1<<k))) continue;
    hints++;
    for (int i=0;i<5;++i){
      if (k < 5) {
        bmap[k][i] |= (1 << k);
      } else {
        bmap[i][k-5] |= (1 << k);
      }
    }
  }
  for (int i=0;i<cardlist.size();++i){
    int name = cardlist[i]/10;
    int val = cardlist[i]%10;
    cnt[bmap[name][val]]++;
    if (cnt[bmap[name][val]] > 1) {
      duplicate = true;
      break;
    }
  }
  for (int i=0;i<cardlist.size();++i){
    int name = cardlist[i]/10;
    int val = cardlist[i]%10;
    cnt[bmap[name][val]]=0;
  }
  if (!duplicate) {
    res = min(hints, res);
  }
}
int main(){
  scanf("%d",&n);
  string card;
  vector<string> temp;
  for(int i=0;i<n;++i){
    cin >> card;
    temp.push_back(card);
  }
  sort(temp.begin(), temp.end());
  for(int i=0;i<n;++i){
    if (i && temp[i-1] == temp[i]) continue;
    int name = -1;
    switch(temp[i][0]) {
      case 'R':
        name = 0;
        break;
      case 'G':
        name = 1;
        break;
      case 'B':
        name = 2;
        break;
      case 'Y':
        name = 3;
        break;
      case 'W':
        name = 4;
        break;
    }
    cardlist.push_back(name*10+(temp[i][1]-'1'));
  }
  for(int i=0;i<(1<<10);++i){
    Check(i);
  }
  printf("%d\n",res);
  return 0;
}

The time complexity is O(2^k k^2 N) where k is the total number of names and values (10), while N is the number of cards (at most 100).