PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Alice and Bob play N matches. The winner of a match receives one point.
M matches have concluded, and you know their results already - given via the binary string S.
Is it possible for the final scores of Alice and Bob to tie after all N matches have completed?
EXPLANATION:
Let A denote the number of matches that Alice has already won, and B denote the number of matches Bob has already won.
These can be found by counting the number of zeros and ones in the binary string S.
There are (N-M) matches remaining, and each of them can be used to increase either A or B by exactly one.
Our goal is to have A = B in the end.
First, note that if N is odd, it’s definitely impossible for the final result to be a tie - after all N matches, one player will have an odd number of wins and the other an even number so they cannot be equal.
So, in this case we can immediately answer “No”.
Next, consider the case where N is even.
We want Alice and Bob to have an equal number of wins in the end - which means they must both end up with exactly \frac N 2 wins.
So, in particular, if either Alice or Bob have \gt \frac N 2 wins initially, it’s surely impossible to make them have exactly \frac N 2 wins in the end — making the answer “No” immediately.
That leaves the case where N is even and Alice and Bob both have \le \frac N 2 wins initially.
In this case, it is indeed possible to make them both reach \frac N 2, since we can just make Alice win any (\frac N 2 - A) remaining matches and Bob win the rest (which will equal (\frac N 2 - B)).
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, m = map(int, input().split())
s = input()
alice, bob = s.count('0'), s.count('1')
if n%2 == 0 and alice <= n//2 and bob <= n//2: print('Yes')
else: print('No')