# USACO 2022 February Contest, Gold Problem 1. Redistributing Gifts

### USACO 2022 February Contest, Gold Problem 1. Redistributing Gifts

Farmer John has NN gifts labeled 1N1…N for his NN cows, also labeled 1N1…N (1N181≤N≤18). Each cow has a wishlist, which is a permutation of all NN gifts such that the cow prefers gifts that appear earlier in the list over gifts that appear later in the list.

FJ was lazy and just assigned gift ii to cow ii for all ii. Now, the cows have gathered amongst themselves and decided to reassign the gifts such that after reassignment, every cow ends up with the same gift as she did originally, or a gift that she prefers over the one she was originally assigned.

There is also an additional constraint: a gift may only be reassigned to a cow if it was originally assigned to a cow of the same type (each cow is either a Holstein or a Guernsey). Given QQ (1Qmin(105,2N)1≤Q≤min(105,2N)) length-NN breed strings, for each one count the number of reassignments that are consistent with it.

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN.The next NN lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of 1N1…N.

The next line contains QQ.

The final QQ lines each contain a breed string, each NN characters long and consisting only of the characters G and H. No breed string occurs more than once.

#### OUTPUT FORMAT (print output to the terminal / stdout):

For each breed string, print the number of reassignments that are consistent with it on a new line.

#### SAMPLE INPUT:

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG


#### SAMPLE OUTPUT:

2
1
1
2
2


In this example, for the first breed string, there are two possible reassignments:

For the second breed string, the only reassignment consistent with it is the original assignment.

#### SCORING:

• For T=2,,13T=2,…,13, test case TT satisfies N=T+4N=T+4.
• Test cases 14-18 satisfy N=18N=18.

Problem credits: Benjamin Qi

### USACO 2022 February Contest, Gold Problem 1. Redistributing Gifts 题解(翰林国际教育提供，仅供参考)

[/hide]

(Analysis by Benjamin Qi)

The first observation that needs to be made is that in each query, the Guernseys and Holsteins can be treated independently of each other. Specifically, if we define GG to be the set of Guernseys within a query, then the answer to that query is ans[G]ans[{1,2,,N}G]ans[G]⋅ans[{1,2,…,N}∖G], where ans[S]ans[S] denotes the number of ways for the cows in SS to trade amongst each other.

It remains to describe how to compute ans[S]ans[S] for all subsets S{1,2,,N}S⊆{1,2,…,N}.

Special Case: Computing ans[{1,2,,N}]ans[{1,2,…,N}]

We can solve this using Bitmask DP (see this USACO Guide module). In fact, this case turns out to be equivalent to this problem from that module.

Let's assign gifts to cow 1, then to cow 2, and so on up to cow NN in that order. Our current state is represented by the pair:

where 0pN0≤p≤N and 0i<2N0≤i<2N.

Let  denote bitwise XOR. From the current state we may transition to (p+1,i(1j))(p+1,i⊕(1≪j)) where gift jj is any unassigned gift that cow p+1p+1 may be assigned. There are 2N2N states (since pp is always equal to the number of bits in ii) and the number of transitions from each state is at most NN, yielding an overall time complexity of O(N2N)O(N⋅2N).

Partial Solution: Suppose that we compute ans[S]ans[S] independently for all subsets SS using the solution for a single SS given above. The total number of operations is bounded above by:

S{1N}|S|2|S|N⎛⎝S{1N}2|S|⎞⎠=Nc=1N[(1 if c not in S)+(2 if c in S)]=N3N∑S⊆{1…N}|S|⋅2|S|≤N⋅(∑S⊆{1…N}2|S|)=N⋅∏c=1N[(1 if c not in S)+(2 if c in S)]=N⋅3N

yielding a solution that runs in O(N3N+NQ)O(N⋅3N+NQ) time.

This is enough for 11 out of 18 test cases.

#include <bits/stdc++.h>
using namespace std;

vector<uint64_t> dp(1 << N);
dp = 1;
for (int i = 0; i < (1 << N); ++i) {
int p = __builtin_popcount(i);
for (int j = 0; j < N; ++j)
if (!(i & (1 << j)))
if (new_adj.at(p) & (1 << j))
dp[i ^ (1 << j)] += dp[i];
}
return dp.back();
}

const int MAX_N = 20;
uint64_t ans[1 << MAX_N];
int N;

