Cowpatibility

USACO 2018 December Gold 2

Problem

Solution

Bruteforce approach for this problem is going through all possible pairs of cows and check if the cows share a common flavor. But it takes $O(N^2)$ to compute the pairs, which brings TLE error.

Let's focus on the number of flavors each cow like, since 5 is much smaller than 50,000. If we think about the possible flavor sets for each cow, there are $2^5-1=31$ cases.

Using PIE, we can count the number of $(i,j) (i>j)$ such that $i$ and $j$ share common flavor.

If $P_i(k)$ refers to number of cows that share more or equal to $i$ flavors with cow $k$,
$N=P_1-P_2+P_3-P_4+P_5$
The problem can be solved by summing up the $N$s.

Code

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
long long N, a[5], r;
map <vector<long long>, long long> m;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(long long i=1; i<=N; i++){
        for(long long i=0; i<5; i++)
            cin >> a[i];
        sort(a, a+5);
        for(long long i=1; i<(1<<5); i++){
            vector <long long> v;
            for(long long k=0; k<5; k++){
                if(i & (1<<k)) v.push_back(a[k]);
            }
            r+=(v.size()%2 ? 1 : -1) *m[v];
            m[v]++;
        }
    }
    cout << N*(N-1)/2-r;
    return 0;
}