Consider two adjacent cows in the original lineup. If they are both John cows, they will both say they are next to a John cow. If one of them is Nhoj cow and the other is John cow, the Nhoj cow will lie and say they are next to a Nhoj cow. The John cow will truthfully say they are next to a Nhoj cow. If they are both Nhoj cows, they will both lie and say they are next to John cows.
In particular, if the cows are from the same farmer they will both say the other cow is a John cow and if they are from different farmers, they will both say the other cow is a Nhoj cow.
Let the type of a cow be defined as what they say about the cow to the left and right of them. Notice that all of cows of the same type can be treated interchangeably.
To solve the decision version of the problem we should aim to come up with some necessary and sufficient conditions.
Note that one consequence of the aforementioned conditions is that the number of type 'JN' cows and 'NJ' cows will be equal because there are an equal number of 'J's in both strings.
These conditions are all necessary. The proof in sufficiency will come in the form of the construction. We can use the conditions to solve the $C = 0$ subtask.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define nl '\n'
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t, c; cin >> t >> c;
while (t--) {
int n; cin >> n;
string a, b; cin >> a >> b;
vi cnt[2][2];
FOR(i, 0, n) {
cnt[a[i] == 'N'][b[i] == 'N'].push_back(i);
}
bool ans = count(all(a), 'J') == count(all(b), 'J')
and count(all(a), 'N') % 2 == 0
and (cnt[0][0].empty() or cnt[1][1].empty() or sz(cnt[0][1]) or sz(cnt[1][0]));
if (ans) cout << "YES" << nl;
else cout << "NO" << nl;
}
}
First, if there are only cows of type 'JJ', we can assign every cow to be from farmer John and put them in any order. Similarly, if there are only cows of type 'NN', we can put them in any arbitrary order and just alternate the farmer string.
Otherwise we can do the following construction. First place all cows of type 'JJ' next to each other and assign them to farmer John.
Then place one cow of type 'JN' to the right of this group and assign it to farmer John. This cow with truthfully report that the cow to their left is a John cow.
Then place all cows of type 'NN' to the right of the one 'JN' cow. Because they say the cows next to them are from farmer Nhoj, their farmers must alternate. The first type 'NN' cow will be a Nhoj cow so that the 'JN' cow truthfully reports the cow to their right is a Nhoj cow.
Because the number of 'JN' and 'NJ' cows are equal, the number of remaining cows should have one more 'NJ' cow (because one 'JN' cow was already used).
We can add as many groups as we possible of one 'NJ' cow followed by one 'JN' cow. In each of these groups, they say the other cow is a John cow so we know they are of the same farmer. Additionally, they have a different farmer than the previous cow because the 'NJ' implies the previous cow was of a different type.
Then we can add the last cow of type 'NJ' with the opposite farmer as the previous cow. Note that this will be farmer John because the farmer switches once for each type 'NN' cow and once for each type 'JN' cow and there are an even number of 'N's total. Thus this last cow can truthfully report the cow to its right is a John cow (part of the first 'JJ' block).
Because this construction is always valid, the conditions are sufficient.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define nl '\n'
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t, c; cin >> t >> c;
while (t--) {
int n; cin >> n;
string a, b; cin >> a >> b;
vi cnt[2][2];
FOR(i, 0, n) cnt[a[i] == 'N'][b[i] == 'N'].push_back(i);
bool ans = count(all(a), 'J') == count(all(b), 'J')
and count(all(a), 'N') % 2 == 0
and (cnt[0][0].empty() or cnt[1][1].empty() or sz(cnt[0][1]) or sz(cnt[1][0]));
if (ans) cout << "YES" << nl;
else cout << "NO" << nl;
if (!c or !ans) continue;
vi p;
if (sz(cnt[0][0]) == n or sz(cnt[1][1]) == n) {
FOR(i, 0, n) p.push_back(i);
} else {
FOR(i, 0, sz(cnt[0][0])) p.push_back(cnt[0][0][i]);
p.push_back(cnt[0][1].back()); cnt[0][1].pop_back();
FOR(i, 0, sz(cnt[1][1])) p.push_back(cnt[1][1][i]);
while (sz(cnt[0][1]) and sz(cnt[1][0])) {
p.push_back(cnt[1][0].back()); cnt[1][0].pop_back();
p.push_back(cnt[0][1].back()); cnt[0][1].pop_back();
}
p.push_back(cnt[1][0].back());
}
FOR(i, 0, n) cout << p[i] + 1 << " \n"[i == n - 1];
int l = 0;
cout << "J";
FOR(i, 1, n) {
if (a[p[i]] == 'N') l = 1 - l;
cout << "JN"[l];
}
cout << nl;
}
}
Remark: This problem can be characterized as finding an euler path on the graph with nodes 'N' and 'J' with each cow being an edge 'NN', 'NJ', 'JN', or 'JJ' which can make the implementation more straightforward. However, this is outside the scope of silver.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define nl '\n'
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t, c; cin >> t >> c;
while (t--) {
int n; cin >> n;
string a, b; cin >> a >> b;
vector<vector<array<int, 2>>> g(2);
int cnt[2][2] = {};
FOR(i, 0, n) {
int u = a[i] == 'N', v = b[i] == 'N';
g[u].push_back({v, i});
cnt[u][v]++;
}
bool ans = count(all(a), 'J') == count(all(b), 'J')
and count(all(a), 'N') % 2 == 0
and (!cnt[0][0] or !cnt[1][1] or cnt[0][1] or cnt[1][0]);
if (ans) cout << "YES" << nl;
else cout << "NO" << nl;
if (!c or !ans) continue;
int st = sz(g[0]) ? 0 : 1;
vi p;
auto dfs = [&] (auto dfs, int u) -> void {
while (sz(g[u])) {
auto [v, i] = g[u].back();
g[u].pop_back();
dfs(dfs, v);
p.push_back(i);
}
};
dfs(dfs, st);
reverse(all(p));
FOR(i, 0, n) cout << p[i] + 1 << " \n"[i == n - 1];
int l = 0;
cout << "J";
FOR(i, 1, n) {
if (a[p[i]] == 'N') l = 1 - l;
cout << "JN"[l];
}
cout << nl;
}
}