BUYORDEREZ - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Preparation: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

There are N items in a shop, numbered 1 to N. Item i has a type, denoted B_i, which is either 0 or 1.
You will buy all N items exactly once, in some order.

  • When buying an item of type 0, you will receive an additional copy of it if you’ve previously bought any item with lower index.
  • When buying an item of type 1, you will receive an additional copy of it if you’ve previously bought any item with higher index.

Find the maximum total number of items you can obtain.

EXPLANATION:

Since we want to maximize the total number of items, it’s ideal to satisfy the conditions of as many items as possible, to get extra copies of them.

So, for each type 0 item, we want to buy a lower index item before it; and for each type 1 item, we want to buy a higher index item before it.
It thus seems ideal to buy type 1 items in descending order, and type 0 items in ascending order.

This way, the condition of almost every item will be fulfilled: specifically, everything other than the first type 0 and the first type 1 item will have their condition fulfilled.
This gives us at least N-2 extra items, for a total of 2N-2.

Now, no matter what we do, the condition of the very first item we buy cannot be satisfied (there’s nothing before it, after all).
So, we can also obtain only at most N-1 extra items, for 2N-1 in total.

This means the answer is either 2N-1 or 2N-2.
Let’s check if it can be 2N-1, and if it cannot, then the answer is 2N-2.

If the answer is to be 2N-1, either:

  1. All type 0 items have their conditions satisfied, or
  2. All type 1 items have their conditions satisfied.

Suppose all type 0 items must have their conditions satisfied.
Then, the smallest type 0 item must have its condition satisfied: which means there must exist another item smaller than it which is bought before it.

Clearly, such an item cannot be of type 0 itself (since we’re already considering the smallest type 0 item).
So, there must exist an item smaller than the smallest type 0 item - which is only possible when B_1 = 1.

If B_1 = 1, we can buy all type 1 items in descending order, then all type 0 items in ascending order, and the conditions of all but the first item will be fulfilled, giving us 2N-1.

Similarly, we have the case of satisfying all type 1 items instead - which by similar analysis is only possible if B_N = 0.

So, if B_1 = 1 or B_N = 0 the answer is 2N-1, otherwise it’s 2N-2.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    b = list(map(int, input().split()))
    if b[0] == 1 or b[-1] == 0: print(2*n - 1)
    else: print(2*n - 2)