PLACE0110 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You have X strings equal to 01 and Y strings equal to 10. You will concatenate them in some order to obtain a binary string S.
Find the minimum possible number of adjacent elements in S that will differ from each other.

EXPLANATION:

First, we see that each 01 and each 10 string will contribute 1 to the count of adjacent different elements, no matter how they’re arranged.
So, a definite lower bound on the answer is X+Y.

This leaves adjacent different elements that come from different strings.
For this, observe that:

  • If a 01 is placed next to another 01, to obtain 0101, there is one occurrence of adjacent different elements between them (01\mid 01, across the bar).
  • If a 01 is placed next to a 10, to obtain either 0110 or 1001, there is no occurrence of adjacent different elements between them.

So, ideally we want to place each 01 next to a 10 and vice versa: which means the best case scenario is for us to alternate between 10 and 01 strings.

Now, suppose X \geq Y, i.e. we have more 01 strings than 10 strings.
Then, the best we can do is to start with 01 and alternate till we run out of 10, at which point we’re forced to place all remaining occurrences of 01 next to each other.
That is, the final string will look like

01\mid 10\mid 01\mid 10\mid \ldots \mid 01\mid 10\mid 01\mid 01\mid 01\mid \ldots \mid 01

The constraints are small enough that you can just create this string directly and then count the number of adjacent unequal elements in it.

You can also math it out: once the alternating part ends we’ll have \max(0, X-Y-1) occurrences of 01 strings remaining, and each of them adds 1 to the answer — so the answer is X+Y + \max(0, X-Y-1).
Note that this was when X \geq Y, so if X is smaller swap them first (or use the expression X+Y+\max(0, |X-Y|-1)).

TIME COMPLEXITY:

\mathcal{O}(1) or \mathcal{O}(X+Y) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    x, y = map(int, input().split())
    if x > y: x, y = y, x # Ensure that x <= y
    ans = x+y + max(0, y-x-1)
    print(ans)
1 Like