Codeforces 442A - Borya and Hanabi

Problem Statement:
442A - Borya and Hanabi

Solution:
Not an easy problem for me.. The first and easiest thing to say is there are 10 type of hints and hence we can do a complete search on each \(2^{10}\) combination of them. Now the hardest part is that, given a combination of hints, check whether they will allow us to differentiate amongst all the cards. For me this is not an obvious task.. One observation is that if a type of cards occurs more than once, we can consider them as one. This is because given a hint (color or value) in which the type belongs to, we will open up all cards belonging to that type, which can be considered as one set. Each type of cards belong to only one set at most, and these sets are disjoint, hence the observation is valid. So it suffices to keep track on the type of cards present.



The next observation, that I can't discover myself, is that given a combination of hint, the positions of all the cards are only determinable if and only if for each pair of card, we can distinguish one from the other. Two cards are distinguishable if we have a hint that allows us to point to only one of them. If all the cards are distinguishable, then naturally we can place them to their correct order by elimination. Very clever indeed.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int mark[5][5];
int tot[10];
int N;

int main(){
    string s;
    scanf("%d",&N);
    int cnt = 0;
    for(int i=0;i<N;++i){
        cin >> s;
        int x;
        if(s[0] == 'G') x = 0;
        if(s[0] == 'B') x = 1;
        if(s[0] == 'R') x = 2;
        if(s[0] == 'Y') x = 3;
        if(s[0] == 'W') x = 4;
        mark[x][s[1]-'1'] = 1;
    }
    int mask = (1<<10) - 1;
    int ans = 11;
    while(mask>=0) {
        int k = 0;
        for(int i=0;i<10;++i){
            if(mask&(1<<i))++k;
        }
        bool ok = true;
        for(int a=0;a<5;++a){
            for(int b=0;b<5;++b){
                for(int c=0;c<5;++c){
                    for(int d=0;d<5;++d){
                        if(a==c && b==d)continue;
                        if(mark[a][b] && mark[c][d]){
                            if(a==c){
                                if(!(mask&(1<<(b+5)) || mask&(1<<(d+5)))){
                                    ok = false;
                                }
                            } else {
                                if(b==d){
                                    if(!((mask&(1<<a)) || (mask&(1<<c)))){
                                        ok = false;
                                    }
                                }else{
                                    if(!((mask&(1<<a)) || (mask&(1<<c)) || (mask&(1<<(b+5))) || (mask&(1<<(d+5))))){
                                        ok = false;
                                    }
                                }
                            } 
                        }
                        if(!ok)break;
                    }
                }
            }
        }
        if(ok){
            ans = min(ans,k);
        }
        --mask;
    }
    printf("%d\n",ans);
    return 0;
}