Two out of Three

The queue has only one piece of memory

The scary part is that the queue changes. The nice part: it changes in a very rigid way.

Suppose we have already performed $t$ two-person serving phases. Then exactly $2t$ people have been removed. Among the first $2t+1$ original people, exactly one may still be waiting; call this person $s$.

So the current front of the queue looks like:

$$s,\; 2t+2,\; 2t+3$$

whenever those new indices exist.

That is the whole trick. We do not need the entire queue. We only need the survivor $s$ from the old prefix. Everything else is deterministic.

Initially, before any phase, the “survivor” is person $1$:

$$dp_0[1]=0.$$

DP state

Define:

$$dp_t[s] = \text{minimum total time after } t \text{ phases, if } s \text{ is the only remaining person among } 1\dots 2t+1.$$

At this moment, the first three candidates are:

$$(s, x, y), \qquad x=2t+2,\quad y=2t+3.$$

There are exactly three possible moves:

1. Serve $x$ and $y$, survivor stays $s$:

$$dp_{t+1}[s] \gets dp_t[s] + \max(a_x,a_y)$$

2. Serve $s$ and $y$, survivor becomes $x$:

$$dp_{t+1}[x] \gets dp_t[s] + \max(a_s,a_y)$$

3. Serve $s$ and $x$, survivor becomes $y$:

$$dp_{t+1}[y] \gets dp_t[s] + \max(a_s,a_x)$$

That is it. No hidden monster under the bed.

How many DP transitions?

Let:

$$T=\left\lfloor \frac{n-1}{2}\right\rfloor.$$

We perform these three-choice transitions for $t=0,1,\dots,T-1$.

Now handle the end separately:

If $n$ is odd

After $T$ transitions, everyone has been introduced, and only one survivor $s$ remains. The final cost is:

$$dp_T[s] + a_s.$$

So we take:

$$\min_s \left(dp_T[s]+a_s\right).$$

If $n$ is even

After $T$ transitions, the queue contains two people: the survivor $s$ and the last person $n$. They must be served together, with cost:

$$\max(a_s,a_n).$$

So we take:

$$\min_s \left(dp_T[s]+\max(a_s,a_n)\right).$$

Reconstruction

During every relaxation, store:

• the previous survivor,
• the pair of people served in this phase.

After choosing the best final survivor, backtrack through these parents. Then append the final operation:

• one person if $n$ is odd,
• two people if $n$ is even.

Reverse the reconstructed list and print it.

Correctness proof

We prove the algorithm computes an optimal valid serving order.

Lemma 1

After $t$ two-person phases, among people $1,2,\dots,2t+1$, exactly one person remains in the queue.

Proof. Initially, for $t=0$, person $1$ is the only person in the prefix $1\dots1$.

Assume the statement holds for some $t$. The first three available people are the survivor $s$ and the next two unseen people $2t+2$ and $2t+3$. The next operation removes exactly two of these three, leaving exactly one survivor among people $1\dots 2t+3$. Thus the statement holds for $t+1$. $\square$

Lemma 2

For every valid state after $t$ phases, the DP considers all possible next operations.

Proof. By Lemma 1, the first three people are exactly:

$$(s,2t+2,2t+3).$$

The algorithm tries all three ways to choose two people from these three. Therefore every legal next operation is considered. $\square$

Lemma 3

$dp_t[s]$ equals the minimum possible total time to reach the state with survivor $s$ after $t$ phases.

Proof. By induction on $t$.

For $t=0$, $dp_0[1]=0$, which is clearly optimal.

For the transition from $t$ to $t+1$, Lemma 2 says every legal move is considered, and each transition adds exactly the correct serving time. Taking the minimum over all previous states gives the optimal value. $\square$

Theorem

The algorithm outputs the minimum possible total serving time.

Proof. After the DP transitions, the remaining queue is forced:

• if $n$ is odd, exactly one survivor remains and must be served alone;
• if $n$ is even, the survivor and person $n$ remain and must be served together.

The algorithm tries every possible final survivor $s$ and adds the forced final cost. By Lemma 3, each prefix cost is optimal, so the minimum final value is globally optimal. $\square$

Complexity

There are $O(n)$ phases and $O(n)$ possible survivors per phase. Each state has $3$ transitions.

$$\text{Time complexity}=O(n^2)$$

We store parents for reconstruction:

$$\text{Memory complexity}=O(n^2)$$

With $n\le 1000$, this is tiny. The cashier may be weird, but the DP is not.