PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Anton Trygub
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
2585
PREREQUISITES:
None
PROBLEM:
For an array A of N integers, define:
- An array P of length N, where P_i is the number of distinct elements in the subarray A[1:i] of A.
- An array S of length N, where S_i is the number of distinct elements in the subarray A[i:N] of A.
You are given arrays P and S. Determine whether there exists an array A corresponding to the given P and S arrays.
EXPLANATION:
There are some preliminary checks to be done on P and S:
- For every 1 < i \le N, P_{i - 1} \le P_i \le P_{i - 1} + 1.
- For every 1 < i \le N, S_i \le S_{i - 1} \le S_i + 1.
- P_1 = 1.
- S_N = 1.
- P_N = S_1.
After we are done with all of these checks, let’s classify each element i based on its P_i - P_{i - 1} and S_i - S_{i + 1}. We have four types: 00, 01, 10, and 11 (where the first number is P_i - P_{i - 1}, and the second number of S_i - S_{i + 1}). Let’s try to reconstruct A knowing the types of each element. We have the following observations:
- 11 are very easy to handle: they are unique values, so we can simply ignore them.
- We know that the amount of 10 and 01 are the same (since P_N = S_1).
- Suppose the array only consists of 10 and 01 elements. We know that each 10 element represents a value that isn’t seen before but is present after this element (and hence there must be some 01 elements going after it); similarly, each 01 represents a value that isn’t seen after but is present before this element (and hence there must be some 10 elements going before it). Therefore, our idea is to match each 10 with a later 01. Indeed, if we are able to match this, then we can construct the array by putting the same value for matched pairs. We can represent this matching problem in even simpler terms: let 10 be a
(character and 01 be a)character, then the bracket sequence must be correct. - Now we add back in 00 elements. Let’s consider these elements as the
.characters. I claim that each.character must be in a position where up until this position, there still exists some unmatched(character. For example,(.)(.)is good because at each., there are some unmatched(characters, while().()is bad because.is in a region where all bracket characters before it are matched. This is true because if there exists some unmatched(characters, we can simply let the value of the.character to be the same as this unmatched(character. Otherwise if all brackets are matched,.is a “unique” value, and therefore should have been a 11 element insteaed.
These observations directly lead to the solution: simply let 01, 10, and 00 be (, ), and . respectively, and check against the conditions listed in the observations.
TIME COMPLEXITY:
Time complexity is O(N) for each test case.
SOLUTION:
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e6+1;
int n,k;
int a[N],b[N];
bool solve(){
cin >> n;
for(int i=1; i<=n ;i++) cin >> a[i];
for(int i=1; i<=n ;i++) cin >> b[i];
b[n+1]=0;
for(int i=1; i<=n ;i++){
if(a[i]-a[i-1]<0 || a[i]-a[i-1]>1) return false;
}
for(int i=n; i>=1 ;i--){
if(b[i]-b[i+1]<0 || b[i]-b[i+1]>1) return false;
}
if(a[n]!=b[1]) return false;
if(a[1]!=1 || b[n]!=1) return false;
for(int i=1; i<=n ;i++){
if(a[i]+b[i]<=a[n]) return false;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
int t;cin >> t;
while(t--){
bool res=solve();
if(res) cout << "YES\n";
else cout << "NO\n";
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> p(n), s(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
}
for (int i = 0; i < n; i++) {
cin >> s[i];
}
bool ok = true;
if (p[0] == 1 && s[n - 1] == 1 && p[n - 1] == s[0]) {
int cur = 0;
for (int i = 0; i < n; i++) {
int cp = p[i] - (i == 0 ? 0 : p[i - 1]);
int cs = s[i] - (i + 1 == n ? 0 : s[i + 1]);
if (cp < 0 || cp > 1 || cs < 0 || cs > 1) {
ok = false;
break;
}
if (cp == 1 && cs == 0) {
cur++;
} else if (cp == 0 && cs == 1) {
if (cur-- == 0) {
ok = false;
break;
}
} else if (cp == 0 && cs == 0) {
if (cur == 0) {
ok = false;
break;
}
}
}
} else {
ok = false;
}
cout << (ok ? "YES\n" : "NO\n");
}
}