Blackslex and Girls

The useful move is to forget the individual arrays for a minute and look at district totals.

Let

$T=x+y$, and $P=\sum p_i$.

If $T<P$, we do not even have enough voters to satisfy the minimum district populations, so the answer is NO. No politics, no geometry, just arithmetic being rude.

For a district with total population $q$, the winning party must have a strict majority, so it needs at least

$\operatorname{win}(q)=\lfloor q/2 \rfloor+1$

voters.

That is the core fact.

When both winner types exist

Suppose there is at least one 0 district and at least one 1 district.

For every 0 district, party A must win. If district $i$ has minimum population $p_i$, then A needs at least

$\lfloor p_i/2 \rfloor+1$

voters there. So define

$needA=\sum_{s_i=0}(\lfloor p_i/2 \rfloor+1)$.

Similarly, every 1 district must be won by party B, so define

$needB=\sum_{s_i=1}(\lfloor p_i/2 \rfloor+1)$.

These are clearly necessary:

• if $x<needA$, A cannot win all 0 districts;
• if $y<needB$, B cannot win all 1 districts.

They are also sufficient, as long as $T\ge P$.

Why? Because once both district types exist, surplus voters are harmless:

• extra A-voters can be dumped into some 0 district, where more A only helps;
• extra B-voters can be dumped into some 1 district, where more B only helps.

So for mixed strings, the answer is exactly:

$T\ge P$, $x\ge needA$, and $y\ge needB$.

Equivalently, possible A totals form the interval

$[needA,\ T-needB]$.

When all districts have the same winner

Now suppose all districts are 0, so A must win everywhere. The all-1 case is symmetric with A and B swapped.

Here, the false assumption is: "extra voters are always harmless." Nope. If everyone must be in an A-winning district, then adding lots of voters can force us to add more A-voters too. You cannot hide a mountain of B-voters in a B-winning district because there are no B-winning districts. Sad.

We need the minimum possible number of A-voters among all districts, given total population $T$.

Start with district $i$ having exactly $p_i$ voters. The initial required A count is

$base=\sum_i(\lfloor p_i/2 \rfloor+1)$.

There are

$E=T-P$

extra voters to place.

Now look at what happens when we increase a district's total population by 1.

If $p_i$ is even, say $p_i=2k$, then initially A needs $k+1$. With one extra voter, the total becomes $2k+1$, and A still only needs $k+1$. So this first extra voter is free.

If $p_i$ is odd, say $p_i=2k+1$, then initially A needs $k+1$. With one extra voter, the total becomes $2k+2$, and A needs $k+2$. So that extra voter costs one more A-voter.

Therefore:

• every even $p_i$ gives one free extra voter;
• after using those free extras, every 2 more extra voters force 1 more winner voter, rounded up.

Let $c$ be the number of even $p_i$.

If $E\le c$, then the minimum winner count stays $base$.

Otherwise, after using $c$ free extras, there are $R=E-c$ extras left, and they increase the minimum winner count by

$\lceil R/2 \rceil$.

So the minimum required winner voters is

$base+\max(0,\lceil (E-c)/2 \rceil)$.

For all 0, we need

$x\ge base+\max(0,\lceil (E-c)/2 \rceil)$.

For all 1, we need the same condition for B:

$y\ge base+\max(0,\lceil (E-c)/2 \rceil)$.

Why intervals are enough

For a fixed district total $q$:

• in a 0 district, A can be any integer from $\lfloor q/2 \rfloor+1$ to $q$;
• in a 1 district, A can be any integer from $0$ to $q-(\lfloor q/2 \rfloor+1)$.

So each district contributes an integer interval of possible A-votes. The sum of integer intervals is still an integer interval. There are no sneaky parity gaps here. The strict majority condition already handles the parity.

That means checking the minimum and maximum possible total A-voters is enough.

Complexity

Each test case is processed in $O(n)$ time and $O(1)$ extra memory. Across all tests, this is $O(\sum n)$, which easily fits.