Codeforces has introduced a third division in their competitions. Initially I though this is the place to go for “easy” stuff, as far as some of the 2nd division problems require some advanced algorithms, like combinations of graphs and months of preparations. I would not discuss the problems from the first division, sometimes they look doable only if you are into competitive programming about 50 hours per week for more than 6 months.
So, there was this interesting problem in the third division – given a binary string what is the minimum, what is the lexicographical minimum possible string you can obtain from the given one if you can perform no more than K moves? So, if the input is 11011010 and the moves_allowed (K) are 5, the minimal string is 01011110.
How to obtain it? These are the optimal 5 swaps to get the minimal string:
Somehow, initially I thought it was an easy problem, because I have already solved a similar one for minimization of permutation, but it was not the case. That one is more advanced and required a different logic. Pretty much, the logic is the following:
- create a new list with “1”, for the length of the given input – result = ['1'] * len_total (it looks beautiful in Python, eh?)
- make a counter for the best possible place – best_place = 0 and increment it every time, when you manage to put a “0” to it;
- start looping from the initial input from left to right and check on each position, whether it is a , because we are only interested in these
- there are two options – we can either move it to the left or we may leave it on its place (if it is optimal or we have no moves left). To calculate the moves, we need the min(moves_allowed, digit_position - best_place)
- decrement the moves_allowed
- write the result at the new position as – result[digit_position - moves_to_go] = '0'
- increment the best place – best_place += 1
- enjoy the “greed” of the algorithm, coming the best solution in O(n) time. (To be honest, first I thought of bruteforcing it with O(n^2), replacing the “10” with “01” on the string until I had moves. It did not work out, complexity is important.)
The whole magic is here:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
import math def main(): tests_count = int(input()) for _ in range(0, tests_count): info = list(map(int,input().split())) len_total = info[0] moves_allowed = info[1] numbers_given = list(input()) result = ['1'] * len_total best_place = 0 for digit_position in range(len_total): if(numbers_given[digit_position] =='0'): moves_to_go = min(moves_allowed, digit_position - best_place) moves_allowed -= moves_to_go result[digit_position - moves_to_go] = '0' best_place += 1 print ("".join(result)) if __name__== "__main__": main() |
Enjoy it!