Substring Removal Game with Python
Understanding the ProblemSubstring Removal Game is an 800-point problem at codeforces, I hope you have read the problem carefully and have tried thinking about solving it. This problem basically states as its name sounds to say, to remove a substring. Per each test, you’re given a string of binary characters (0’s and 1’s) and you’re required to remove each consecutive 1’s to make Alice win. Who is Alice? Alice and Bob are players in the game, and the winner is the one who removes the highest numbers of 1’s. Your duty is to make Alice win given that Alice is the first to move.
How to Think for a Solution
- input for test cases
- input for each string of binary characters per each test case
01111001this means that we have 4 consecutive 1’s and then just 1; to make Alice win in this case, we should make her take that move which is obviously her first move already and then Bob can take the second move which is the last 1 in the string. Let’s have another example, 111111 these are 6 ones which can be the first move for Alice so 6 moves will be her win. How about this tricky one:
101010101? So there are 5 ones… which of them should be Alice’s moves? That would be the first and the third and the fifth… so here 3 moves for Alice. What for this one:
011011110111? Here, we have 2 consecutive ones, 4 consecutive ones, and 3 consecutive ones. Which moves can make Alice win? So we need then to think how we can make number of moves the highest possible so if we sort numbers of consecutive ones in descending order and then start on the highest number that would give us the first move for Alice, and the second move should be a step two from that one. So in this case:
[4 3 2]Alice will take moves 4 and 2 which sum up to 6. That’s how I thought about this problem and below is my implementations in Python:
N = int(input()) s =  for _ in range(N): s.append(input()) for n in range(N): ones =  count = 0 for c in s[n]: if c == '1': count += 1 else: if count: ones.append(count) count = 0 if count: ones.append(count) onessorted = sorted(ones, reverse=True) print(sum(onessorted[0::2]))
ShoutoutI’d like to share this video because the idea of solving this solution is from this guy. Check out his solution in C++ if you’re interested.
Please share your Feedback:
Did you enjoy reading or think it can be improved? Don’t forget to leave your thoughts in the comments section below! If you liked this article, please share it with your friends, and read a few more!