Official Analysis (C++)

Explanation

First, let's determine the cards that Bessie will play for each mode. Intuitively, if she plays $x$ turns of the "higher mode", then she must play the $x$ highest cards in some order. Her score for "higher mode" can't improve if she switches out any card for a lower-numbered card. Even if the score for the "higher mode" stays the same, doing this could worsen our score for the "lower mode". As for her strategy, she always wants to play the smallest card available among all $x$ cards that is greater than Elsie's card. Therefore, the following algorithm is always optimal for "highest mode":

Let E = An array of Elsie's first x cards
let B = An array of Bessie's highest x cards
score = 0
for d from 1 to 2n:
  for elsie_card in E:
    if bessie_card with number (elsie_card + d) exists in B:
      remove elsie_card from E
      remove bessie_card from B
      add 1 to score

Directly implementing the above algorithm yields quadratic time for each $x$, which is too slow. We can use a segment tree to speed things up.

Essentially, the segment tree calculates the score for each $d$ within a interval of length $2^k$, where $k$ is the depth of the vertex from its leaves. For each vertex of the segment tree, we have to track the following:

• The maximum achievable score after pairing all Bessie cards with Elsie cards in the interval.
• The number of Elsie cards that have not been paired with a Bessie card.
• The number of Bessie cards that have not been paired with an Elsie card.

To merge two intervals into a bigger interval, we can pair all unpaired Elsie cards in the left interval with unpaired Bessie cards in the right interval. Therefore, the minimum of these two values will contribute to the score for the bigger interval.

The algorithm for "lower mode" can be determined similarly.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

struct Segtree {
	bool higher_mode;
	int n;

	struct item {
		int ans, bessie, elsie;
	};