Indian Computing Olympiad

Greedy Algorithms→Teleporters (IOI 2008)

You are participating in a competition that involves crossing Egypt from west to east along a straight line segment. Initially you are located at the westmost point of the segment. It is a rule of the competition that you must always move along the segment, and always eastward.

There are N teleporters on the segment. A teleporter has two endpoints. Whenever you reach one of the endpoints, the teleporter immediately teleports you to the other endpoint. (Note that, depending on which endpoint of the teleporter you reach, teleportation can transport you either eastward or westward of your current position.) After being teleported, you must continue to move eastward along the segment; you can never avoid a teleporter endpoint that is on your way. There will never be two teleporter endpoints at the same position. Endpoints will be strictly between the start and the end of the segment.

Every time you get teleported, you earn 1 point. The objective of the competition is to earn as many points as possible. In order to maximize the points you earn, you are allowed to add up to M new teleporters to the segment before you start your journey. You also earn points for using the new teleporters.

You can set the endpoints of the new teleporters wherever you want (even at non‐integer coordinates) as long as they do not occupy a position already occupied by another endpoint. That is, the positions of the endpoints of all teleporters must be unique. Also, endpoints of new teleporters must lie strictly between the start and the end of the segment.

Note that it is guaranteed that no matter how you add the teleporters, you can always reach the end of the segment.

Constraints:

• 1≤N≤10⁶
• 1≤M≤10⁶
• Distance between endpoints of segment≤2×10⁶

It helps to analyze why the last statement is true --- why will you always reach the end of the segment?

Construct a directed graph where the vertices represent the segments between teleporters.

• From each segment (except the last one) there is exactly one outgoing edge: walk to the right endpoint of the segment and see where the teleporter takes you.
• Each segment (except the first one) has exactly one incoming edge: the other end point of the teleporter at the left end of the segment.

Thus, the first segment has an outgoing edge but no incoming edge. As we walk, we can never close a cycle (because for each segment we have seen, we have already traversed its unique incoming edge), so we eventually trace out a path and exit via the last segment.

The nodes that are not visited on this path form (disjoint) cycles.

In other words, we start with a graph that consists of one path and several cycles. What happens when we add a teleporter?

1. A teleporter connects two segments across disjoint components.
   
   The corresponding segments in each cycle get split (one node becomes two) and we end up with a connection that forms a single larger cycle.
   
   Therefore:
• If we connect a path to a cycle, we get a longer path.
• If we connect a cycle to a cycle, we get a longer cycle.
2. A teleporter connects two segments in the same components.
   
   This splits the cycle into two disjoint cycles. This is not useful!
3. A teleporter is connected within a segment.
   
   This expands the current cycle with one edge and spawns a separate cycle with a single node (self loop).

Greedy algorithm:

• Find connected components of the graph and identify the path and all the cycles.
• Sort the cycles in descending order of size.
• Connect the path to the largest cycle — expands the path.
• Keep adding cycles in descending order of size till no cycles remain. At this stage, the entire graph is a single path.
• If you have not yet exhausted the M additional teleporters edges, alternately apply case 3 and case 1 — i.e., expand the path by one edge and spawn off a trivial cycle, then merge the trivial cycle back to form a longer path.

All these operations can be done in linear time. (Note: you don't have to actually do the operations above, just compute how the sizes change as a result of performing these operations!)

What about sorting? Since we know that the number is bounded by 10⁶, we can do a counting sort. Maintain an array A of size 10⁶ and record a count of how many times each value appears (when you read a value i, increment A[i]). After scanning the input, scan A and print out i A[i] times.

---