PARTPAL - Editorial

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)
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.