How Long Until Nothing Remains?

Some small facts came quickly:

Next I tried to understand what happens to an individual number when you do or don't choose it at different steps. I wrote down $101111_2$ and drew out the tree of choice-sequences — YN, NN, YNNY, and so on, meaning "yes choose, no don't choose" — to see when it gets killed, when it ends up at $1$, etc. Then more examples: $10_2$, $1011_2$, $101011101_2$.

At this point I could see, and started implicitly using, a pointer picture: halving an odd number turns its low bit to $0$ and moves a pointer to the next bit; half-ceiling it adds $1$ first and then moves the pointer. But I could not come to (and didn't really ask myself) the question underneath:

It was floating in the back of my mind, but it seemed intractable, or I didn't really try to formalize it. I just kept thinking there must be some greedy way to assign this. Pick the leftmost $0$? Make sure nothing becomes a full run of $111\ldots1$'s, which seems to make everything worse (it forces an overflow at some point)? If there's a $1$, take it — and otherwise, taking item $a$ then item $b$ seems provably the same as taking $b$ then $a$, so maybe just take the odd items greedily, in arbitrary or sorted order?

I kept flip-flopping between these greedy variants without any of them dying to a concrete counterexample. More or less stuck.

A different way to look at it: each second we MUST choose exactly one item, so a solution is really an assignment of items to timestamps. How do we pick a distribution of item-to-timestamp assignments that works? Greedily — always assign an item as late as possible, or something? But it doesn't work, because whether an item dies depends on the exact set of timestamps it receives, not just the latest one. The full set matters.

Which brings us right back to the same question: how do we characterize exactly the set of timestamp choices that kill a given item? I think all solutions rest on this. It kept floating in and out of my consciousness, but I did not seriously sit down to write it out and formalize it.

Honestly, I doubt I would have gotten it in contest from here. That was the end of my in-contest progress.

Writing it out produced a classification. For a fixed $T$:

• There are impossible items: their sheer binary length forces more than $T$ seconds no matter what. Any of these, and the answer is no.
• There are loose items: they finish in some $x$ or $x+1$ seconds with $x+1 \leq T$, so there's nothing to optimize — they drop to $1$ and sit there until we get around to killing them, any time in $[x+1, \infty)$.
• There are tight items: they finish in either $T$ or $T+1$ seconds depending on how well we optimize them.

If there's more than one tight item, we're dead — we can't optimize both within $T$. The loose ones are kind of willy-nilly — might as well kill them as late as possible. Which leaves the single tight item. And again: it's not a simple greedy to allocate its timestamps, because the full set matters.

So let's finally sit down and formalize it.

Fix one element with value $a$, and fix $T$ total seconds, numbered $0, 1, \ldots, T-1$. Let $S$ be the set of seconds at which we choose it: it gets floored at those seconds and ceiled at all the others.

The first useful rewrite — which was literally sitting in my initial observations as "$(a_i+1)/2$":

So every second, every element does the same thing: maybe add $1$, then chop off the low bit. Chosen $=$ just chop. Skipped $=$ add $1$, then chop. (The pointer picture from Idea 1, basically.)

101011101   N
 10101111   N
  1011000   N
   101100   N
    10110   N
     1011   N
      110   N
       11   Y
        1   Y
        0

101011101        start                      101011101
101011110   N    +2^0      >> 1   =          10101111
101100000   N    +2^1      >> 2   =           1011000
101100100   N    +2^2      >> 3   =            101100
101101100   N    +2^3      >> 4   =             10110
101111100   N    +2^4      >> 5   =              1011
110011100   N    +2^5      >> 6   =               110
111011100   N    +2^6      >> 7   =                11
111011100   Y    no +1     >> 8   =                 1
111011100   Y    no +1     >> 9   =                 0

In the fixed frame, then, the whole $T$-second run collapses into a single expression:

In words: take $a$, add the binary number $U$ whose $1$-bits are the skipped seconds, then delete the low $T$ bits.

So when does the element get killed? Exactly when $a + U < 2^T$ — when the additions never overflow into a new bit. If $a + U \geq 2^T$, it definitionally has a bit at position $\geq T$, and the $T$ chops only delete the low $T$ bits, so the element must still be alive at the end. Now rewrite $a + U < 2^T$ as $a \leq 2^T - 1 - U$. But $2^T - 1$ is the all-$1$'s number over all $T$ seconds, and $U$'s bits are the skipped seconds — so $2^T - 1 - U$ is exactly the chosen seconds:

To watch it once, take $a = 13 = 1101_2$ and $T = 4$. Choose seconds $\{1,2,3\}$ (skip second $0$): $U = 2^0 = 1$, and $13 + 1 = 14 < 16$ — dead. Choose $\{0,1,3\}$ (skip second $2$): $U = 2^2 = 4$, and $13 + 4 = 17 = 10001_2 \geq 16$ — the overflow bit survives all four chops. Alive.

And cool — does this work with the earlier observations? A $1$ is killed by any single second, since $2^{s} \geq 1$ always: that's the "each $1$ needs its own dedicated second" fact — eventually we choose it at some big timestamp, and that lone power of two is trivially $\geq 1$. And a full run of $1$'s like $7 = 111_2 = 1 + 2 + 4$ demands the three earliest seconds exactly, or something bigger — consistent with the hunch from Idea 1 that a full run of $1$'s makes everything worse.

The one thing to carry over from Idea 4 (Lemma 1): element $a_i$ is killed iff the set of seconds at which we choose it, written out as a binary number ($1$-bit at each chosen second $s$, i.e. worth $2^s$), is $\geq a_i$. And each second is given to exactly one element. So for a fixed $T$, the dynamics are gone entirely:

How do we check whether that's possible? The condition per item is "received seconds, as a binary number, $\geq a_i$" — and comparing binary numbers is something you do from the most significant bit down. So sweep the seconds from the highest-worth down to the lowest, handing them out, and track where each item stands. At any point, either the item's received bits are still equal to the leading bits of $a_i$, or it has already received a second at a position where $a_i$ has a $0$ — making its number strictly bigger, so that item is taken care of no matter what happens at the lower bits. While an item is still equal, it needs every bit where $a_i$ has a $1$: miss one, and its received number falls strictly below $a_i$, with no way to recover from the smaller bits. (Writing this out, it's just the usual lexicographic comparison of bit strings, as a process.)

My first thoughts from there: if exactly one still-equal item needs the current bit, we must give the second to that item. If two or more items both need it, it's not possible — only one of them can have it, and everything remaining is worth less. Otherwise we can give the bit to anyone: I figured probably to the largest remaining item (cleaner), or alternatively "bank" it in a counter to spend later (probably more provably correct). Working it through, giving it to the largest actually does work:

def works(T, a):
    if T <= 30 and any(x >> T > 0 for x in a):   # bit-length alone exceeds T
        return False
    S = multiset(a)
    for t in T-1, T-2, ..., 0:                   # second worth 2^t
        if S is empty or max(S) <= 0: return True
        x = pop largest demand
        x -= 2^t                                  # give the second to the largest
        push x back into S
        if max(S) still has bit t set:            # a second demand needed this bit
            return False                          # ...and nothing left can cover it
    return all demands in S are <= 0
 
# answer: binary search the smallest workable T in [n, n+33]

Checking the samples: $[5, 2]$ at $T = 3$: seconds worth $4, 2, 1$ — the $5$ takes the $4$ (owes $1$), the $2$ takes the $2$, the leftover $1$ finishes the $5$. At $T = 2$ the total worth is $3 < 5$. Answer $3$. $[1, 2, 3, 4, 5, 6]$ at $T = 6$: the seconds pair off demand-by-demand; at $T = 5$ the two smallest demands starve. Answer $6$.

Accepted.