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))