Sum of Substrings (Codeforces 1691C)
Tags: Greedy, strings

You are given a binary string $$$s$$$ of length $$$n$$$.Let's define $$$d_i$$$ as the number whose decimal representation is $$$s_i s_{i+1}$$$ (possibly, with a leading zero). We define $$$f(s)$$$ to be the sum of all the valid $$$d_i$$$. In other words, $$$f(s) = \sum\limits_{i=1}^{n-1} d_i$$$.For example, for the string $$$s = 1011$$$:   $$$d_1 = 10$$$ (ten);  $$$d_2 = 01$$$ (one)  $$$d_3 = 11$$$ (eleven);  $$$f(s) = 10 + 01 + 11 = 22$$$. In one operation you can swap any two adjacent elements of the string. Find the minimum value of $$$f(s)$$$ that can be achieved if at most $$$k$$$ operations are allowed.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.First line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le k \le 10^9$$$) — the length of the string and the maximum number of operations allowed.The second line of each test case contains the binary string $$$s$$$ of length $$$n$$$, consisting of only zeros and ones.It is also given that sum of $$$n$$$ over all the test cases doesn't exceed $$$10^5$$$.

Output: For each test case, print the minimum value of $$$f(s)$$$ you can obtain with at most $$$k$$$ operations.

Note:   For the first example, you can't do any operation so the optimal string is $$$s$$$ itself. $$$f(s) = f(1010) = 10 + 01 + 10 = 21$$$.  For the second example, one of the optimal strings you can obtain is "0011000". The string has an $$$f$$$ value of $$$22$$$.  For the third example, one of the optimal strings you can obtain is "00011". The string has an $$$f$$$ value of $$$12$$$. 

Sample Inputs:
3
4 0
1010
7 1
0010100
5 2
00110

Sample Outputs:
21
22
12

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    s = input()
    count1 = 0
    for i in range(n):
        if s[i] == '1':
            count1 += 1
            r = i
            if count1 == 1:
                l = i
    if not count1:
        print(0)
        continue
    ans = count1 * 11
    r = n - r - 1
    if k >= r:
        ans -= 10
        count1 -= 1
        k -= r
    if k >= l and count1:
        ans -= 1
    print(ans)

Solution (Python):
from sys import stdin

def input():
    return stdin.readline().strip()

def read_int():
    return int(input())

def read_ints():
    return map(int, input().split())
t = read_int()
for case_num in range(t):
    (n, k) = read_ints()
    s = input()
    m = s.count('1')
    if m == 0:
        print(0)
    elif m == n:
        print(11 * (n - 1))
    else:
        ans = 11 * m
        l = s.find('1')
        r = s.rfind('1')
        lneed = l
        rneed = n - 1 - r
        if k >= lneed + rneed and m > 1:
            ans = 11 * (m - 1)
        elif k >= rneed:
            ans = 11 * m - 10
        elif k >= lneed:
            ans = 11 * m - 1
        print(ans)

Solution (Python):
def sum_of_substring(t):
    result = ''
    for _ in range(t):
        (n, k) = map(int, input().split())
        s = input()
        ones_positions = [i for (i, char) in enumerate(s) if char == '1']
        total_sum = 0
        if ones_positions:
            if n - 1 - ones_positions[-1] <= k:
                k -= n - 1 - ones_positions[-1]
                total_sum += 1
                ones_positions.pop()
        if ones_positions:
            if ones_positions[0] <= k:
                k -= ones_positions[0]
                total_sum += 10
                ones_positions.pop(0)
        result += str(11 * len(ones_positions) + total_sum) + ' '
    for r in result.split():
        print(r)
t = int(input())
sum_of_substring(t)