Lost Civilization — Deon Nicholas

Problem

Imagine you start with some sequence of numbers, each between $1$ and $10^9$ . At any point, you can take an index $i$ , look at the item $x_i$ at that position, and insert the number $x_i + 1$ immediately after it. That grows the sequence by one. You can do this as many times as you want, in any order, and then stop.

In this problem you are given the ending sequence: an integer $n$ (up to $3 \cdot 10^5$ ) and the final sequence $a_1, \ldots, a_n$ .

In the easy version (A1), your task is to find the shortest original sequence that could have generated the final sequence, and print its length.

In the hard version (A2), let $f(b)$ be the A1 answer for a sequence $b$ . You have to print the sum of $f(a_l, \ldots, a_r)$ over all subsegments $1 \leq l \leq r \leq n$ .

Initial Observations

Generate.
Ad hoc problem.
Staircase?
Runs; pseudo-runs.
Reverse; recursion.
Plus zero or plus one.
Greedy.
[Examine Examples] (with small variations); [Work Backward]; [Write It Out].
$O(n \log n)$ .
Rightmost; sweep left-to-right or right-to-left; "exposed".

IdeaWorking backward: who generated whom?AC

Examine Examples

Start with the sample test cases. The first one is $[1, 2, 3, 4, 5]$ : clearly it could have started as just $[1]$ — the $1$ generates a $2$ , the $2$ generates a $3$ , and so on. The answer is $1$ . The second one is $[1, 3, 5, 7, 9]$ : the items are separated by two, and we only ever insert by adding one, so no item could have generated any other. The answer is $5$ .

So it seems like we're interested in the number of "runs". By a run I mean a staircase-like stretch where each item either repeats the previous number or goes up by exactly one, like $[3, 4, 4, 5, 5]$ (the plus-zero-or-plus-one shape from my observations).

Generate and Test

A first conjecture, then: maybe the answer is just the number of runs. Let's test it on the last sample, $[9, 8, 9, 2, 3, 4, 4, 5, 3]$ , which is a strange and complicated case. The $9$ is a run by itself. Then $8, 9$ is a run. Then $2, 3, 4, 4, 5$ is a run (a $3$ is allowed to generate two different $4$ 's). Then the last $3$ is a run. So the answer should be $4$ .

But the expected output says $3$ . The conjecture is wrong, and something surprising is going on: somehow that final $3$ doesn't need to be in the original sequence.

Work Backward

Given the ending sequence, what we really want is to reverse the process. If a number $x$ is followed by $x + 1$ , then that pair is possible to undo. But it quickly gets complicated on other examples (I also played with cases such as $[3, 4, 5, 4]$ ). One thing to realize is that after an item, you can generate any number of copies of the item plus one: a $2$ can be followed by several $3$ 's, and then in between, those $3$ 's can generate $4$ 's. So you can get sequences like $2, 3, 4, 3, 4, 3, 4, 5$ entirely out of a single $2$ . In fact $2, 3, 4, 4, 5, 3$ , the tail of the strange sample above, can also come entirely out of a single $2$ . The structure is something like a series of stacks, or maybe even a tree: which item generated which?

Observation.

For a given item $a_i$ , which item to its left could have generated it? If some solution has any element generating $a_i$ , you can swap that choice for the closest element to its left that equals $a_i - 1$ , and the solution still works. So greedy is safe: if $a_i$ attaches at all, attach it to the closest possible parent.

Key Question

Under what conditions, exactly, can one item have generated another?

Let's work through the last sample. The first $9$ stands alone. Then comes the $8$ — and once you put the $8$ down, the $9$ before it cannot be used anymore: it can't have spawned the $8$ , and nothing later can attach to that $9$ with the $8$ sitting in between. So the $9$ dies. The next $9$ attaches to the $8$ . Then the $2$ arrives, and it kills both the $8$ and the $9$ the same way. And at the very end, the $3$ attaches to the $2$ far to its left — everything in between ( $3, 4, 4, 5$ ) is bigger than or equal to it, and all of that could have been generated after the $3$ was. That's why the answer is $3$ and not $4$ .

Key Observation

Sweep from left to right, and maintain a set of items that are still "alive", meaning still allowed to be the parent of a later item. To add $a_i$ : first delete everything in the set that is $\geq a_i$ (those can no longer be used, with $a_i$ sitting after them). Then, if the largest item left in the set equals $a_i - 1$ , attach $a_i$ to it, at no cost. Otherwise $a_i$ is a "root" — it had to be in the original sequence — so add one to the answer, and empty the whole set, because nothing before a root can be the parent of anything after it. Either way, insert $a_i$ into the set. The answer is the number of roots.

