Strange Instructions (Codeforces 1621F)
Tags: Greedy, data structures

Dasha has $$$10^{100}$$$ coins. Recently, she found a binary string $$$s$$$ of length $$$n$$$ and some operations that allows to change this string (she can do each operation any number of times):  Replace substring 00 of $$$s$$$ by 0 and receive $$$a$$$ coins.  Replace substring 11 of $$$s$$$ by 1 and receive $$$b$$$ coins.  Remove 0 from any position in $$$s$$$ and pay $$$c$$$ coins. It turned out that while doing this operations Dasha should follow the rule:  It is forbidden to do two operations with the same parity in a row. Operations are numbered by integers $$$1$$$-$$$3$$$ in the order they are given above. Please, calculate what is the maximum profit Dasha can get by doing these operations and following this rule.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.The first line of each test case contains four integers $$$n$$$, $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \leq n \leq 10^5, 1 \leq a, b, c \leq 10^9$$$).The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.It is guaranteed that the total sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test case print the answer.

Note: In the first test case one of the optimal sequences of operations is 01101 $$$\rightarrow$$$ 0101 $$$\rightarrow$$$ 011 $$$\rightarrow$$$ 01. This sequence of operations consists of operations $$$2$$$, $$$3$$$ and $$$2$$$ in this order. It satisfies all rules and gives profit $$$3$$$. It can be shown that it is impossible to achieve higher profit in this test case, so the answer is $$$3$$$.In the second test case one of the optimal sequences of operations is 110001 $$$\rightarrow$$$ 11001 $$$\rightarrow$$$ 1001 $$$\rightarrow$$$ 101.In the third test case one of the optimal sequences of operations is 011110 $$$\rightarrow$$$ 01110 $$$\rightarrow$$$ 1110 $$$\rightarrow$$$ 110 $$$\rightarrow$$$ 11 $$$\rightarrow$$$ 1.

Sample Inputs:
3
5 2 2 1
01101
6 4 3 5
110001
6 3 2 1
011110

Sample Outputs:
3
11
4

Solution (Python):
from copy import copy
import sys
fin = sys.stdin

def start_from_1(count_moves_1_glue, count_moves_2, a, b, c):
    profit = 0
    if b > c:
        minimal_1 = 0
    else:
        minimal_1 = 1
    while count_moves_1_glue and count_moves_1_glue[-1] <= minimal_1:
        count_moves_1_glue.pop()
    while True:
        if not count_moves_1_glue:
            return profit
        can_glue = len(count_moves_1_glue) > 2
        assert count_moves_1_glue[-1] >= 1
        assert count_moves_2 >= 0
        if len(count_moves_1_glue) == 2:
            count_moves_1_glue = sorted(count_moves_1_glue)
        count_moves_1_glue[-1] -= 1
        if count_moves_1_glue[-1] > 0:
            profit += a
        else:
            if count_moves_2 == 0 and (not can_glue):
                return profit
            profit -= c
        while count_moves_1_glue and count_moves_1_glue[-1] <= minimal_1:
            can_glue = len(count_moves_1_glue) > 2
            if minimal_1 == 0 and can_glue:
                count_moves_2 += 1
            count_moves_1_glue.pop()
        if count_moves_2 == 0:
            return profit
        else:
            count_moves_2 -= 1
            profit += b

def solve(a, b, c, s):
    count_moves_1 = [0]
    count_moves_2 = 0
    for (c0, c1) in zip(s, s[1:]):
        if c0 == '1' and c1 == '1':
            count_moves_2 += 1
    if s[0] == '1':
        count_moves_1.append(0)
    for char in s:
        if char == '0':
            count_moves_1[-1] += 1
        elif char == '1' and count_moves_1[-1] > 0:
            count_moves_1.append(0)
    count_moves_1_glue = sorted([count_moves_1[0], count_moves_1[-1]]) + sorted(count_moves_1[1:-1], reverse=True)
    options = [0, start_from_1(copy(count_moves_1_glue), count_moves_2, a, b, c)]
    if count_moves_2 > 0:
        count_moves_2 -= 1
        options.append(b + start_from_1(count_moves_1_glue, count_moves_2, a, b, c))
    return max(options)

def operations(a, b, c, s, operation):
    if operation == 0:
        for index in range(len(s) - 1):
            if s[index:index + 2] == '11':
                yield (s[:index] + s[index + 1:], 1 - operation, b)
    if operation == 1:
        for index in range(len(s) - 1):
            if s[index:index + 2] == '00':
                yield (s[:index] + s[index + 1:], 1 - operation, a)
        for index in range(len(s)):
            if s[index:index + 1] == '0':
                yield (s[:index] + s[index + 1:], 1 - operation, -c)
max_score = dict()

def solve_slow_recursive(a, b, c, s, operation):
    k = (s, operation, a, b, c)
    if k in max_score:
        return max_score[k]
    options = [add_score + solve_slow_recursive(a, b, c, new_s, new_operation) for (new_s, new_operation, add_score) in operations(a, b, c, s, operation)]
    max_score[k] = max(options + [0])
    return max_score[k]

def solve_slow(a, b, c, s):
    alternatives = [solve_slow_recursive(a, b, c, s, operation) for operation in [0, 1]]
    return max(alternatives)

def local_test():
    a = 1
    b = 20
    c = 10
    for i in range(1, 10):
        for j in range(2 ** i):
            s = format(j, f'0{i}b')
            answer = solve(a, b, c, s)
            answer_correct = solve_slow(a, b, c, s)
            assert answer == answer_correct, f'{s}, {answer} != {answer_correct}'
