PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: sumaiya1903045
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
You’re given two strings A and B, and a parameter K.
You can do the following:
- Choose a substring of A of length K and a character \alpha, and set every character in this substring to \alpha.
Find a sequence of at most 2N moves that turns A into B, or decide that this is impossible.
EXPLANATION:
If A = B initially, nothing needs to be done.
Otherwise, we definitely need at least one operation to achieve our goal.
Suppose a valid sequence of operations exists.
In particular, look at the last operation in this sequence: some substring of length K has all its elements set to the same character.
But, the final string must equal B. This means B itself must contain a substring of length K whose characters are all the same - otherwise it’s definitely impossible to make A equal B, since we don’t have a valid final operation.
So, we consider only the case where B does have a substring of length K containing the same character.
Fix one such substring, say starting at index L.
Let’s try to make A equal to B from left to right.
- If A_1 = B_1 already, great.
Otherwise, we have no choice but to use an operation at index 1 with the character B_1. - Next, we want to make A_2 = B_2, without affecting A_1.
The simplest way to do this, is to perform an operation at index 2 with the character B_2. - Similarly, we can then perform an operation at index 3 with B_3, then at index 4 with B_4, and so on.
If we perform this process as long as we can (i.e. as long as it’s possible to choose a length K substring), we’ll eventually make the first N-K+1 characters of A and B equal - we only need to deal with the remaining K-1 characters now (which form a suffix).
Note that the above process can also be performed in reverse instead: that is, fix A_N = B_N by operating on the substring ending at index N, then make A_{N-1} = B_{N-1}, and so on.
Here’s the neat part: we can stop the reverse process as soon as we operate on the substring starting at index L, and A and B will be equal!
Why?
Recall that L was chosen so that the substring of B starting at index L of length K has all its characters equal, that is, B_L = B_{L+1} = B_{L+2} = \ldots = B_{L+K-1}.
Our initial forward motion ensured that A_i = B_i for all i \lt L.
Our backward motion, since it stopped here, ensured that A_i = B_i for all i \geq L+K-1.
Since the last move was at index L, and the length K substring of B starting here has all its characters equal, the characters at indices between L and L+K-1 are also correctly set.
This takes care of every index!
So, as long as B contains a length K substring consisting of the same character, we’re always able to make A = B.
Note that the above process uses \leq 2N moves because we have one pass forward and one backward.
It’s also quite easy to optimize this to \leq N moves (the forward pass can be stopped at L too), though that isn’t needed to obtain AC.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, k; cin >> n >> k;
string s, t; cin >> s >> t;
if (s == t){
cout << 0 << "\n";
return;
}
vector <int> ps(n);
for (int i = 1; i < n; i++){
ps[i] = ps[i - 1] + (t[i] != t[i - 1]);
}
int x = k;
for (int i = 0; i < n; i++){
int j = i + k - 1;
if (j >= n) continue;
if (ps[j] == ps[i]){
vector <pair<int, int>> vec;
for (int k = 0; k < i; k++){
vec.push_back({k, t[k]});
}
for (int k = n - 1; k > j; k--){
vec.push_back({k - x + 1, t[k]});
}
vec.push_back({i, t[i]});
cout << vec.size() << "\n";
for (auto [x, y] : vec) cout << (x + 1) << " " << (char)y << "\n";
return;
}
}
cout << -1 << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
void solve(istringstream cin) {
int n, x;
cin >> n >> x;
string s, t;
cin >> s >> t;
if (s == t) {
cout << 0 << '\n';
return;
}
for (int i = 0, j = 0; i < n; i = j) {
while (j < n && t[i] == t[j]) {
j++;
}
if (j - i >= x) {
cout << n - x + 1 << '\n';
for (int k = 0; k < i; k++) {
cout << k + 1 << " " << t[k] << '\n';
}
for (int k = n - x; k >= i; k--) {
cout << k + 1 << " " << t[k + x - 1] << '\n';
}
return;
}
}
cout << -1 << '\n';
}
////////////////////////////////////////
#define IGNORE_CR
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
res += buffer[pos];
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1e4);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(2, 2e5);
in.readSpace();
int x = in.readInt(2, n);
in.readEoln();
sn += n;
auto s = in.readString(n, n, in.lower);
in.readEoln();
auto t = in.readString(n, n, in.lower);
in.readEoln();
ostringstream sout;
sout << n << " " << x << '\n';
sout << s << '\n';
sout << t << '\n';
solve(istringstream(sout.str()));
}
cerr << sn << endl;
assert(sn <= 2e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, x = map(int, input().split())
s = input()
t = input()
if s == t:
print(0)
continue
freq = [0]*26
st = -1
for i in range(n-x+1):
if i == 0:
for j in range(x): freq[ord(t[j]) - ord('a')] += 1
else:
freq[ord(t[i-1]) - ord('a')] -= 1
freq[ord(t[i+x-1]) - ord('a')] += 1
if max(freq) == x: st = i
if st == -1:
print(-1)
continue
print(n-x+1)
for i in range(st): print(i+1, t[i])
for i in reversed(range(st, n-x+1)): print(i+1, t[i+x-1])
