PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You are given arrays A and B, of lengths N and M.
In one move, you can replace some subarray of A of length M, with a cyclic rotation of B.
Find the lexicographically minimum possible array A.
All the elements of A are distinct, as are the elements of B.
EXPLANATION:
First, it’s easy to see that if we ever do a replacement, it must be with the lexicographically minimum cyclic rotation of B.
Since the elements of B are distinct, this minimum rotation is obtained by simply rotating the array so that the minimum element of B is at the start, easily done in \mathcal{O}(M).
Our operation is now just “replace a subarray of A with B”.
Now, let’s look at how A can be minimized.
Since we’re working with lexicographic order, a simple greedy algorithm works here: for each i from 1 to N-M+1, if replacing the subarray starting at i with B is good, do it.
Of course, a direct implementation of this would take \mathcal{O}(NM) time which is too slow, so we need to be smarter about it.
Let’s analyze what’s actually going on.
For each i from 1 to N,
- If A_i \lt B_1, it’s optimal to not replace here since we’d only increase the value.
- If A_i \gt B_1, it’s optimal to replace here. Note that this will affect comparisons of following elements.
- If A_i = B_1, it may or may not be optimal to replace starting here, and we have to look at further elements to decide.
Now, observe that if we ever do perform a replacement at index i, we’ll set A_{i+1} to be B_2 (which is strictly larger than B_1).
This means it’s then optimal to perform the replacement at index i+1 as well, then at index i+2, i+3, and so on.
That is, if the first time we perform a replacement is at index L, we’ll end up performing a replacement for every valid index \geq L.
This is a useful observation because it allows us to easily simulate all the operations:
- The last M elements of A will just be B itself, as a result of the final replacement.
- For each i in the range [L, N-M+1], A_i will just equal B_1.
- Elements of A before L will be unchanged.
That is, the final array will look like
So, if L is known, the final array can easily be constructed in \mathcal{O}(N) time.
Our task is now thus just to find L quickly.
However, looking at the greedy algorithm, this is not too hard.
L will equal either the leftmost index with a value greater than B_1, or an index with a value that’s equal to B_1.
Since the elements of A are distinct, there’s at most one such index in the second case, so we only have at most two candidates for L.
This means a simple implementation is to simply find both candidates for L, generate the final array in both cases, and print the minimum among them.
Note that M = 1 is an edge case for the above solution.
However, it’s easy to handle this separately: there’s only one element in B, so it’s clearly optimal to just set every A_i to \min(A_i, B_1), i.e. replace every element of A that’s larger than B_1, by B_1.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
vector<int> a(n), b(m);
for (int &x : a) cin >> x;
for (int &x : b) cin >> x;
rotate(begin(b), ranges::min_element(b), end(b)); // Bring the smallest element of b to the front
if (m == 1) {
for (int i = 0; i < n; ++i) cout << min(a[i], b[0]) << ' ';
cout << '\n';
continue;
}
for (int i = 0; i+m <= n; ++i) {
if (a[i] < b[0]) continue;
bool replace = true;
if (a[i] == b[0]) {
replace = false;
for (int j = 0; j < m; ++j) {
if (a[i+j] == b[j]) continue;
if (a[i+j] < b[j]) break;
replace = true;
break;
}
}
if (!replace) continue;
for (int j = i; j < n; ++j)
a[j] = b[0];
for (int j = 0; j < m; ++j)
a[n-1-j] = b[m-1-j];
break;
}
for (int x : a) cout << x << ' ';
cout << '\n';
}
}
: