[Codeforces 1389F] Bicolored Segments

Problem Description

Problem Link

Given 2 * 1e5 ranges with two colors, find maximum ranges that ranges with different color may not overlap.

Solution

Solution from the tutorial

Bipartite Match on a special graph

If we consider the relationship of two ranges with different color overlap as an edge and each range as a vertex, the problem is to calculate the maxmium independent set of a special bipartite graph. And

|independent_set| = n - |match|

Here is a greed algorithm to find the max match of this graph.

For each range R sorted by right, if there are ranges connecting to it, match R with the range with minimal right.

To get better implementation, we can sort the range ends as events, and use two sets to maintain the range can be used in the match. Details can be found in code.

Segment Tree + DP

DP states:
dp[i][t] := for type `t`, the max number of chosen ranges with right end == i.

State transformation:
For each range R,
1. dp[R.right][R.t] = max(dp[1..R.left - 1][1 - R.t]) + 1
2. dp[1..R.left - 1][1 - R.t] += 1

Details can be found in code.

Posts

• [Codeforces 1391E] Pairs of Pairs

• [Codeforces 1393D] Rarity and New Dress

• Convex Hull Trick

• [Codeforces 1389G] Directing Edges

• [Codeforces 1389F] Bicolored Segments

• [Codeforces 1381C] Mastermind

• [Codeforces 1375G] Tree Modification

• [Codeforces 1375F] Integer Game

• [Codeforces 1375E] Inversion SwapSort

subscribe via RSS