[NOI 2019]Sequence

Difficulty Ratings

Idea Creativity: 2/5
Techniques Used: 3/5
Implementation : 2/5
Last week very hard, this week easier...

Problem Link

Link in simplified chinese by matthew99

Simplified Statement

Given two sequences $a,b$, both of length $1 \le N \le 2 \times 10^5$ consisting of positive integers. Pick $K$ elements on each sequence such that there exists at least $L$ integers $i$, where both $a_i$ and $b_i$ are chosen. Find the maximum possible sum of the chosen elements.

Solution

You realise that this problem probably is looking for some kind of greedy, but it is hard to find one or prove this. In this case, you might write stress test and try your greedies out. In this problem, a lot of different fishy-looking solutions work, and most of them can be proved by min-cost flow.

Consider the following construction. Create a source $S$, a sink $T$, $N$ nodes, each for an element in $a$; another $N$ nodes, each for an element in $b$, and finally, two additional nodes $C$ and $D$. Then. create the following edges:
$S \rightarrow A_i$ with capacity $1$ and cost $a_i$
$A_i \rightarrow B_i$ with capacity $1$ and cost $0$.
$A_i \rightarrow C$ with capacity $1$ and cost $0$.
$C \rightarrow D$ with capacity $K-L$ and cost $0$.
$D \rightarrow B_i$ with capacity $1$ and cost $0$.
$B_i \rightarrow T$ with capacity $1$ and cost $b_i$
The max-cost K flow is the answer. Just negate all costs then it would become min cost flow. Obviously, just running flow here would be too slow.

To optimize, you realise that the flows through the edges $S \rightarrow A_i$ and $B_i \rightarrow T$ will never be retracted. This means that if you have selected an element in the process, then you would never deselect it. With this, we can easily formulate a greedy: If the $C \rightarrow D$ edge isnt full (ie. there are less than $K-L$ pairs that have different indices), then you can just select the maximum unselected element in each side, and take both of them. Otherwise there are 3 cases, 1st is you find $i$ such that $a_i$ and $b_i$ are both unselected and $a_i+b_i$ is maximum, and then you select both. 2nd is you find $i$ such that $b_i$ is selected and $a_i$ isnt and $a_i$ is maximum, and you also find $j$ such that $b_j$ is not selected and $b_j$ is maximum, then you choose $a_i$ and $b_j$. 3rd is the mirror situation of 2nd. You just find the maximum value increased out of the 3 cases and pick that. Repeat $K$ times then you'll get the answer. You can easily maintain them with some priority_queues or sets.

Comments

If you are new to greedy problems based on flow, you might want to try this very typical codechef problem...