CS
Problems Base course RU

Problem

Village labels on a map

satisfiability connectivity graph geodata points

A cartographer is labelling villages on a map. A village’s label is a rectangle of height 2h, vertically centred on the village’s point, and horizontally either right next to the point on the right or right next to it on the left; there are no other places. The label width w differs from village to village: it depends on the length of the name. Labels must not overlap each other and must not cover the points of other villages; touching at the edges is allowed, and a village’s point may lie on the edge of another label.

The label of a village at point (x, y) on the right occupies the rectangle [x, x + w] × [y − h, y + h], on the left [x − w, x] × [y − h, y + h]. Two labels overlap if their rectangles have a common interior point. A label covers a village if its point lies strictly inside the rectangle.

Place the labels or say that it is impossible.

Input

The first line holds n and h (1 ≤ n ≤ 2000, 1 ≤ h ≤ 105). Then n lines x y w: the village’s coordinates in metres and its label width (|x|, |y| ≤ 3 · 106, 1 ≤ w ≤ 105). No two villages stand at the same point.

Output

NO if the labels cannot be placed. Otherwise YES and on the second line n letters: R if the village’s label is on the right, L if on the left, in the order of villages in the input. Any correct placement will do.

Tests 4 to 8 are the 675 towns and villages of the South Moravian Region from the GeoNames gazetteer at five font sizes: a letter 60, 80, 96, 98 and 150 metres wide, with h equal to the letter width.

Examples

Example 1

Input
3 2
0 0 6
8 0 6
20 0 6
Output
YES
RRR

Example 2

Input
3 2
0 0 10
4 0 10
8 0 10
Output
NO

Limits

Time · Python
8000 ms
Time · Go
2000 ms
Memory
256 MB
Judging
12 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Each village has exactly two options. Write it as a Boolean variable: “label on the right” or not. What does the condition “the labels of villages i and j in these positions overlap” look like?

2Hint 2

“Not (A and B)” is “not A or not B”, a disjunction of two variables. And a disjunction of two variables can be read as two implications: if A then not B, and if B then not A. Draw all these implications as arrows.

3Hint 3

If the arrows lead from “right” to “left” for one village and back, what does that mean?

4The idea

This is a 2-SAT problem: a set of conditions of the form “a or b”, where a and b are variables or their negations. For village i introduce two statements: Ri, “the label is on the right”, and ¬Ri, “on the left”. Each pair of positions in which two villages’ labels overlap forbids that combination: ¬(p ∧ q), that is, the arrows p → ¬q and q → ¬p. A position in which a label covers another village is forbidden by itself: the arrow p → ¬p.

This gives an implication graph on 2n vertices. Find its strongly connected components. If Ri and ¬Ri are in one component, then “right” implies “left” and “left” implies “right”, and neither position is possible: the answer is NO. Otherwise a placement exists, and the order of components gives it: for each village choose the statement whose component stands further along the arrows of the condensation. Tarjan closes components starting from the sinks, so that is the statement with the smaller component number.

5Walkthrough

Why the choice “whatever is further along the arrows” contradicts no condition. Let p be chosen, and let there be an arrow p → q. The implication graph is symmetric: together with it there is an arrow ¬q → ¬p. If ¬q had been chosen, the component of ¬q would stand further than that of q; but ¬q → ¬p, so ¬p stands no earlier than ¬q, and p → q puts q no earlier than p. That gives the chain “p no further than q, q before ¬q, ¬q no further than ¬p”, that is, ¬p further than p, yet p was chosen. A contradiction.

The pairs that may interfere are found by sorting the villages by y: labels overlap vertically only for villages whose y differ by less than 2h. The village points a label covers are found just as quickly.

The most telling tests are the sixth and seventh. With a 96-metre letter the labels of South Moravia can be placed. With 98 they cannot, and a trio of villages is to blame: the labels of Horní Loučky and Újezd u Tišnova fit side by side in only one way, the first on the right and the second on the left, and Újezd’s label on the left covers the village of Řikonín.

5+Solution
6Complexity

The implication graph has 2n vertices and two arrows per forbidden pair; Tarjan is linear in their number. Finding the pairs after sorting depends on the density of villages: O(n²) in the worst case, if all villages are in one strip of height 2h, almost linear on real maps.

7Common mistakes
  • Greed from west to east. Put a label on the right if it fits, otherwise on the left. On the map of Moravia with an 80-metre letter this fails, although a placement exists: a greedy choice in the west takes room from villages further east. In the eleventh test a three-village trap is repeated 400 times.
  • Forgetting the village points. A label that covers a neighbouring village is forbidden even when it overlaps no label.
  • Strictness of comparisons. Touching at the edges is allowed: comparisons with the ends of segments are strict.
  • The wrong order. Taking the statement from the component that stands earlier along the arrows means choosing something from which something else follows, and breaking the conditions.

Algorithms behind it

GRA Algorithm Strongly connected components Groups of vertices where any can reach any: Tarjan in one traversal, Kosaraju in two, O(V + E). O(V + E) 2 problems GRA Algorithm 2-SAT Conditions “a or b”: an implication graph, strongly connected components and the answer in O(n + m); on real scores. O(n + m) 1 problem
The algorithms catalogue