FLREV - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

There are N flowerpots, each with either a red or a blue flower, represented by binary string S.
You can reverse one segment of flowerpots if you wish.
Maximize the number of pairs of adjacent flowerpots with the same-colored flowers.

EXPLANATION:

The main observation here is that if we reverse the range [L,R], then only really the adjacencies (L-1, L) and (R, R+1) can effectively change the score.
This is because:

  • For i \lt L-1, (i, i+1) both don’t change in value anyway.
  • Similarly for i \gt R, (i, i+1) both don’t change.
  • For i \le L \lt R, the pair (i, i+1) of flowerpots will still remain adjacent to each other after the reversal - they will just move to a different location.

Thus, only (L-1, L) and (R, R+1) can possibly change anything.

Since we want to increase the number of adjacent equal values, ideally we start with L and R such that S_L \ne S_{L-1} and S_R \ne S_{R+1}, and turn them into S_L = S_{L-1} and S_R = S_{R+1}.

Note that this also means S_L \ne S_R can’t hold, since otherwise after reversing them we’d end up in the same position as before.
So, we want S_{L-1} \ne S_L \ne S_{R} \ne S_{R+1}.

Equivalently, we’re looking for two occurrences of either 10 or 01 as a substring - if we have two occurrences of 10 for example, we can reverse the part between the 0 of the first occurrence and the 1 of the second occurrence, and gain a “profit” of 2.

However, what if that’s impossible? As in, 01 and 10 both appear at most once each?

In such cases, the string is heavily constrained in form so we analyze each case:

  • 10 and 01 both don’t appear as substrings.
    • In this case the string must consist of only a single type of character. There’s no point in reversing anything.
  • Only 10 appears, or only 01 appears as a substring.
    • In this case, the string must be sorted in either ascending or descending order.
      Again, it can be verified that reversing a substring doesn’t really help us.
  • 10 and 01 both appear as substrings.
    • In this case, the string will look like either 1\ldots 10\ldots 01\ldots 1 or 1\ldots 01\ldots 10\ldots 0.
    • We can turn these two types of strings into sorted strings by reversing an appropriate prefix/suffix.
      This will improve the answer by 1.

So, putting everything together.
Let K denote the number of adjacent equal elements in the original string.

  • If either 10 or 01 appear as a substring \ge 2 times, the answer is K+2.
  • Otherwise, if both 10 and 01 appear as substrings, the answer is K+1.
  • Otherwise, the answer is K.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    
    c01, c10 = 0, 0
    k = 0
    for i in range(n-1):
        if s[i] == '0' and s[i+1] == '1': c01 += 1
        elif s[i] == '1' and s[i+1] == '0': c10 += 1
        else: k += 1
    
    if max(c01, c10) >= 2: print(k+2)
    elif min(c01, c10) >= 1: print(k+1)
    else: print(k)