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:

  • The original assignment: cow 11 receives gift 11, cow 22 receives gift 22, cow 33 receives gift 33, and cow 44 receives gift 44.
  • Cow 11 receives gift 11, cow 22 receives gift 33, cow 33 receives gift 22, and cow 44 receives gift 44.

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:

 

(p,i)=(the number of cows assigned,the bitmask of gifts assigned),(p,i)=(the number of cows assigned,the bitmask of gifts assigned),

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;

uint64_t solve_adj(const vector<int> &new_adj) {
	const int N = (int)size(new_adj);
	vector<uint64_t> dp(1 << N);
	dp[0] = 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 adj[MAX_N];
int N;

uint64_t solve_subset(int mask) {
	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);
		vector<int> new_adj(size(bits));
		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]))
					new_adj[i] ^= 1 << j;
		ans[mask] = solve_adj(new_adj);
	}
	return ans[mask];
}

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;
			adj[i] |= 1 << 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.

Let dp[mask][last]dp[mask][last], where the highest set bit of maskmask is ii and mask&(1last)0mask&(1≪last)≠0, represent the state where all cows in mask(1last)mask⊕(1≪last) and all gifts in mask(1i)mask⊕(1≪i) have been paired up, and we are assigning a gift to cow lastlast next. From this state, we can either

 

  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:

 

dp[8][3]dp[12][2]ans[12]dp[28][4]dp[29][0]dp[31][1]ans[31].dp[8][3]→dp[12][2]→ans[12]→dp[28][4]→dp[29][0]→dp[31][1]→ans[31].

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 adj[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;
			adj[i] |= 1 << g;
			if (g == i)
				break;
		}
	}
	ans[0] = 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 mask = 1 << i; mask < 1 << (i + 1); ++mask) {
			for (int last = 0; last <= i; ++last)
				if (mask & (1 << last)) {
					const uint64_t val = dp[mask][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
						ans[mask] += val;
				}
			for (int k = i + 1; k < N; ++k) // start a new cycle
				dp[mask ^ (1 << k)][k] += ans[mask];
		}
	}
	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.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class RedistributingGiftsGold {
    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 {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        rankings = new int[n][n];
        for (int cow = 0; cow < n; cow++) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            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[0] = 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) {
                            dpEndingAt[end][mask] = dpClosed[mask - (1 << end)];
                        } else {
                            for (int last = start; last < n; last++) {
                                if (last != end && adj(last, end) && (mask & (1 << last)) != 0) {
                                    dpEndingAt[end][mask] += dpEndingAt[last][mask - (1 << end)];
                                }
                            }
                        }
                    }
                    if (adj(end, start)) {
                        dpClosed[mask] += dpEndingAt[end][mask];
                    }
                }
            }
        }
        StringBuilder out = new StringBuilder();
        for (int q = Integer.parseInt(in.readLine()); q > 0; q--) {
            String breeds = in.readLine();
            int guernseyMask = 0;
            int holsteinMask = 0;
            for (int cow = 0; cow < n; cow++) {
                if (breeds.charAt(cow) == 'G') {
                    guernseyMask += 1 << cow;
                } else {
                    holsteinMask += 1 << cow;
                }
            }
            out.append(dpClosed[guernseyMask] * dpClosed[holsteinMask]).append('\n');
        }
        System.out.print(out);
    }
}

[/hide]

翰林国际教育资讯二维码