PROBLEM LINK:
Setter: Shahjalal Shohag
Tester: Rahul Dugar
Editorialist: Ishmeet Singh Saggu
DIFFICULTY:
Medium
PREREQUISITES:
Ad-hoc
PROBLEM:
You are given two integer sequences A_1,A_2,…,A_N and B_1,B_2,…,B_N and an integer K. You may perform the following operation at most 3⋅N times:
- Select a contiguous subsequence of A with length K.
- Create an integer sequence S_1,S_2,…,S_K which is isomorphic to the selected subsequence i.e. for each pair of integers i and j (1≤i,j≤K), S_i=S_j must hold if A_{L−1+i}=A_{L−1+j} and S_i≠S_j must hold if A_{L−1+i}≠A_{L−1+j}. In addition, 1≤S_i≤1,000 must hold for each valid i.
- For each valid i replace A_{L−i+1} by S_i.
QUICK EXPLANATION:
- You will note that isomorphism is equivalent to mapping, so there is a bijection when applying the operation. So it doesn’t matter if you apply the operation on A or B just you have to note that all the operation applied on B will be placed in reverse order at last.
- Try to make elements of the sequence A and sequence B as distinct as possible by applying operations.
- We can make sequence A to sequence B only If each distinct element in A after the process is mapped to a distinct element of B else we cannot.
EXPLANATION:
Let’s define the “common portion”, which will be a part of all K length subarrays (might not be there when K is small). For example common portion of “acbcd” for K = 4 is “cbc” and for K = 2 there is no common part.
Also, if sequence X and Y are isomorphic then X[i...j] and Y[i...j] are also isomorphic for any 1 \leq i \leq j \leq N. So the necessary condition is that the common portions of the A and B have to be isomorphic and if it is, then it turns out that it is also the sufficient condition.
Also, you will note that isomorphism is equivalent to mapping, so there is a bijection when applying the operation. So it doesn’t matter if you apply the operation on A or B just you have to note that all the operation applied on B will be placed in reverse order at last(as you could have applied it to A in the reverse order to get to B).
Now for the construction of the solution is as follows :
- Maintain a set of unused numbers.
- Apply operation over all subarray with size K on sequence A and B.
- Suppose you are applying operation on sequence A and on subarray, A[l, ..., l+k-1] Operation will involve selecting the current subarray and replacing each element with unused numbers while maintaining the isomorphism. Also while doing the operation if the count of an element in sequence A or sequence B becomes 0 then insert it in the unused set.
set<int> unused;
vector<int> countA(1001, 0), countB(1001, 0);
for(int i = 1; i <= 1000; i ++) {
unused.insert(i);
}
for(int i = 1; i <= N; i ++) {
unused.erase(A[i]); // As this has already used
}
for(int i = 1; i <= N; i ++) {
unused.erase(B[i]); // As this has already used
}
for(int i = 1; i+k <= N; i ++) {
map<int,int> ID;
for(int j = 0; j < k; j ++) {
nums[A[i+j]] = -1;
}
for(auto &it : ID) {
it.second = *unused.begin(); // assigning new IDs while maintaining the isomorphism.
unused.erase(unused.begin());
}
for(int j = 0; j < k; j ++) {
countA[A[i+j]] --;
if(countA[A[i+j]] == 0) {
unused.insert(A[i+j]);
}
A[i+j] = ID[A[i+j]];
countA[A[i+j]] ++;
}
}
for(int i = 1; i+k <= N; i ++) {
map<int,int> ID;
for(int j = 0; j < k; j ++) {
nums[B[i+j]] = -1;
}
for(auto &it : ID) {
it.second = *unused.begin(); // assigning new IDs while maintaining the isomorphism.
unused.erase(unused.begin());
}
for(int j = 0; j < k; j ++) {
countB[B[i+j]] --;
if(countB[B[i+j]] == 0) {
unused.insert(B[i+j]);
}
B[i+j] = ID[B[i+j]];
countB[B[i+j]] ++;
}
}
- What you are trying to do is trying to make elements of the sequence A and B as distinct as possible and in the worst case it will take 2*N operations
- Now we can make sequence A to sequence B only If each distinct element in A after the process is mapped to a distinct element of B else we cannot. You can check that by iterating over the range [1, K], [K+1, 2*K] … and checking if they follow isomorphism or not and if yes convert that particular segment to the segment of B by doing an operation and in the worst case, the whole process will take N operations.
vector<vector<int>> total_operation;
for(int i=1; i <= N; i += K) {
vector<int> single_operation;
int start = min(i, N-K+1);
map<int,int> A_to_B;
map<int,int> B_to_A;
for(int j = start; j <= start+K-1; j ++) {
if(A_to_B.find(A[j]) != A_to_B.end() && A_to_B[A[j]] != B[j]) {
cout << "NO" << endl;
return;
}
if(B_to_A.find(B[j]) != B_to_A.end() && B_to_A[B[j]] != A[j]) {
cout << "NO" << endl;
return;
}
B_to_A[B[j]] = A[j];
A_to_B[A[j]] = B[j];
A[j] = B[j];
single_operation.push_back(A[j]); // storing operation.
}
total_operation.push_back(operation);
}
- Order of printing the operation will be as, first all the operation we have done to make elements of A as distinct as possible, then conversion of A to B(after both sequences are processed to have elements as distinct as possible), then all the operation of making elements of B as distinct as possible in reverse order.
TIME COMPLEXITY:
- Time complexity per testcase is O(N^2*log(N)),
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
vector<int> transform(vector<int> a) {
map<int, int> last;
int n = a.size();
vector<int> b(n, 0);
for (int i = 0; i < n; i++) {
if (last.find(a[i]) != last.end()) {
b[i] = i - last[a[i]];
}
last[a[i]] = i;
}
return b;
}
bool is_isomorphic(vector<int> a, vector<int> b) {
return transform(a) == transform(b);
}
set<int> can;
vector<pair<int, vector<int>>> distinctify(int n, int k, vector<int> &a, bool rev = 0) {
vector<pair<int, vector<int>>> states;
for (int i = 0; i + k <= n; i++) {
if (rev) {
states.push_back({i + 1, vector<int>(a.begin() + i, a.begin() + i + k)});
}
map<int, int> mp;
for (int j = i; j < i + k; j++) {
mp[a[j]] = 69;
}
auto it = can.begin();
for (auto &x: mp) {
x.second = *(it++);
}
for (int j = i; j < i + k; j++) {
a[j] = mp[a[j]];
}
can.erase(a[i]);
if (!rev) {
states.push_back({i + 1, vector<int>(a.begin() + i, a.begin() + i + k)});
}
}
if (rev) {
reverse(states.begin(), states.end());
}
return states;
}
vector<pair<int, vector<int>>> convert(int n, int k, vector<int> a, vector<int> b) {
vector<pair<int, vector<int>>> states;
for (int i = 0; i + k <= n; i++) {
map<int, int> mp;
for (int j = i; j < i + k; j++) {
a[j] = b[j];
}
states.push_back({i + 1, vector<int>(a.begin() + i, a.begin() + i + k)});
}
return states;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t--) {
int n, k; cin >> n >> k;
can.clear();
for (int i = 1; i <= 1000; i++) {
can.insert(i);
}
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
can.erase(a[i]);
}
vector<int> b(n);
for (int i = 0; i < n; i++) {
cin >> b[i];
}
auto states1 = distinctify(n, k, a);
can.clear();
for (int i = 1; i <= 1000; i++) {
can.insert(i);
}
for (int i = 0; i < n; i++) {
can.erase(a[i]);
can.erase(b[i]);
}
auto states2 = distinctify(n, k, b, 1);
if (is_isomorphic(a, b)) {
auto cur = convert(n, k, a, b);
cout << "YES\n";
cout << states1.size() + cur.size() + states2.size() << '\n';
for (auto x: states1) {
cout << x.first << ' ';
for (auto y: x.second) {
cout << y << ' ';
}
cout << '\n';
}
for (auto x: cur) {
cout << x.first << ' ';
for (auto y: x.second) {
cout << y << ' ';
}
cout << '\n';
}
for (auto x: states2) {
cout << x.first << ' ';
for (auto y: x.second) {
cout << y << ' ';
}
cout << '\n';
}
}
else {
cout << "NO\n";
}
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int a[105],b[105];
int cntr[1005];
int ii=0;
void solve() {
ii++;
memset(cntr,0,sizeof(cntr));
int n=readIntSp(1,100),k=readIntLn(1,n);
set<int> avl;
fr(i,1,1000)
avl.insert(i);
vector<vi> ops;
fr(i,1,n) {
if(i!=n)
a[i]=readIntSp(1,1000);
else
a[i]=readIntLn(1,1000);
cntr[a[i]]++;
avl.erase(a[i]);
}
fr(i,1,n) {
if(i!=n)
b[i]=readIntSp(1,1000);
else
b[i]=readIntLn(1,1000);
cntr[b[i]]++;
avl.erase(b[i]);
}
fr(i,1,n-k+1) {
map<int,int> tol;
rep(j,i,i+k) {
tol[a[j]]=0;
cntr[a[j]]--;
if(cntr[a[j]]==0)
avl.insert(a[j]);
}
for(auto &it:tol) {
it.se=*avl.begin();
avl.erase(avl.begin());
}
vi op={i};
rep(j,i,i+k) {
a[j]=tol[a[j]];
op.pb(a[j]);
cntr[a[j]]++;
}
ops.pb(op);
}
vector<vi> op2;
fr(i,1,n-k+1) {
map<int,int> tol;
rep(j,i,i+k) {
tol[b[j]]=0;
cntr[b[j]]--;
if(cntr[b[j]]==0)
avl.insert(b[j]);
}
for(auto &it:tol) {
it.se=*avl.begin();
avl.erase(avl.begin());
}
vi op={i};
rep(j,i,i+k) {
op.pb(b[j]);
b[j]=tol[b[j]];
cntr[b[j]]++;
}
op2.pb(op);
}
reverse(all(op2));
for(int i=1; i<=n; i+=k) {
int star=min(i,n-k+1);
vi op={star};
map<int,int> poo;
map<int,int> ulta;
rep(j,star,star+k) {
if(poo.find(a[j])!=poo.end()&&poo[a[j]]!=b[j]) {
cout<<"NO"<<endl;
return;
}
if(ulta.find(b[j])!=ulta.end()&&ulta[b[j]]!=a[j]) {
cout<<"NO"<<endl;
return;
}
ulta[b[j]]=a[j];
poo[a[j]]=b[j];
a[j]=b[j];
op.pb(a[j]);
}
ops.pb(op);
}
for(auto i:op2)
ops.pb(i);
cout<<"YES"<<endl<<sz(ops)<<endl;
for(auto i:ops) {
for(auto j:i)
cout<<j<<" ";
cout<<endl;
}
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(8);
int t=1;
// cin>>t;
t=readIntLn(1,100);
fr(i,1,t)
solve();
// assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
return 0;
}
VIDEO EDITORIAL:
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. 
