TCO 2015 round 1A

Similars.cpp

/* The similarity of two number is the number of common digits they have. 
   E.g. S(1123, 220181) = 2 as they all have 1 and 2*/
class Similars {
    public:
    vector<int> getDigits(int i){
        vector<int> res;
        while(i>0){
            res.push_back(i%10);
            i/=10;
        }
        return res;
    }
    
    int maxsim_editorial(int L, int R) {
        int mask[R+1], ans;
        for(int i=L;i<=R;++i){
            for(int d: getDigits(i)){
                mask[i] |= (1<<d); //用bitmask把每個數字代表的bit設為1，就像是我們在naive算法中使用set<char>的概念，可以用&來取intersection，不再需要sort, unique, set_intersection，更為方便。
            }
            //1000: only look for pairs 從i到i-1000，這個數是怎麼決定的？
            for(int j=i-1; j>=L && j>=i-1000; j--){
                ans = max(ans, __builtin_popcount(mask[i]&mask[j]));
            }
        }
        return ans;
    }//http://apps.topcoder.com/wiki/display/tc/TCO15+Round+1A
    
    int maxsim_naive(int L, int R) {
        int ans=0;
        int sz = to_string(R).size();
        for(int i=L;i<=R;++i){
            for(int j=i+1; j<=R;++j){
                string s1=to_string(i), s2=to_string(j);
                vector<char> v(sz);
                sort(s1.begin(), s1.end());
                auto p = unique(s1.begin(), s1.end());
                s1.resize(p-s1.begin());
                sort(s2.begin(), s2.end());
                auto q = unique(s2.begin(), s2.end());
                s2.resize(q-s2.begin());
                auto it = set_intersection(s1.begin(), s1.end(),s2.begin(), s2.end(), v.begin());                
                v.resize(it-v.begin());
                ans = max(ans, (int)v.size());
            }
        }
        return ans;
    }
};