Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Answer connectivity in threshold order: The Limited Paths.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Offline Union Find queries matches the clues
- 2Keep this true after every move: before a query of limit L, Union Find contains exactly edges with weight less than L
- 3Reach the result within O((edges + queries) log(edges + queries))
Rules and pressure
- Target cost: O((edges + queries) log(edges + queries))
- State rule: before a query of limit L, Union Find contains exactly edges with weight less than L
Lesson 1 of 3
Live algorithm trace
Offline Union Find queries
Complete execution1 of 6
0-1:2
edge
1-2:4
0-2:8
q 0-2 <5
q 0-2 <4
query
Sort edges by weight and queries by increasing limit while retaining query indices.
1
sort edges by weight2
sort indexed queries by limit3
for each query in limit order4
union edges with weight < limit5
compare the query roots6
write answer at original index7
return answersedges = 2,4,8queryLimits = 4,5
Truth to preserve / Cost target
Truth to preserve
before a query of limit L, Union Find contains exactly edges with weight less than L
Cost target
O((edges + queries) log(edges + queries))
Sort weighted edges and queries by limit. Before answering one query, union every edge strictly lighter than its limit; the current components then represent exactly the paths that query is allowed to use.
Your call · What should guide every step of this algorithm?