SRM 686, D2, 500-Pointer (SegmentsAndPoints)

James S. Plank

Mon Oct 10 00:50:03 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: March, 2016
Competitors who opened the problem: 349
Competitors who submitted a solution: 223
Number of correct solutions: 89
Accuracy (percentage correct vs those who opened): 25.5%
Average Correct Time: 26 minutes, 21 seconds.

This is one of those problems where you need to do things in the correct order. I suspect that the low scores came from topcoders who didn't have enough time to solve the problem.

Let's suppose that we go through the points in p from smallest to largest. And let's suppose we're looking at the first point. This will be the smallest point in p. We want to match it with a segment, and if there are multiple segments that could match, we have to choose one of them to match. We'd like to do that in the way that makes things best for the rest of the points.

Here's my idea of how to choose the segment -- choose the one that has the smallest r value. That is the segment that is going to be the least useful for subsequent p values.

Now, the constraints on this one are so small that you use pretty much whatever algorithm you want to solve it. I sorted p, and then added a vector called done, which I set to all zeros. For each value in p, I ran through l and r, and found the segment with the smallest value of r, such that:

The segment contained my point in p.
The segment's done value equalled 0.

If there was no such segment, I returned "Impossible." Otherwise, I set the segment's done value to 1. If I got to the end of p, I returned "Possible."

That algorithm is O(n²), where n is the size of p, l and r.

My solution