CS
Problems Base course RU

Problem

Two hands

satisfiability graph connectivity

A pianist decides which hand plays each note. A note sounds from time s to time e, and two notes sound together if their intervals [s, e) intersect. For each pair of notes of different pitch sounding together, two rules apply:

  • the hands do not cross: the lower note cannot be in the right hand while the upper one is in the left;
  • a hand takes at once no wider than the stretch S: if the notes are more than S semitones apart, different hands play them.

Two notes of the same pitch sounding together are one key (this happens when two voices meet in unison), and no rules apply to them. How many notes one hand has does not matter. Assign the notes to hands or say that two hands are not enough.

Tests three to ten are real pieces from MIDI files of the Mutopia project: preludes by Bach and Chopin, two Joplin rags and a Bach organ toccata, each at a stretch that is enough and at a smaller one.

Input

The first line holds n and S (1 ≤ n ≤ 2 · 10⁴, 1 ≤ S ≤ 60). Then n lines of three integers: the start s, the end e and the pitch p of a note (0 ≤ s < e ≤ 10⁶, 0 ≤ p ≤ 127). The pitch is the key number, as in MIDI: adjacent numbers are a semitone apart, and 60 is middle C. There are at most 2 · 10⁵ pairs of notes sounding together.

Output

If two hands are enough, YES, and on the second line n letters: the i-th is L if the i-th note is played by the left hand and R if by the right. If there are several assignments, output any. If two hands are not enough, the single word NO.

Examples

Example 1

Input
4 12
0 4 48
0 4 64
2 6 72
4 8 52
Output
YES
LRRL

Example 2

Input
3 12
0 4 36
0 4 60
0 4 84
Output
NO

Limits

Time · Python
5000 ms
Time · Go
1000 ms
Memory
256 MB
Judging
15 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 note has two options, left or right. Write both rules for a pair of notes a below b as conditions of the form “this or that” about two notes at once. How many such conditions does one pair give?

2Hint 2

“The hands do not cross” is “a left or b right”. “Wider than the stretch” is two conditions: “a right or b right” (not both left) and “a left or b left” (not both right). All conditions have two literals. What algorithm solves such formulas in linear time?

3The idea

2-SAT. A variable is a note, “true” is the right hand. Each condition “x or y” gives two arrows ¬x → y and ¬y → x in an implication graph on 2n literals. Two hands are not enough exactly when some note and its negation end up in one strongly connected component; otherwise a note is in the right hand if its “right” component comes after its “left” component in topological order. The proof is in the article.

4Walkthrough

Sort the notes by start. For each note go through the following ones while they start before its end: these are all the notes sounding together with it, and the enumeration costs as much as there are pairs (at most 2 · 10⁵). Skip notes of the same pitch. For a pair of lower a and upper b, add the crossing condition, and if b − a > S, two more. Literal 2i is note i right, 2i + 1 left, the negation is x ^ 1. Components are Tarjan with its own stack: its component numbers go in reverse topological order, so a note is in the right hand if the number of the component of 2i is smaller than the number of the component of 2i + 1.

4+Solution
5Complexity

O(n log n + m), where m is the number of pairs sounding together: sorting, one to three pairs of arrows per pair of notes, and one traversal of a graph with 2n vertices and at most 6m arrows.

6Common mistakes
  • Deciding moment by moment. This is wrong.py: each note gets a hand at the moment it starts, with the notes sounding at that moment split at the widest gap in pitch. But the choice for a long note is never revisited later. The Bach prelude starts with middle C, which sounds alone and goes to the right hand, and a beat later E5 enters above it: 16 semitones in one hand at a stretch of an octave. And this method never says NO, while in the second test three notes two octaves apart cannot be taken by two hands at all.
  • One arrow per condition. Without the second arrow ¬y → x the graph loses its symmetry, and the assignment from the order of components may break a rule.
  • The order of components mixed up. In Tarjan’s algorithm the numbers go in reverse topological order, in Kosaraju’s in forward order. The rule for choosing a literal depends on which traversal is used.
  • Unison. Two notes of the same pitch sounding together must not be treated as a “lower–upper” pair: the crossing condition would forbid one of the assignments, while by the statement unison has no rules. The fifteenth test has two such places arranged as mirror images: whichever of the two notes you treat as lower, one of them becomes a contradiction, and the answer comes out NO instead of YES.
  • Recursion. In the fourteenth test low and high notes alternate and each sounds together with the next: the implications line up in a chain of 20,000 literals. A recursive traversal in Python hits the depth limit.

Algorithms behind it

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 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
The algorithms catalogue