G - Longest Chord Chain Editorial by en_translator

MMNMM's user editorial

This is a translation of a user editorial by MMNMM.

As described in the official editorial, the answer is at least \\(k\\) if and only if we can pick \\(k\\) or more nested intervals.

Let us say a set of intervals \(\lbrace I _ 1,I _ 2,\ldots,I _ k\rbrace\) is monotonically indexable when \(I _ 1\subset I _ 2\subset\cdots\subset I _ k\).

Denote the given \(N\) chords by \((a _ i,b _ i)\ (1\leq a _ i\lt b _ i\leq2N)\). It is sufficient to find the maximum size of a monotonically indexable subset of a set of intervals \(\lbrace\lbrack a _ i,b _ i\rbrack\rbrace\cup\lbrace\lbrack b _ i,a _ i+2N\rbrack\rbrace\).

Proof

First, we will show that the answer is at least this value.

Consider a monotonically indexable subset \(\lbrace I _ 1,I _ 2,\ldots,I _ k\rbrace\) of size \(k\). Since any interval’s length is less than \(2N\), there exists a real number \(x\ (0\leq x\lt2N)\) such that neither \(x\) nor \(x+2N\) is contained in the largest interval \(I _ k\). By cutting and unrolling the circle at the point corresponding to the real number \(x\) (namely, at point \(x\) itself if \(x\) is an integer, and at an arbitrary point between points \(n\) and \(n+1\) for the integer \(n\) with \(n\lt x\lt n+1\) if \(x\) is not an integer, where point \(2N+1\) refers to point \(1\) for convenience), we see that the \(k\) chords corresponding to the intervals satisfy the condition. Hence, the answer is at least \(k\).

Conversely, we show that there exists a monotonically indexable subset whose size is at least the answer to the problem.

Given a set of \(k\) chords that satisfy the condition, take a point on the circle to cut. (There are two possible places, but the choice does not affect to the discussion.) Suppose that this point is between points \(i\) and \(i+1\). Rename the points as points \(i+1,i+2,\ldots,i+2N\) in the order you encounter when you traverse the circle clockwise starting from the chosen cutting point. Then we see that the set of chords is a monotonically indexable subset of \(\lbrace\lbrack a _ i,b _ i\rbrack\mid i+1 /2\notin\lbrack a _ i,b _ i\rbrack\rbrace\cup\lbrace\lbrack b _ i,a _ i+2N\rbrack\mid i+1 /2\in\lbrack a _ i,b _ i\rbrack\rbrace\). Since \(\lbrace\lbrack a _ i,b _ i\rbrack\mid i+1 /2\notin\lbrack a _ i,b _ i\rbrack\rbrace\cup\lbrace\lbrack b _ i,a _ i+2N\rbrack\mid i+1 /2\in\lbrack a _ i,b _ i\rbrack\rbrace\) is a subset of \(\lbrace\lbrack a _ i,b _ i\rbrack\rbrace\cup\lbrace\lbrack b _ i,a _ i+2N\rbrack\rbrace\), the claim has been proven.

The sought value can be found by sorting the intervals by one end, and finding the length of a longest increasing (or decreasing) subsequence of the other ends.

Sample code is shown below.

#include <vector>
#include <algorithm>
#include <iostream>
#include <ranges>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    vector<pair<unsigned, unsigned>> intervals;
    intervals.reserve(2 * N);
    for (unsigned i{}, a, b; i < N; ++i) {
        cin >> a >> b;
        if (a > b)
            swap(a, b);
        intervals.emplace_back(a, b); // Add [a, b]
        intervals.emplace_back(b, a + 2 * N); // and [b, a + 2N]
    }
    // Sort by one endpoint
    ranges::sort(intervals, greater{}, &pair<unsigned, unsigned>::second);

    // and find an LIS (Longest Increasing Subsequence)
    vector<unsigned> lis_dp;
    for (const auto l : intervals | views::keys)
        if (const auto it{ranges::lower_bound(lis_dp, l)}; it != end(lis_dp))
            *it = l;
        else
            lis_dp.emplace_back(l);

    // The answer is the length of LIS
    cout << size(lis_dp) << endl;
    return 0;
}

posted:
last update: