PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Hiroto Sekido
Editorialist: Kevin Atienza
DIFFICULTY:
EASY
PREREQUISITES:
Ad hoc, string processing, greedy
PROBLEM:
Given a string s of length n consisting of letters B and G, and an integer called type (which can only be 0, 1 or 2). You need to rearrange the letters so that no two adjacent positions contain the same letter. The only valid moves are swaps between two positions, and the cost of swapping positions i and j is equal to |i-j|type.
QUICK EXPLANATION:
-
There are only two strings with no adjacent same letters, so we try each string t and check if it is possible to transform s to t.
-
We solve the problem differently for each value of type.
-
When type = 0, the cost of swapping numbers is always 1. The answer is simply the number of positions where s and t differ, divided by two.
-
It is never beneficial to swap to positions containing the same letter. Thus the relative ordering of the
Gs andBs will stay the same, and one can easily compute the final position of each letter. -
When type = 1, one can show that there is always a solution involving only swaps of adjacent elements. From this, one can show that the answer is just the sum of the distances of each letter to its final position, divided by two.
-
When type = 2 (and also, when type > 2), one can also show that the answer is the same as for type = 1.
EXPLANATION:
Throughout this explanation, we will use zero-based indexing, so the first letter of s is s0, and the last is sn-1.
Let’s call a string likable if no two adjacent positions contain the same letter. Notice that there are only two likable strings of length n: one starting with G (GBGBGB...) and one starting with B (BGBGBG...).
We are only rearranging the letters in s, so the number of Gs and Bs will not change. This means that if the number of Gs and Bs do not match any of the likable strings above, then we immediately know that the task is impossible, so we can already output -1. On the other hand, if the numbers match at least one likable string t, then it’s always possible to rearrange s into t, because any permutation can be decomposed into a series of swaps. So the answer in the latter case is the minimum cost of rearranging from s to any likable string t. There are only two t’s to check, so in what follows, we fix the likable string t.
We have reduced the problem into finding the minimum cost of rearranging s into t. Notice that the cost is dependent on type, and the cost function for each type are somewhat different from one another, so we will need to make a separate solution for each of the possible values of type. We start with type = 0.
Making a string likable, when type = 0
If type = 0, then the cost of swapping positions i and j is equal to |i-j|0, or simply 1. This means that we are simply trying to minimize the number of swaps needed to transform s into t 
A greedy algorithm can be used for this purpose. Let D be the number of positions where s and t differ. Then s and t are equal if and only if D = 0. But there are a couple more observations:
-
D is the number of positions i such that either (1) si =
Gand ti =B, or (2) si =Band ti =G. But s and t have the same number ofGs andBs, so the number of positions that satisfy (1) must be equal to the number of positions that satisfy (2) (why?). It follows that D is even. - Notice that whenever we swap two elements in the string, we can only reduce D by at most 2. Therefore, the minimum number of swaps is at least D/2.
- On the other hand, it is always possible to transform s into t in D/2 steps: Select a position i that satisfies (1) and a position j that satisfies (2), and swap si and sj. This reduces D by two, so one can repeat this process D/2 times and D will become zero.
These observations simply say that the answer is half the number of positions where s and t differ! Thus, this can be computed in O(n) time with a simple loop, and a single division at the end. The following pseudocode illustrates this:
def min_cost_type_0(s, t):
ans = 0
for i from 0 to n - 1
if s[i] != t[i]
ans += 1
return ans / 2
It is easy to see that this runs in O(n) time.
Making a string likable, when type = 1
Next, let’s move on to the case where type = 1. This time, the cost of swapping positions i and j is |i-j|1 = |i-j|, or simply the distance between the positions i and j.
First, note that we can simulate any swap of cost 2 with two swaps of cost 1. For example, suppose we want to swap positions 1 and 3 in the string BBG (which yields GBB). Then we can instead swap positions 2 and 3 to get BGB, and then positions 1 and 2 to get GBB. If instead the string was BGG, then we can swap positions 1 and 2, and then 2 and 3, to get the desired GGB. Similar replacements can be done for strings GBB and GGB. Therefore, we don’t have to consider swaps of cost 2 anymore.
In fact, we can extend the above argument to show how to simulate any swap of cost k with k swaps of cost 1! For example, suppose we want to swap positions 1 and k+1 in the string B???????G (let’s say the B is in position 1 and the G is in position k+1, and we don’t know about the values of the ?s). Also, suppose that we have already shown that swaps of costs k’ < k can be replaced with k’ swaps of cost 1 (induction). We then handle two cases, depending on the letter on position k (second-to-last letter):
-
If the letter on position k is a
B, then we want to transformB??????BGtoG??????BB. One can first swap positions k and k+1 to getB??????GB, and then swap positions 1 and k to get the desiredG??????BB. The following illustrates it:B??????BG || B??????GB | | G??????BB
However, the second swap only costs k-1, so we can replace it with k-1 swaps of cost 1. The result is k swaps of cost 1 which performs exactly what we want.
-
If the letter on position k is a
G, then we want to transformB??????GGtoG??????GB. One can first swap positions 1 and k to getG??????BG, and then swap positions 1 and k to get the desiredG??????GB. The following illustrates it:B??????GG | | G??????BG || G??????GB
Once again, we replace the first swap with swaps of cost 1 because it only costs k-1.
The case G???????B can be handled similarly. Thus, it is always possible to replace any valid solution by a series of adjacent swaps (swaps of adjacent elements) without increasing the cost, so we may simply restrict ourselves to swaps of cost 1.
Using only adjacent swaps
We now wish to find the minimum number of swaps needed to transform s to t, if only adjacent swaps are allowed. Let’s only handle the case where t starts with a G (the other case is essentially the same).
The first observation is that it is never beneficial to swap two positions if they contain the same element. Thus, the relative orders of all the Bs with each other will stay the same throughout. The same is true for the Gs. This means the following:
- we already know where each letter will end up in the final array: the i’th
B(i \ge 0) in s will end up at position 2i+1 in t and the i’thGin s will end up at position 2i in t . Let’s denote by f_j the final position of sj. - we also know how many steps at the minimum each letter will move: since sj will end up at position f_j, it has to travel at least |f_j - j| steps. Let’s denote by M_j the quantity f_j - j (without the absolute value), so M_j also encodes which direction sj needs to go (e.g. negative for “left”).
- each swap moves exactly two elements, so the total number of steps each number will move is equal to twice the number of swaps.
Thus, the answer is at least half of the sum |M_0| + |M_1| + \cdots + |M_{n-1}|. But can it always be done with exactly this number of steps? The answer is yes! To show this, we only need to show that if s \not= t, then there exists adjacent positions i and i+1 such that M_i > 0 and M_{i+1} < 0, so we can swap them and reduce the sum above by two.
To show it, let j be the first position where s and t differ. Suppose that sj is a G (the other case can be handled similarly). Also, let sk be the first B after sj. Note that M_0, M_1, \ldots, M_{j-1} are all zero, but M_j is not. We also have the following observations:
- M_k < 0, because sk’s final position is j (Actually we have M_k = j - k).
-
M_j, M_{j+1}, M_{j+2}, \ldots, M_{k-1} are all > 0. This is because they are all
Gs, so they will have to eventually end up to the right of theBin position k, so they have to move at least one step right.
In particular, M_{k-1} > 0 and M_k < 0, which is exactly what we want! Therefore, the answer is exactly half the value |M_0| + |M_1| + \cdots + |M_{n-1}|.
The following pseudocode illustrates this (note that we have removed the assumption that t starts with a G):
def min_cost_type_1(s, t):
ans = 0
count_eq = 0 // how many letters encountered equal t[0]?
count_ne = 0 // how many letters encountered don't equal t[0]?
for i from 0 to n - 1
if s[i] == t[0]
ans += abs(i - (2*count_eq))
count_eq += 1
else
ans += abs(i - (2*count_ne+1))
count_ne += 1
return ans / 2
This also clearly runs in O(n).
Making a string likable, when type = 2
Finally, we handle the case where type = 2. Similarly to the type = 1 case, we can also replace a swap of distance d with d adjacent swaps. But this one is even better: the cost of swapping with distance d is d2, while simulating it with d adjacent swaps requires only a cost of d. Thus, we are better off only swapping adjacent elements, and so the solution is the same as for type = 1! So no additional work is needed: the min_cost_type_1 function above works also for type = 2 (and indeed for any type > 2!).
Code
Let’s summarize what we discussed above in pseudocode:
// solve the test case (s, type)
def solve_case(s, type):
result = min(t_solve_case(s, type, 'G'), t_solve_case(s, type, 'B'))
if result < infinity
return result
else
return -1
// solve the test case (s, type), assuming the target 't' starts with letter 't_start'
def t_solve_case(s, type, t_start):
n = s.length
if t_start == "B"
t = "BGBGBGBG..." // of length n
else
t = "GBGBGBGB..." // of length n
if count_occurrences(n, s, 'G') != count_occurrences(n, t, 'G') // no need to check for 'B'
return infinity
if type == 0
return min_cost_type_0(n, s, t)
else
return min_cost_type_1(n, s, t)
// how many times the letter 'c' appears in string 's'
def count_occurrences(n, s, c):
count = 0
for i from 0 to n - 1
if s[i] == c
count += 1
return count
def min_cost_type_0(n, s, t):
ans = 0
for i from 0 to n - 1
if s[i] != t[i]
ans += 1
return ans / 2
def min_cost_type_1(n, s, t):
ans = 0
count_eq = 0
count_ne = 0
for i from 0 to n - 1
if s[i] == t[0]
ans += abs(i - (2*count_eq))
count_eq += 1
else
ans += abs(i - (2*count_ne+1))
count_ne += 1
return ans / 2
Author’s solution for type \ge 1
Here we describe the author’s solution to the case type = 1 (and thus will also apply for type > 1). It’s a bit different (and nicer!) from the solution described above, but I chose it because in my opinion its correctness is easier to show.
First, we create an array a[0…n-1], defined as follows:
- a[i] = 0, if si = ti.
-
a[i] = 1, if si \not= ti and si =
Band ti =G. -
a[i] = -1, if si \not= ti and si =
Gand ti =B.
Now in this problem, you have to move elements here and there in such a way that finally all the elements of the array becomes zero and the total operations taken is minimized. Formally, you have to match 1’s with -1’s so that the sum of the distances between matched pairs is minimized. This problem is a simplified version of problem PRLADDU.
The solution now is very easy and can be described by the following pseudocode:
def min_cost_type_1(s, t):
ans = 0
curr = 0
for i from 0 to n - 1
curr += a[i]
ans += abs(curr)
return ans
The proof of this is given in the editorial of the problem. Also the editorial gives a quite nice detailed proof of this strategy.
Time Complexity:
O(n)
