USACO 2022 US Open Contest, Gold Problem 2. Pair Programming

USACO 2022 US Open Contest, Gold Problem 2. Pair Programming

A program consists of a sequence of instructions, each of which is of one of the following forms:

1. ×d×d, where dd is a digit in the range [0,9][0,9]
2. +s+s, where ss is a string denoting the name of a variable. Within a program, all variable names must be distinct.

The result of executing a program is defined to be the expression that results after applying each instruction in order, starting with 00. For example, the result of executing the program [×3,+x,+y,×2,+z][×3,+x,+y,×2,+z] is the expression

(0×3+x+y)×2+z=2×x+2×y+z(0×3+x+y)×2+z=2×x+2×y+z. Different programs, when executed may produce the same expressions; for example, executing [+w,×0,+y,+x,×2,+z,×1][+w,×0,+y,+x,×2,+z,×1] would also result in the expression 2×x+2×y+z2×x+2×y+z.
Bessie and Elsie each have programs of NN (1≤N≤20001≤N≤2000) instructions.

They will interleave these programs to produce a new program of length 2N2N. Note that there are (2N)!N!×N!(2N)!N!×N! ways to do this, but not all such programs, when executed, will produce distinct expressions.

Count the number of distinct expressions that may be produced by executing Bessie and Elsie's interleaved program, modulo 109+7109+7.
Each input contains TT (1≤T≤101≤T≤10) test cases that should be solved independently. It is guaranteed that the sum of NN over all test cases does not exceed 20002000.

 

SAMPLE INPUT:

4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+1

SAMPLE OUTPUT:

1
3
9
9

For the first test case, the two possible interleaved programs are [×1,×0][×1,×0] and [×0,×1][×0,×1]. These will both produce the expression 00 when executed.

For the second test case, executing an interleaving of [×1,×2,+x][×1,×2,+x] and [+y,×0,×2][+y,×0,×2] could produce one of the expressions 00, xx, or 2×x2×x.

Problem credits: Benjamin Qi

USACO 2022 US Open Contest, Gold Problem 2. Pair Programming 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

(Analysis by Benjamin Qi)
First, discard all occurrences of ×1×1 since they don't affect the answer. Also, if a program contains an occurrence of ×0×0, discard the portion of the program before the last such occurrence.

Say that two instructions are of the same type if they are both ×d×d or both +s+s. When do two interleaved programs produce the same expression? It turns out that this happens if and only if one interleaved program can be transformed into the other by repeatedly swapping two adjacent instructions of the same type, where one of the instructions belongs to Bessie and the other belongs to Elsie.

Therefore, the number of distinct expressions is precisely the number of interleaved programs that do not contain a pair of adjacent instructions of the same type where the first instruction belongs to Elsie and the second instruction belongs to Bessie, because every such program that contains such a pair can be uniquely transformed via a series of swaps into a program that does not contain such a pair (while there exists such a pair, swap the two instructions in the pair).

The full solution involves dynamic programming on a grid. In the code below, dp[i][j][k]dp[i][j][k] is the number of ways to interleave the first ii instructions of Bessie's program with the first jj instructions of Elsie's program such that the last instruction in the interleaving belongs to Bessie if k=0k=0 or Elsie if k=1k=1. dp[i][j][k]dp[i][j][k] is used to update both dp[i][j+1][1]dp[i][j+1][1] (if Elsie adds her jj-th instruction to the end of the interleaving) and dp[i+1][j][0]dp[i+1][j][0] (if Bessie adds her ii-th instruction to the end of the interleaving) unless Elsie last added to the interleaving and the j−1j−1-th instruction of Elsie's program has the same type as the ii-th instruction of Bessie's program.
The overall time complexity is proportional to the number of DP states, which is O(N2)O(N2).

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

template <class T> using V = vector<T>;

const int MOD = 1e9 + 7;
void mod_add(int &a, int b) { a = (a + b) % MOD; }

void read(string &s) {
	string _s;
	cin >> _s;
	for (char c : _s) {
		if (c == '1') continue;
		if (c == '0') s.clear();
		if (c != '+') c = '2';
		s += c;
	}
}

int solve() {
	int N;
	cin >> N;
	string A, B;
	read(A);
	read(B);
	V<V<array<int, 2>>> dp((int)size(A) + 1,
	                       V<array<int, 2>>((int)size(B) + 1));
	int ans = 0;
	auto upd = [&](int x, int y, int k, int v) {
		if (x <= (int)size(A) && y <= (int)size(B))
			mod_add(dp.at(x).at(y).at(k), v);
	};
	dp.at(0).at(0).at(0) = 1;
	for (int i = 0; i <= (int)size(A); ++i) {
		for (int j = 0; j <= (int)size(B); ++j) {
			for (int k : {0, 1}) {
				int v = dp.at(i).at(j).at(k);
				if (v == 0) continue;
				if (i == (int)size(A) && j == (int)size(B)) mod_add(ans, v);
				else {
					upd(i, j + 1, 1, v);
					if (k == 0) upd(i + 1, j, 0, v);
					else {
						assert(j > 0);
						if (i < (int)size(A) && B.at(j - 1) != A.at(i))
							upd(i + 1, j, 0, v);
					}
				}
			}
		}
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while (T--) cout << solve() << "\n";
}