PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
For a binary string S, define f(S) as follows:
- |S|-1 times, delete one character from S.
Then, add to the score the number of pairs of adjacent characters that differ.
You’re given S, compute f(S).
EXPLANATION:
Let k denote the number of adjacent different characters in S.
For example, if S = \texttt{110100} then k = 3.
Let’s analyze how k changes when one character is deleted from S.
This requires a bit of casework.
Casework
- If we delete S_1,
- If S_1 = S_2, k doesn’t change at all.
- Otherwise, k decreases by 1.
- Similarly, deleting S_N reduces k by either 0 or 1, depending on whether S_N = S_{N-1} or not.
- Next, say we delete S_i for some index 1 \lt i \lt |S| (that is, some character in the middle of S).
- If S_{i-1} \neq S_{i+1}, k doesn’t change.
- If S_{i-1} = S_{i+1}, we again have two further cases:
- If S_i = S_{i-1}, k doesn’t change (this is, for example, deleting the middle element from \texttt{000}).
- If S_i \neq S_{i-1}, k reduces by 2 (this corresponds to deleting the middle element from \texttt{010}).
The important thing to note here is that no matter what, k cannot increase: it either remains the same, decreases by 1, or by 2.
To compute f(S), we repeatedly delete a character from it, update k, and add k to the score.
Our objective is to maximize this sum: and so ideally, we perform deletions that don’t change k as much as possible.
This is, in fact, always possible!
That is, we can always perform moves that don’t affect k, till we’re forced to do so - at which point every following move can reduce k by 1, till we eventually reach k = 0 exactly when the string has length 1.
Proof
First, consider the case when S is an “alternating” string, i.e, S = \texttt{010101\ldots} or S = \texttt{101010\ldots}
For such a string, we’ll have k = |S|-1.
Deleting the first (or last) character of S will reduce both |S| and k by 1, which is the best we can do.
If S is not an alternating string, S must satisfy at least one of the following:
- Every character of S is the same.
In this case, k = 0 already, and it doesn’t matter which character we delete. - S contains \texttt{001} as a substring.
Here, we can delete the middle 0, and k doesn’t change. - S contains \texttt{110} as a substring.
Here, we can delete the middle 1, and k doesn’t change.
So, if every character of S is initially the same, the moves we make don’t matter (and k is always 0).
Otherwise, we can always perform moves that don’t reduce k, till S becomes an alternating string.
For an alternating string, k is one less than the length; so any move we make is forced to reduce k as well (since k can’t be \geq |S|).
We have a way to always reduce k by exactly 1, and so that’s optimal.
This gives us a rather simple way to calculate the cost.
Let k initially be the number of adjacent different characters in S.
Then,
- The last few moves will add k-1, k-2, k-3, \ldots, 0 to our score.
This adds 0 + 1 + 2 + \ldots + (k-1) = \frac{k\cdot (k-1)}{2} to the overall total. - Every other move will add k to the score.
That’s (N-1-k) moves, for a total of (N-1-k)\cdot k.
The final answer is thus simply
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
k = 0
for i in range(n-1):
k += s[i] != s[i+1]
print((n-1-k)*k + k*(k-1)//2)
