Hello great codeforces community, I was trying to solve this problem, the core problem is simple: Given n lines, find maximum number line segments such that no two line segments intersect.

Formally: Given set A containing n line segments from point (Xs[i],0) to point (Xf[i],Yf[i]) inclusive for each integer (1 ≤ i ≤ n), with satisfy this condition: (1 ≤ n ≤ 200, -40000 ≤ Xs[i], Xf[i] ≤ 40000, 0 ≤ Yf[i] ≤ 40000; all n,Xs[i],Xf[i],Yf[i] are integers), let set B containing all subset of set A such that no pair of line segments in that set intersect. The problem is to find an element from set B with maximum length.

One valid example:

in the picture above there are 12 line segments: A={AB,BC,CD,EF,GH,IJ,KL,MN,OP,QR,ST,UV}

One of the solution (maximum subset of set A such that no two line segments intersect):

Here is informal explanation about the solution above:

Because AB intersect with BC "at point (1,2)", and BC intersect with CD "at point (2,0)" so if we select segment BC we can't select segment AB and CD, but if we select AB we can selecy CD, so the optimal one is not to select BC.

Because EF intersect with GH "at point (3.5,1)", so we must choose one of them, in this case I select GH (it's correct too if we select EF instead, so the solution isn't unique, but the size of solution must be unique).

Because IJ not intersect with any other line so obviously we must select it.

For group {KL,MN,UV} is similar to group {AB,BC,CD}, the optimal one is not to select MN.

For group {OP,QR,ST} because all segment intersect each other we can only choose one of them.

so the maximum size of subset from set A with no two intersecting segments is 7.

After I read this problem, I think it's maxflow problem, so I model the graph with rule like this:

• add edge from "source" to vertex (Xs[i],0) for each (1 ≤ i ≤ n) with capacity=1
• add edge from vertex (Xf[i],Yf[i]) to "snk" for each (1 ≤ i ≤ n) with capacity=1
• for each intersection: make new vertex, add capacity of that vertex with capacity=1 (I'll not explain how to add capacity to vertex here, it's a bit complicated, of course you can google it :) )
• for each segment when traveling from (Xs[i],0) to (Xf[i],Yf[i]) if found some intersection vertex:
• • if there is no previous intersection vertex add edge from vertex (Xs[i],0) to this intersection vertex with capacity=1
• • else add edge from previous intersection vertex to this intersection vertex with capacity=1
• • finally add edge from previous intersection vertex (or vertex (Xs[i],0) if there is no previous intersection vertex) to vertex (Xf[i],Yf[i]) with capacity=1

After implementing it, I submit my solution but surprisingly it only pass sample case (1 of 10 given case)

After long time debugging (at first I think the problem is with my maxflow implementation), finally build some random case (the example case given here), and here is the result of my maxflow:

fffffffuuuuuuu!! The maxflow is 8 instead of 7 (the correct answer).

I'm very surprised, I should re-design the graph modeling rule, but I have no idea how to handle this troll case.

Finally I give up with maxflow, and change strategy to backtracking (of course it's very slow) and it just AC on 2 of 10 given case, after heavy pruning it just AC on 4 of 10 given case, after time cut (if close to the time limit, stop process and return best so far) it AC on 6 of 10 given case, and finally add some greedy on backtracking part it AC on 7 of 10 given case.

I wonder how to get full score. Is maxflow possible for this problem?

I'm very curious, hope someone can give me a hand :)