PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Testers: Tejas Pandey, Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
TBD
PREREQUISITES:
Observation
PROBLEM:
Given a binary string of length 2N, partition it into non-palindromic substrings or report that this is impossible.
EXPLANATION:
A trivial impossible case is when S consists of only 0's or only 1's.
In every other case, a valid partition exists: in fact, you only need 2 substrings at most.
How?
Let’s consider a few cases.
Suppose S is itself not a palindrome. Then, no more partitioning needs to be done: just take S itself.
Now we consider the case when S is a palindrome. Note that the length of S is even.
- Suppose the first half of S is not a palindrome. Then, its second half is also not a palindrome, so simply partition it into these two halves
- Otherwise, the first N characters of S form a palindrome. In this case, consider the string formed by the first N+1 characters of S: this is definitely not a palindrome.
Proof
Suppose it was a palindrome. Note that the first N characters of this string are also a palindrome. Together, this information tells us that all the characters of this substring must be the same.
However, if this were to be the case, then S being a palindrome would make all the characters of S the same, which is a contradiction since we took care of that case at the very beginning.
The exact same argument shows that the first (and hence last) N-1 characters of S also don’t form a palindrome. So, we can split S into its first N+1 and last N-1 characters to obtain a solution.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, 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;
if(!(l <= x && x <= r))
{
cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
assert(false);
}
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 readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
int main() {
int t;
t = readIntLn(1, 100000);
int smn = 0;
while(t--) {
int n;
n = readIntLn(1, 100000);
smn += n;
assert(smn <= 200000);
string s = readStringLn(2*n, 2*n);
bool same = 1;
for(int i = 0; i < 2*n; i++) assert(s[i] == '0' || s[i] == '1'), same &= (s[0] == s[i]);
if(same) {
cout << "-1\n";
continue;
}
bool is_palindrome = 1, half_palindrome = 1;
for(int i = 0; i < n; i++) is_palindrome &= (s[2*n - 1 - i] == s[i]), half_palindrome &= (s[n - 1 - i] == s[i]);
if(!is_palindrome)
cout << "1\n" << 2*n << "\n";
else if(!half_palindrome)
cout << "2\n" << n << " " << n << "\n";
else {
assert(n > 2);
cout << "2\n" << n - 1 << " " << n + 1 << "\n";
}
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
if s.count('0') == 0 or s.count('1') == 0:
print(-1)
continue
if s != s[::-1]: print(1, '\n', 2*n)
elif s[:n] != s[n-1::-1]: print(2, '\n', n, n)
else: print(2, '\n', n+1, n-1)