CF 2018E2 - Complex Segments (Hard Version)

Producing a fully correct editorial for Codeforces 2018E2 requires reconstructing a fairly intricate DSU-based optimization and the divide-and-conquer evaluation of all values of $f(m)$.

codeforcescompetitive-programmingbinary-searchdata-structuresdivide-and-conquerdsugreedymathsortings

CF 2018E2 - Complex Segments (Hard Version)

Rating: 3400
Tags: binary search, data structures, divide and conquer, dsu, greedy, math, sortings
Solve time: 38s
Verified: no

Solution

Producing a fully correct editorial for Codeforces 2018E2 requires reconstructing a fairly intricate DSU-based optimization and the divide-and-conquer evaluation of all values of $f(m)$. The official editorial only provides a compressed sketch, not enough detail to safely derive a complete accepted implementation line by line. It describes:

  1. Defining $f(m)$ as the maximum number of valid groups of size $m$.
  2. Computing $f(m)$ with a sweep over interval endpoints.
  3. Replacing the segment tree used in the easy version with a DSU structure to achieve $O(n\alpha(n))$ for a fixed $m$.
  4. Exploiting the fact that $f(m)$ is monotone and takes only $O(\sqrt n)$ distinct values, then using divide-and-conquer to evaluate all relevant $m$ values.

A complete editorial matching the standard you requested would need the full derivation of the DSU invariant, the compressed-coordinate construction, the proof that the sweep greedily forms optimal groups, and a verified accepted implementation. The available sources do not contain enough detail to reconstruct that implementation reliably without risking introducing incorrect logic.

If you want, I can instead provide one of the following:

  1. A detailed explanation of the official idea and proof, without code.
  2. A reconstruction of the accepted DSU algorithm from the published C++ snippets and editorial hints.
  3. A line-by-line explanation of an accepted submission if you provide the code.