Write It Out

You kind of have to write this out to see what's going on. The whole sweep on $[9, 8, 9, 2, 3, 4, 4, 5, 3]$ :

item   deleted (>= item)   set left    attaches to    set after      roots
9      -                   {}          no: root       {9}            1
8      9                   {}          no: root       {8}            2
9      -                   {8}         8              {8,9}          2
2      9, 8                {}          no: root       {2}            3
3      -                   {2}         2              {2,3}          3
4      -                   {2,3}       3              {2,3,4}        3
4      4                   {2,3}       3              {2,3,4}        3
5      -                   {2,3,4}     4              {2,3,4,5}      3
3      5, 4, 3             {2}         2              {2,3}          3

Three roots: the first $9$ , the $8$ , and the $2$ . Everything else attaches to one of them.

Algorithm

S = empty set;  answer = 0
for i = 1..n:
    delete everything >= a[i] off the back of S
    if (a[i] - 1) is not in S:
        answer += 1          # a[i] is a root: it was in the original
        S = empty set        # nothing before a root can parent anything after
    insert a[i] into S
output answer

This runs in $O(n \log n)$ , amortized: every item is inserted once and deleted at most once, so even the repeated deleting is fine. I got a wrong answer here at some point (my WA) — I honestly don't remember now what it was — but the version above is correct (my accepted A1).

IdeaA2: summing over all subsegmentsAC

To restate what A2 is asking: let $f(b)$ be the A1 answer for a sequence $b$ , meaning the length of the shortest original sequence that could have generated $b$ . We now need the sum of $f(a_l, \ldots, a_r)$ over every subsegment $l \leq r$ . That is noticeably more complicated.

A few thoughts to start:

Keep the same sweep as A1.
The roots probably still matter.
What happens when you add one new element in?

That last one feels like the question to chase:

Key Question

What happens to all these subsegment answers when a single new element $a_i$ is added on the right?

Problem Simplification

Anchor on the right endpoint. Every subsegment ends somewhere, so as we sweep, we can consider just the windows that end exactly at the current position $i$ : handle those when we arrive at $i$ , then move the anchor to $i + 1$ . Sweeping this way naturally partitions all the subsegments, with nothing missed and nothing double-counted.

Exploit the Constraints

And how does a window's answer change when $a_i$ arrives at its right end? The sweep from Idea 1 already tells us: $a_i$ either attaches to a parent (the closest $a_i - 1$ to its left that is still alive), or it's a root. So run the exact same sweep, with the exact same set, but at each step record who the parent is. Call its position $P_i$ , with $P_i = 0$ if $a_i$ is a root.

Now compare each window ending at $i$ against the matching window ending at $i - 1$ :

If $a_i$ is a root, it could not have been generated in any window: $f(a_l, \ldots, a_i) = f(a_l, \ldots, a_{i-1}) + 1$ for every left endpoint $l$ .
If $a_i$ has a parent at position $P_i$ : for windows with $l \leq P_i$ , the parent is inside the window, and the answer does not change. For windows with $l > P_i$ , the parent is cut off, so $a_i$ is a root of that window, and the answer goes up by one. There are $i - P_i$ such windows.

So the total over windows ending at $i$ depends only on the total over windows ending at $i - 1$ , which means we can write it as a DP:

Key Observation

Let $dp_i$ be the sum of $f$ over all windows ending at $i$ :

dp_i = \sum_{l \leq i} f(a_l, \ldots, a_i) .

Then

dp_i = dp_{i-1} + (i - P_i),

where $P_i$ is the position of the parent that the Idea 1 sweep attaches $a_i$ to, or $0$ if $a_i$ is a root. The final answer is $dp_1 + dp_2 + \cdots + dp_n$ .

The example I was walking through and playing with was $[1, 2, 2, 3, 2, 3, 4, 1]$ :

a     =  1   2   2   3   2   3   4   1
P     =  0   1   1   3   1   5   6   0
i - P =  1   1   2   1   4   1   1   8
dp    =  1   2   4   5   9  10  11  19     answer = sum of dp = 61

You can spot-check a column: the windows ending at position $5$ are $[2]$ , $[3,2]$ , $[2,3,2]$ , $[2,2,3,2]$ , $[1,2,2,3,2]$ , with answers $1 + 2 + 2 + 3 + 1 = 9 = dp_5$ .

Algorithm