t = int(fin.readline())
for test in range(t):
    (n, a, b, c) = map(int, fin.readline().split())
    s = fin.readline().rstrip('\n')
    answer = solve(a, b, c, s)
    print(answer)

Solution (Python):
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
(t,) = I()
for _ in range(t):
    (n, a, b, c) = I()
    s = input()
    start = int(s[0])
    curr = s[0]
    ind = 0
    blocks = []
    for i in range(1, n):
        if s[i] != curr:
            blocks.append(i - ind)
            curr = s[i]
            ind = i
    blocks.append(n - ind)
    l = len(blocks)
    zero = 0
    one = 0
    for i in range(l):
        if i % 2 == start:
            zero += blocks[i] - 1
        else:
            one += blocks[i] - 1
    if c > b:
        val = (a + b) * min(zero, one)
        if zero > one:
            print(val + a)
        elif one > zero:
            print(val + b)
        else:
            print(val)
    else:
        zeroes = [blocks[i] for i in range(l) if i % 2 == start and i > 0 and (i < l - 1)]
        zeroes.sort()
        extra = 0
        xxtra = 0
        if start == 0:
            extra += blocks[0] - 1
            xxtra += 1
        if (l - 1) % 2 == start:
            extra += blocks[-1] - 1
            xxtra += 1
        z1 = zeroes[:]
        extra1 = extra
        xxtra1 = xxtra
        val1 = 0
        ind = 0
        for i in range(one):
            while ind < len(zeroes) and zeroes[ind] == 1:
                ind += 1
            if ind < len(zeroes):
                zeroes[ind] -= 1
                val1 += a
            elif extra > 0:
                extra -= 1
                val1 += a
            elif xxtra > 0:
                xxtra -= 1
                val1 -= c
            else:
                break
            val1 += b
        val1 += (b - c) * zeroes.count(1)
        if len(zeroes) > 0 and max(zeroes) > 1 or extra > 0:
            val1 += a
        val2 = 0
        ind = 0
        for i in range(one):
            val2 += b
            if i == one - 1:
                break
            while ind < len(zeroes) and z1[ind] == 1:
                ind += 1
            if ind < len(z1):
                z1[ind] -= 1
                val2 += a
            elif extra1 > 0:
                extra1 -= 1
                val2 += a
            elif xxtra1 > 0:
                xxtra1 -= 1
                val2 -= c
            else:
                break
        val2 += (b - c) * z1.count(1)
        print(max(val1, val2))

Solution (Python):
import sys
input = sys.stdin.readline
out = []
ssl = []
t = int(input())
for _ in range(t):
    (n, a, b, c) = map(int, input().split())
    s = input().strip()
    ssl.append(s)
    z = [0]
    zc = 0
    oc = 0
    for ch in s:
        if ch == '0':
            z[-1] += 1
            zc += 1
        else:
            z.append(0)
            oc += 1
    M1 = sum((max(0, v - 1) for v in z))
    if len(z) == 1:
        out.append(a if n >= 2 else 0)
        continue
    l = z.pop(0)
    r = z.pop()
    poss = [0]
    zz = sorted(z)[::-1]
    curr = 0
    L1 = M1
    L2 = 0
    Z1 = 0
    OL = oc
    ZL = zc
    while zz and zz[-1] == 0:
        zz.pop()
        L2 += 1
    while zz and zz[-1] == 1:
        zz.pop()
        Z1 += 1
    while True:
        if ZL == 0:
            break
        if L1 > 0:
            poss.append(curr + a)
        if OL <= 1:
            break
        if L2 > 0:
            if L1 > 0:
                curr += a
                ZL -= 1
                L1 -= 1
                if zz:
                    zz[-1] -= 1
                    if zz[-1] == 1:
                        zz.pop()
                        Z1 += 1
                curr += b
                L2 -= 1
                OL -= 1
            else:
                curr -= c
                ZL -= 1
                curr += b
                OL -= 1
        else:
            ZL -= 1
            if Z1 == 0:
                break
            Z1 -= 1
            curr -= c
            OL -= 1
            curr += b
        poss.append(curr)
    zz = sorted(z)[::-1]
    curr = 0
    L1 = M1
    L2 = 0
    Z1 = 0
    OL = oc
    ZL = zc
    while zz and zz[-1] == 0:
        zz.pop()
        L2 += 1
    while zz and zz[-1] == 1:
        zz.pop()
        Z1 += 1
    good = False
    if L2:
        OL -= 1
        L2 -= 1
        curr = b
        poss.append(b)
        good = True
    while good:
        if ZL == 0:
            break
        if L1 > 0:
            poss.append(curr + a)
        if OL <= 1:
            break
        if L2 > 0:
            if L1 > 0:
                curr += a
                ZL -= 1
                L1 -= 1
                if zz:
                    zz[-1] -= 1
                    if zz[-1] == 1:
                        zz.pop()
                        Z1 += 1
                curr += b
                L2 -= 1
                OL -= 1
            else:
                curr -= c
                ZL -= 1
                curr += b
                OL -= 1
        else:
            ZL -= 1
            if Z1 == 0:
                break
            Z1 -= 1
            curr -= c
            OL -= 1
            curr += b
        poss.append(curr)
    out.append(max(poss))
print('\n'.join(map(str, out)))