PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: hellolad
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
Given N and K, construct two strings S and T of length N such that:
- Each character of S and T is one of \{\texttt{A, B, C}\}.
- S_i \neq S_{i+1} and T_i \neq T_{i+1} for each valid index i.
- \text{LCS}(S, T) = K, where \text{LCS}(S, T) denotes the longest common subsequence between S and T.
EXPLANATION:
The condition that adjacent characters can’t be equal is really the main restriction here: without it, trivial solutions exist - for example
would be a valid construction otherwise.
This condition is so strong in fact that it makes sure that no matter what, the LCS of S and T is quite large.
Specifically, if S and T are ABC-strings of length N with no adjacent equal characters, then \text{LCS}(S, T) \geq \left\lfloor \frac{N}{2} \right\rfloor.
Proof
Let’s look at the first two characters of both strings, i.e. the characters S_1, S_2, T_1, T_2.
These are four characters, but they can only take three distinct values.
So, some two of them must be equal.It can’t be S_1 and S_2 since they’re adjacent, and similarly it can’t be T_1 and T_2 since they’re adjacent.
This means the only possibility is that one of (S_1, S_2) equals one of (T_1, T_2).
Either way, we have at least one match in the first two characters.The same applies to the third and fourth characters, then the fifth and sixth, and so on.
Simply taking these single-character matches gives us a common subsequence of length \left\lfloor \frac{N}{2} \right\rfloor, so the longest common subsequence certainly cannot be smaller than that.
If K \lt \left\lfloor \frac{N}{2} \right\rfloor then we can immediately say that no solution exists.
For K = \left\lfloor \frac{N}{2} \right\rfloor, we have the following construction:
Here the only common subsequence is of the form BBB\ldots, and the maximum length of such a subsequence is \left\lfloor \frac{N}{2} \right\rfloor.
For K \gt \left\lfloor \frac{N}{2} \right\rfloor, one simple construction is to just set S_1 = T_1 and then solve for (N-1, K-1).
Essentially, make some prefix of S and T equal till you reach the point where exactly half of the remaining characters must form the LCS, then mimic the above construction.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
if k < n//2:
print(-1)
continue
chars = 'ABC'
s, t = '', ''
cur_n = n
for i in range(n):
if k == cur_n//2:
for j in range(i, n):
if (i-j)%2 == 1:
s += chars[(i+2)%3]
t += chars[(i+2)%3]
else:
s += chars[(i+1)%3]
t += chars[(i)%3]
break
else:
s += chars[i%3]
t += chars[i%3]
k -= 1
cur_n -= 1
print(s)
print(t)
Tester's code (C++)
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define vi vector<int>
using namespace std;
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;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
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);
}
}inp;
int smn = 0;
void solve()
{
int n = inp.readInt(1,1000);
inp.readSpace();
int k = inp.readInt(0,n);
inp.readEoln();
smn += n;
if(k < n/2){
cout << "-1\n";
return;
}
string s;
repin{
s.push_back('A' + (i&1));
}
if(k == n/2){
string t = s;
repin{
if(s[i] == 'A')t[i] = 'C';
}
cout << s << " " << t << "\n";
}
else{
string t = s;
int left = k - (n-n/2);
for(auto &x : t){
if(x == 'B')x = 'C';
}
rep(i,0,left){
t[2*i+1] = 'B';
}
cout << s << "\n" << t << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = inp.readInt(1,1000);
inp.readEoln();
while(t--)
solve();
inp.readEof();
assert(smn <= 1000);
return 0;
}