Official

G - Jumping sequence Editorial by en_translator


First, we rotate the plane by \(45\) degrees, considering on the coordinate system of \((X+Y, X-Y)\). Then, the jump in each direction can be written as \((\pm D_i, \pm D_i)\) (any double sign).
Therefore, the problem boils down to finding the assignments of \(+1\) and \(-1\) to \(s_i\) and \(s'_i\) so that

\[ \displaystyle\sum_{i=1}^Ns_iD_i=A+B\quad\text{, and } \quad \displaystyle\sum_{i=1}^Ns'_iD_i=A-B. \]

Moreover, defining \(S=\displaystyle\sum_{i=1}^ND_i\) the problem boils down to finding the assignment of \(0\) and \(1\) to \(t_i\) and \(t'_i\) so that

\[ \displaystyle\sum_{i=1}^Nt_iD_i=\frac{S+A+B}{2}\quad\text{, and} \quad \displaystyle\sum_{i=1}^Nt'_iD_i=\frac{S+A-B}{2}. \]

If one of the right hand sides is negative or greater than \(S\), or is not an integer, then obviously it is unachievable.
Otherwise, the problem can be solved with a DP (Dynamic Programming) where \(dp[x][y]=(1\text{ if we can achieve }\displaystyle\sum_{i=1}^xt_iD_i=y\text{, or }0\text{ otherwise}) \). However, note that we have to compute about \(NS\) times, so we have to speed up appropriately with bitsets or \(64\)-times optimizations. Also, the recovery of sequence of operations can be done through the recovery of DP. But naively, we have to store all the bit sequences in the process. However, the space complexity required for that is \(NS\leq 2000\times (1800\times 2000)=7.2\times 10^9\) bits \((=900MB)\), which fits in the range of constraints, so the computation is possible.

Therefore, the problem has been solved. In the sample code, we did optimization by bitset with the method described above.

Sample code in C++:

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

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep3(i, a, b) for(int i = a; i >= b; i--)

int main(void) {
	int n;
	int m[2];
  
	bitset<3600001> a[2001];
	int b[2000];
	char c[4] = { 'L','U','D','R' };
  
	bool v = true;
	int x, y;
	string ans;

	cin >> n >> x >> y;
	m[0] = x + y;
	m[1] = x - y;
	x = 0;
	rep(i, n) {
		cin >> b[i];
		x += b[i];
	}
	rep(i, 2)if (abs(m[i]) > abs(x))v = false;
	rep(i, 2)if ((m[i] + x) % 2 != 0)v = false;
	if (!v) {
		cout << "No" << endl;
		return 0;
	}
	rep(i, 2)m[i] = (m[i] + x) / 2;
	a[0][0] = true;
	rep(i, 2000)a[i + 1] = a[i] | (a[i] << b[i]);
	if ((!a[n][m[0]]) || (!a[n][m[1]])) {
		cout << "No" << endl;
		return 0;
	}
	rep3(i, n - 1, 0) {
		x = 0;
		rep(j, 2) {
			if (!a[i][m[j]]) {
				m[j] -= b[i];
				x += (1 << j);
			}
		}
		ans = c[x] + ans;
	}
	cout << "Yes" << endl;
	cout << ans << endl;

	return 0;
}

posted:
last update: