Codeforces
CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage
  1. Home
  2. /
  3. Codeforces
  4. /
  5. Contests
  6. /
  7. Educational Codeforces Round 190 (Rated for Div. 2)
  8. /
  9. D. Good Schedule
  10. /
  11. Hints: Good Schedule

Hints: Good Schedule

For any subarray $A[L \ldots R]$, consider the lex-smallest maximal subsequence that is a permutation of $1, 2, \ldots, k$ for the largest possible $k$.

This is obtained greedily: find the leftmost occurrence of $1$ in $[L, R]$, say at position $w_1$. Then the leftmost occurrence of $2$ after $w_1$, say at position $w_2$. Continue until no next value exists. The index sequence $(w_1, w_2, \ldots, w_k)$ is the greedy chain of $A$ from $L$.

Define the greedy chain for $B$ from $L$ the same way: leftmost $1$ in $B$, then leftmost $2$ after it, etc.

Can you characterise when a segment $[L, R]$ is valid in terms of these two chains?

Answer to Hint 1: A segment $[L, R]$ is valid if and only if the greedy chains of $A$ and $B$ from $L$ are identical — same length and same index sequence.

Why sufficient: if both chains are $(w_1, \ldots, w_k)$, then on each chain day $w_j$ we have $a_{w_j} = b_{w_j} = j$ (both watch episode $j$, good). On any non-chain day $i$ in $(w_{j-1}, w_j)$, neither $a_i$ nor $b_i$ equals $j$ (otherwise the chain would have advanced earlier), so neither watches.

Why necessary: if the chains differ, there is a first index $k$ where they diverge. At that point one of Alice/Bob is ready to watch episode $k$ (their chain has advanced to level $k-1$) but the other is not yet at that episode — creating a mismatch day.

At what type of position can the two chains first diverge?

Answer to Hint 2: Call a position $i$ an agree position if $a_i = b_i$, and a disagree position if $a_i \ne b_i$.

Agree positions never cause a divergence: if the current expected level is $\ell$ and $a_i = b_i = \ell$, both chains advance together. If $a_i = b_i \ne \ell$, both chains skip together.

Divergence can only happen at a disagree position $i$ where exactly one of $a_i, b_i$ equals the current expected level $\ell$. For instance, if $a_i = \ell$ and $b_i \ne \ell$: the $A$-chain advances to level $\ell$ at position $i$, but the $B$-chain does not. The segment becomes invalid at position $i$.

So: a segment $[L, R]$ is valid iff it contains no divergence position. What is the “current expected level” at each position, and how does it depend on $L$?

Answer to Hint 3: The current expected level at position $i$ (for segment starting at $L$) is $\ell = $ (number of agree positions in $[L, i-1]$ that are chain elements) $+ 1$.

More concretely: both chains advance together at every agree position in the chain. The agree chain positions are exactly $w_1 < w_2 < \cdots$ where $w_k$ is the first position $\ge L$ with $a = b = k$. The expected level at position $i$ is $k + 1$ where $w_k < i \le w_{k+1}$ (and $0 + 1 = 1$ before $w_1$).

So position $i$ is a divergence position for segment starting at $L$ iff:

  • $a_i \ne b_i$, and
  • $a_i = \ell$ or $b_i = \ell$, where $\ell$ is the current expected level.

The segment $[L, R]$ is valid iff no divergence position falls in $[L, R]$.

How do you efficiently find the first divergence position for each starting index $L$?

Answer to Hint 4: Fix the agree positions for level $k$: the sorted list $W_k$ of positions where $a_i = b_i = k$. The chain from $L$ uses $w_k = $ first element of $W_k$ after $w_{k-1}$.

Between two consecutive chain elements $w_k$ and $w_{k+1}$, the expected level is $k + 1$. Any disagree position $i$ in this interval with $a_i = k+1$ or $b_i = k+1$ is a divergence.

Precompute:

  • $W_k$ = sorted positions where $a_i = b_i = k$.
  • $D_k$ = sorted positions where $a_i \ne b_i$ and ($a_i = k+1$ or $b_i = k+1$) — disagree positions dangerous at expected level $k+1$.

Define $\mathrm{FB}[j]$ for each agree position $j$ (at level $k$) as the first divergence in the chain starting at $j$: look for the first $D_k$ element in $(j, \mathrm{nxt}[j])$; if none, delegate to $\mathrm{FB}[\mathrm{nxt}[j]]$.

How do you compute $\mathrm{FB}[j]$ and then answer each query for $L$?

Answer to Hint 5: Compute $\mathrm{FB}[j]$ right to left (since $\mathrm{nxt}[j] > j$). For agree position $j$ at level $k$:

$$\mathrm{nxt}[j] = \text{first element of } W_{k+1} \text{ after } j \quad (\infty \text{ if none})$$ $$\mathrm{d} = \text{first element of } D_k \text{ in } (j,\, \mathrm{nxt}[j])$$ $$\mathrm{FB}[j] = \begin{cases} \mathrm{d} & \text{if } \mathrm{d} \text{ exists} \\ \mathrm{FB}[\mathrm{nxt}[j]] & \text{if } \mathrm{nxt}[j] \le n \\ n + 1 & \text{otherwise (no divergence ever)} \end{cases}$$

For each start $L$:

  1. $w_1 =$ first element of $W_1 \ge L$.
  2. Before $w_1$: expected level is $1$; check if any $D_0$ element (disagree with $a_i = 1$ or $b_i = 1$) lies in $[L, w_1 - 1]$.
  3. From $w_1$ onward: first divergence is $\mathrm{FB}[w_1]$.
  4. $\mathrm{firstDiv}(L) = \min(\text{step 2 result},\; \mathrm{FB}[w_1])$.
  5. Valid right endpoints for $L$: $\mathrm{firstDiv}(L) - L$.

All lookups are binary searches. Time: $O(n \log n)$.

Reformulation. A segment $[L, R]$ is valid iff the greedy chains of $A$ and $B$ from $L$ — that is, the lex-smallest maximal subsequences of $A[L \ldots R]$ and $B[L \ldots R]$ that are permutations of $1, 2, \ldots, k$ — are identical index sequences.

Divergence positions. Both chains advance together at every agree position ($a_i = b_i$). A disagree position $i$ ($a_i \ne b_i$) causes divergence when the expected level $\ell$ satisfies $\ell \in \{a_i, b_i\}$ — one side advances the chain, the other does not.

Precomputation. Iterate $i = 1$ to $n$:

  • $a_i = b_i$: append $i$ to $W_{a_i}$.
  • $a_i \ne b_i$: append $i$ to $D_{a_i - 1}$ and to $D_{b_i - 1}$.

($W_k$ = agree positions at level $k$; $D_k$ = disagree positions dangerous when expected level is $k + 1$.) All lists are already sorted.

Compute $\mathrm{FB}[j]$. Process positions $j = n$ down to $1$; skip disagree positions. For agree position $j$ at level $k = a_j$:

  • $\mathrm{nxt}[j]$ = first element of $W_{k+1}$ after $j$ (binary search; $n+1$ if none).
  • $\mathrm{d}$ = first element of $D_k$ in $(j, \mathrm{nxt}[j])$ (binary search).
  • $\mathrm{FB}[j] = \mathrm{d}$ if $\mathrm{d} \le n$; else $\mathrm{FB}[\mathrm{nxt}[j]]$ if $\mathrm{nxt}[j] \le n$; else $n+1$.

Answer queries. For each $L = 1$ to $n$:

  • $w_1$ = first element of $W_1 \ge L$.
  • $\mathrm{d_0}$ = first element of $D_0 \ge L$ that is $< w_1$.
  • $\mathrm{firstDiv} = \min(\mathrm{d_0},\; w_1 \le n \mathbin{?} \mathrm{FB}[w_1] : n+1)$.
  • Add $\mathrm{firstDiv} - L$ to the answer.

Correctness. Before $w_1$ the expected level is $1$, so only $D_0$ can cause divergence. From $w_1$ onward, $\mathrm{FB}[w_1]$ chains through each agree interval and reports the first dangerous disagree position encountered.

Complexity. $O(n \log n)$ per test case.