MAX_BIN - Editorial

PROBLEM LINK:

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

Author: hjindal
Tester: abhidot
Editorialist: iceknight1093

DIFFICULTY:

1143

PREREQUISITES:

Greedy

PROBLEM:

Given a binary string S, you can perform the following operations on it:

  • Change a 0 to a 1
  • Insert a 0 anywhere in the string

Find the maximum possible integer that can be formed after at most K operations.

EXPLANATION:

Let X be the decimal value of the string.
Let’s see how the given operations affect the value of X.

  • Suppose we change bit i from 0 to 1. This increases the value of X by 2^i.
  • Suppose we insert a 0 after bit i. This doesn’t change anything about bits 0, 1, 2, \ldots, i-1, but shifts bits i, i+1, \ldots to the left by one step, i.e, multiplies their values by 2.
    So, if Y is the total value of bits \geq Y, X will increase by exactly Y.

From this, it’s easy to see that whenever we insert a 0, it’s always optimal to do so at the end of the string, since it directly multiplies the value of X by 2.

So, we only need to decide when to insert a 0 and when to change a 0 into a 1.
In fact, this can be done greedily!

  • If the leftmost character of S is 1, then insert a 0 at the end of S
  • Otherwise, change the leftmost character of S to 1.

Each operation is easily performed in \mathcal{O}(1), so the final string can be found in \mathcal{O}(N+K).

TIME COMPLEXITY

\mathcal{O}(N + K) per test case.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    s, k = input().split()
    k = int(k)
    s = list(s)
    if s[0] == '0':
        s[0] = '1'
        k -= 1
    s += ['0']*k
    print(''.join(s))