if (!ans[mask]) { // would speed up if not all queries distinct
vector<int> bits;
for (int i = 0; i < N; ++i)
if (mask & (1 << i))
bits.push_back(i);
for (size_t i = 0; i < size(bits); ++i)
for (size_t j = 0; j < size(bits); ++j)
if (adj[bits[i]] & (1 << bits[j]))
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
assert(N <= MAX_N);
for (int i = 0; i < N; ++i) {
vector<int> pref(N);
for (int &g : pref)
cin >> g;
for (int &g : pref) {
--g;
if (g == i)
break;
}
}
int Q;
cin >> Q;
while (Q--) {
string breeds;
cin >> breeds;
int g = 0, h = 0;
for (int i = 0; i < N; ++i) {
if (breeds[i] == 'G')
g ^= 1 << i;
else
h ^= 1 << i;
}
cout << solve_subset(g) * solve_subset(h) << "\n";
}
}


Full Credit: We again use bitmask DP to compute all entries of ansans, but this time we'll do so in O(N22N)O(N2⋅2N) time.

Motivated by the silver version of this problem, the key idea is to assign gifts to cows in order of the cycle decomposition of the assignment, rather than in increasing order of cow label. For example, consider the assignment consisting of the pairs:

12,25,34,43,51,1→2,2→5,3→4,4→3,5→1,

where aba→b means that cow aa is assigned gift bb. This assignment decomposes into two cycles:

434,5125.4→3→4,5→1→2→5.

To avoid counting any assignment more than once, we have rotated each cycle such that its largest label comes first and sorted the cycles in increasing order of largest label. Then we would process the pairs in the following order:

43,34,51,12,25.4→3,3→4,5→1,1→2,2→5.

1. Assign cow lastlast a gift with index less than ii, extending the current cycle.
2. Assign cow lastlast the gift with index ii, completing the current cycle. Then start a new cycle.

After converting the above assignment from 1- to 0-indexing:

32,23,40,01,14,3→2,2→3,4→0,0→1,1→4,

this would correspond to the following transitions between DP states:

dpdpansdpdpdpans.dp→dp→ans→dp→dp→dp→ans.

There are O(N2N)O(N⋅2N) states and each transitions to at most NN others, yielding the desired time complexity.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 20;
uint64_t ans[1 << MAX_N];
uint64_t dp[1 << MAX_N][MAX_N];
int N;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
assert(N <= MAX_N);
for (int i = 0; i < N; ++i) {
vector<int> pref(N);
for (int &g : pref)
cin >> g;
for (int &g : pref) {
--g;
if (g == i)
break;
}
}
ans = 1;
for (int k = 0; k < N; ++k) // start a cycle
dp[1 << k][k] = 1;
for (int i = 0; i < N; ++i) {
for (int last = 0; last <= i; ++last)
if (mask & (1 << last)) {
for (int k = 0; k < i; ++k) // case 1, extend the cycle
if (!(mask & (1 << k)))
if (adj[last] & (1 << k))
dp[mask ^ (1 << k)][k] += val;
if (adj[last] & (1 << i)) // case 2, complete the cycle
}
for (int k = i + 1; k < N; ++k) // start a new cycle
}
}
int Q;
cin >> Q;
while (Q--) {
string breeds;
cin >> breeds;
int g = 0, h = 0;
for (int i = 0; i < N; ++i) {
if (breeds[i] == 'G')
g ^= 1 << i;
else
h ^= 1 << i;
}
cout << ans[g] * ans[h] << "\n";
}
}


Danny Mittal's code (which sorts the cycles in decreasing order of lowest label):

import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

static int[][] rankings;

static boolean adj(int from, int to) {
return rankings[to][from] >= rankings[to][to];
}

public static void main(String[] args) throws IOException {
rankings = new int[n][n];
for (int cow = 0; cow < n; cow++) {
for (int rank = n; rank > 0; rank--) {
rankings[cow][Integer.parseInt(tokenizer.nextToken()) - 1] = rank;
}
}
long[][] dpEndingAt = new long[n][1 << n];
long[] dpClosed = new long[1 << n];
dpClosed = 1;
for (int start = n - 1; start >= 0; start--) {
for (int mask = 1 << start; mask < 1 << n; mask += 1 << (start + 1)) {
for (int end = start; end < n; end++) {
if ((mask & (1 << end)) != 0) {
if (end == start) {
} else {
for (int last = start; last < n; last++) {
if (last != end && adj(last, end) && (mask & (1 << last)) != 0) {
}
}
}
}
}
}
}
}
StringBuilder out = new StringBuilder();
for (int q = Integer.parseInt(in.readLine()); q > 0; q--) {
for (int cow = 0; cow < n; cow++) {
if (breeds.charAt(cow) == 'G') {
} 