TRTR3 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

For a binary string A of length 3N, define f(A) to be the binary string B of length N such that B_i = \text{mode}(A_i, A_{i+N}, A_{i+2N}).

Given N and X, construct any binary string A of length 3N containing X ones such that f(A) is lexicographically minimal.

EXPLANATION:

Lexicographic minimization means we want to be as greedy as possible: it’s optimal to try and make the first character of f(A) 0 if we can, then the second character, 0 and so on.

For ease of notation, let B = f(A).

Let’s try to make B_1 = 0 first.
There are only two ways for this to happen:

  • A_1, A_{N+1}, A_{2N+1} must all be 0, or
  • Two of \{A_1, A_{N+1}, A_{2N+1}\} are 0 and the third character is 1.

Observe that this is always possible as long as we have at least two zeros available to us.

Clearly, whenever it’s possible we should choose the second option, i.e. “use up” one occurrence of 1.
This frees up more zeros for the future indices, which can hopefully allow for more zeros to be created.

Once these three elements are fixed, we can move on and do the same thing to try and make B_2 = 0, then B_3 = 0, and so on.

Observe that if we fail to make B_i = 0 at any point, it means we have at most one occurrence of 0 remaining.
This means that all future indices can’t be made 0 either; so it doesn’t matter how we place the remaining characters - just fill them up in any way.

Thus, we obtain a very simple solution in linear time:

  • Let there be Z zeros and O ones unused so far.
    Initially, Z = 3N-K and O = K.
  • For i = 1, 2, 3, \ldots, N,
    • If Z \ge 2, set A_i = A_{i+N} = 0 and A_{i+2N} = 1, while reducing Z by 2 and O by 1.
      • A special case here is if O = 0, in which case we set A_{i+2N} = 0 as well.
    • Otherwise, if Z = 1 set A_i = 0.
      Then, fill all remaining characters with 1.

Other implementations are possible too: for example, an alternate solution is to place ones at positions 3N, 3N-1, \ldots, 2N+1 as much as possible, and then in the order 2N, N, 2N-1, N-1, \ldots
This way, when breaking A into three parts of length N each, each part will have ones in some suffix; and the lengths of these suffixes can be easily computed with a bit of simple math.
This is what the implementation below does, avoiding (explicit) loops entirely.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())

    x = min(n, k)
    k -= x
    p3 = '0'*(n-x) + '1'*x

    a, b = k//2, (k+1)//2
    p2 = '0'*(n-a) + '1'*a
    p1 = '0'*(n-b) + '1'*b

    print(p1+p2+p3)