Merge Triplets to Form Target Triplet
Drop the overshooters, OR the exact hits of the rest
A merge takes the elementwise maximum, so every value it touches either stays put or climbs — nothing ever comes back down. That one-way property decides the whole problem. Any triplet holding a value larger than the target in some slot is poison: merge it even once and that slot is permanently too big, so it can be deleted from consideration entirely. Every remaining triplet is safe to merge, because none of its values can push a slot past the target. Merging all of the safe ones together is therefore never worse than merging some of them, and the result in each slot is simply the largest safe value there. So the answer is yes exactly when each of the three slots is matched exactly by at least one safe triplet — a single pass, no choices, no backtracking.
Details
Animated on: triplets = (2,5,3),(5,8,1),(1,6,4),(9,1,1),(5,2,7),(3,6,7),(4,6,8), target = (5,6,7) — repeatedly replace a triplet with the elementwise max of two triplets; can (5,6,7) be produced?
Problem:Merge Triplets to Form Target TripletMedium
Drop the overshooters, OR the exact hits of the rest
step 1 / 9
Target is (5,6,7). A merge replaces a triplet with the elementwise MAX of two, so a value can only ever climb — one slot that already sits above the target can never be brought back down. That splits the work in two: throw away every triplet that overshoots anywhere, then ask whether the survivors between them hit (5,6,7) exactly in all three slots. Covered so far: nothing yet.
1FUNCTION mergeTriplets(triplets, target)2 found <- [FALSE, FALSE, FALSE]3 FOR i <- 0 TO LENGTH(triplets) - 14 IF triplets[i][0] > target[0] OR triplets[i][1] > target[1] OR triplets[i][2] > target[2]5 CONTINUE6 FOR k <- 0 TO 27 IF triplets[i][k] = target[k]8 found[k] <- TRUE9 RETURN found[0] AND found[1] AND found[2]
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- Target is (5,6,7). A merge replaces a triplet with the elementwise MAX of two, so a value can only ever climb — one slot that already sits above the target can never be brought back down. That splits the work in two: throw away every triplet that overshoots anywhere, then ask whether the survivors between them hit (5,6,7) exactly in all three slots. Covered so far: nothing yet.
- (2,5,3) is safe to merge — it never exceeds (5,6,7) — but none of 2, 5, 3 reaches the matching target value, so it can lift a slot part-way and no further. Harmless and useless at the same time, which is why the scan needs no backtracking. Covered stays nothing yet.
- (5,8,1) overshoots the target: 8 in the second slot against 6. Merging it into anything drags that slot above the target permanently, so it is dropped outright rather than weighed against the others. Covered stays nothing yet.
- (1,6,4) sits at or below (5,6,7) in every slot, so it is safe to merge, and it matches the target exactly in the second slot. Merging can only raise a slot that is still short, so that position is now settled for good. Covered: second.
- (9,1,1) overshoots the target: 9 in the first slot against 5. Merging it into anything drags that slot above the target permanently, so it is dropped outright rather than weighed against the others. Covered stays second.
- (5,2,7) sits at or below (5,6,7) in every slot, so it is safe to merge, and it matches the target exactly in the first and third slots. Merging can only raise a slot that is still short, so those positions are now settled for good. Covered: first + second + third.
- (3,6,7) is safe to merge — it never exceeds (5,6,7) — but its exact hits are the second and third slots, already covered by an earlier triplet. Harmless and useless at the same time, which is why the scan needs no backtracking. Covered stays first + second + third.
- (4,6,8) overshoots the target: 8 in the third slot against 7. Merging it into anything drags that slot above the target permanently, so it is dropped outright rather than weighed against the others. Covered stays first + second + third.
- All 7 triplets are classified. Every slot of (5,6,7) was hit exactly by some safe triplet (first + second + third), so merging just those together produces (5,6,7) — answer true. Notice no triplet ever had to be reconsidered: an overshooting one is useless forever, and a safe one can never do harm.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.