CF 2021C2 - Adjust The Presentation (Hard Version)

Rating: 1900
Tags: constructive algorithms, data structures, greedy, implementation, sortings
Solve time: 57s
Verified: no

Solution

Problem Understanding

We have a fixed permutation a describing the initial order of team members in a line. During the presentation, the person currently at the front presents the next slide. After presenting, that same person may be inserted anywhere later in the line while the relative order of everybody else stays unchanged.

Another array b specifies who must present each slide. The question is whether there exists a sequence of allowed line modifications that makes the presentation order exactly equal to b.

The hard version adds up to 2 · 10^5 persistent updates. Each update changes one position of b, and after every modification we must answer again whether the presentation remains feasible.

The total sum of n, m, and q across all test cases is at most 2 · 10^5, which is the real constraint that matters. Any solution that recomputes the answer from scratch after each update would need roughly O(nq) or O(mq) work and would exceed the limit. We need something close to logarithmic time per update.

The subtle part of the problem is understanding what sequences b are actually achievable.

Consider:

a = [1,2,3]
b = [1,1,2,3]

This is possible. Member 1 presents, stays at the front, presents again, then moves behind 2.

Now consider:

a = [1,2,3]
b = [2,1]

This is impossible because member 1 starts at the front and must present the first slide before anyone else can.

A common mistake is to check only the relative order of consecutive slides. That fails on examples where the same member appears many times. The correct condition depends only on the first appearance of every member.

For example:

a = [1,2,3]
b = [1,3,3,2]

The first appearances occur at:

1 -> position 1
2 -> position 4
3 -> position 2

Member 3 appears before member 2 even though 2 stands ahead of 3 in the initial line. The answer is TIDAK.

Another easy pitfall is members that never appear.

a = [1,2,3]
b = [1]

Member 2 and member 3 never present. They should be treated as having first occurrence equal to infinity. Their absence must still participate correctly in the ordering checks.

Approaches

A brute force simulation is possible.

For every state of b, we could try to reconstruct the presentation process. One way is to maintain the current line and repeatedly check whether the required presenter is currently at the front. If so, move them somewhere valid and continue.

This approach is correct because it directly models the process. Unfortunately, even checking a single state may require O(m) or worse, and doing that after each of up to 2 · 10^5 updates is completely infeasible.

The key observation comes from looking at the first time each member appears in b.

Let first[x] be the earliest position where member x appears in b. If x never appears, set first[x] = +∞.

Suppose the initial order is:

a = [a1, a2, a3, ...]

Member a1 star