# PARTPAL - Editorial

Author: Jeevan Jyot Singh
Testers: Tejas Pandey, Hriday
Editorialist: Nishank Suresh

TBD

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, ' '); }
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[n - 1] = readIntLn(l, r);
return a;
}

// -------------------- Input Checker End --------------------

int main() {
int t;
int smn = 0;
while(t--) {
int n;
smn += n;
assert(smn <= 200000);
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)

1 Like

Very nice problem.

I wasn’t able to come up with this approach in the contest, But I considered all possible partitioning in which we partition string in two parts.
I checked if the partitioning is valid or not using hashing in O(1) .

Here is my solution.
https://www.codechef.com/viewsolution/77702859

Now after reading editorial, it seems not very hard. Also missed reading the part where it was written N will be even. Nice problem overall

1 Like

Yes, I also missed that the length is always even. Because of that, I was considering 00100 which is impossible to make a valid partition.