S = empty set of (value, position)
for i = 1..n:
    delete everything with value >= a[i] off the back of S
    if S is empty or its largest value != a[i] - 1:
        P[i] = 0             # root
        S = empty set
    else:
        P[i] = position of that largest value
    insert (a[i], i) into S
 
dp[0] = 0
for i = 1..n:  dp[i] = dp[i-1] + (i - P[i])
answer = dp[1] + dp[2] + ... + dp[n]     # use 64-bit integers

This is the same sweep as A1, with the same set, still $O(n \log n)$ . You have to use long longs so the sum doesn't overflow. Accepted (my A2 submission).

Lesson

I actually first tried a more complicated way of computing $P_i$ , using mins and maxes over the items sitting between $a_i$ and its candidate parent. It got unwieldy. The A1 sweep was already computing exactly this parent the whole time — I should have reused what I'd already built instead of deriving it again from scratch.

Review

Call an item of the sequence a root if it could not have been generated by any item to its left. Every root must have been in the original sequence, and everything else can be generated starting from the roots. So for A1, the length of the shortest original sequence is the number of roots. The path:

Play with the samples. A chain of consecutive numbers can grow out of a single item ( $[1,2,3,4,5]$ has answer $1$ ), and gaps of two can't be crossed ( $[1,3,5,7,9]$ has answer $5$ ). But counting staircase runs (stretches that go up by zero or one at each step) is not enough: $[9,8,9,2,3,4,4,5,3]$ looks like four runs and its answer is $3$ , because the final $3$ can attach to the $2$ far to its left.
Attach greedily. If $a_i$ could have been generated at all, then it could have been generated by the closest $a_i - 1$ to its left that is still usable: any other valid choice can be swapped to that one. So each item has only one candidate parent to check.
Sweep, keeping the set of possible parents. Go left to right, maintaining a set of the items that are still allowed to become parents. To add $a_i$ : first delete everything $\geq a_i$ from the set, since with $a_i$ after them they can never be parents again. Then, if the largest remaining item equals $a_i - 1$ , attach $a_i$ to it. Otherwise $a_i$ is a root: count it, and empty the set, because nothing before a root can be the parent of anything after it. The A1 answer is the number of roots. [KQ] [1]
For A2, anchor on the right endpoint. Let $f(b)$ be the A1 answer for a sequence $b$ ; A2 asks for the sum of $f$ over all subsegments. Partition the subsegments by their right endpoint, and let $dp_i$ be the sum of $f$ over the windows ending at $i$ . When $a_i$ arrives, windows that still contain its parent keep the same answer, and windows that cut the parent off pay one each: $dp_i = dp_{i-1} + (i - P_i)$ , where $P_i$ is the parent's position from the same sweep, or $0$ for a root. [KQ] [2]
Sum the $dp$ values with 64-bit integers. The A2 code is the A1 sweep, only also recording each item's parent.

(My accepted A1 and A2 submissions.)

References

Problem-solving techniques used:

Examine Examples

Look at examples with small variations, and watch how the answer changes as one thing changes. The whole structure of this problem came out of the last sample being $3$ instead of $4$ : one surprising example taught more than the friendly ones.

Generate and Test

The run-counting conjecture was quick to state and quick to disprove. Once it failed, I studied the failing example, and that example carried me to the real question of how one item can generate another. Later, the sweep itself was also a conjecture — I didn't prove it in contest, I tested it on the examples and submitted.

Work Backward

The process is described forward (insert $x_i + 1$ after $x_i$ ), but the input is the ending sequence, so the whole problem is about undoing it: who could have generated whom?

Pursue Extremes

Sweeping is a form of this: when things are ordered, pick an ordering — left to right here — and attack the items in that order. Deciding each item's fate at the moment it arrives is what made the set data structure fall out.

Write It Out

The stack-like behavior of the alive set is the kind of thing you have to trace by hand. After writing out the full table for the last sample, I trusted the algorithm enough to code it.

Exploit the Constraints

Going back to what I'd already built: the A1 sweep was already computing every item's parent, which is exactly what the A2 recurrence needs (the lesson from Idea 2).

Learning points:

This was a cool ad hoc problem. I don't think I'm very good at ad hoc problems, but I am getting better — and there are going to be more and more of them, so getting to a reasonable hypothesis quickly is the best strategy for me. Learn to love the ad hoc problem.
Looking at small examples, and at how the answer changes when you add or change one thing, has been helpful again and again.
I first tried a complicated from-scratch way of computing the parents in A2 before realizing the A1 sweep already had them (the lesson from Idea 2). Reuse what you've already built.

Topics:

Ad hoc / constructive
Greedy
Dynamic programming (DP)
Combinatorics / counting
Data structures