AtCoder Heuristic Contest 073
Circles of Inversion Editorial
Basic properties
- There are always 3 magic circles
→ think of it as "the used circle moves to the departure point" - A teleport moves you by 2d, where d = C − P
→ the parity of each coordinate never changes- Only walking can change the parity
- Walking only takes moves per leg on average
- A leg is the trip from one destination to the next
- 151 points per case ( points over 150 cases)
The first idea: forward greedy
- Visit the destinations one by one in order
- For each leg, pick the cheapest of 4 options
- Walk only
- Teleport with one of the circles, then walk (3 options)
- Result: moves per leg (walking only: )
- No teleport at all in % of the legs
points
Forward greedy 2: walk, then teleport exactly
- For each circle C, walk to X = 2C − G, from which a teleport lands exactly on the destination G
- Pick the cheapest of the 4 options, including walking only
- The cost is |2C − P − G| + 1, the same as the forward greedy. Only the used circle's new position differs (X instead of P)
- Result: moves per leg, no teleport in % of the legs
points
Why the forward direction fails
- Magic circles pile up at the edges
- A used circle moves to the departure point, and departure points (P or X) are spread over the whole board
- A teleport lands on the opposite side of the circle
→ using a circle near the edge almost always leaves the board - A circle left near the edge can never be used again and stays there
- Circles within 8 cells of an edge: forward greedy %, forward greedy 2 % (23% if uniform)
- As a result, at the start of a leg only of the 3 circles on average can land on the board (forward greedy)
Think in reverse
- Build the operation sequence from the end. Rewinding time turns a teleport into this operation:
- Takahashi warps onto a magic circle's cell, and the circle moves to the midpoint between that cell and his departure point (if the parities differ, first take 1–2 steps to match them)
Solve it as a reverse problem
Forward
3 magic circlesfree choice
→
Initial position
→
Destination 0
→
…
→
Destination 149
Reverse
3 magic circlesfree choice
→
Destination 149
→
…
→
Destination 0
→
Initial positionoutput the circles here
- In reverse, start from the last destination with the circles anywhere you like
- The final circle positions of the forward process can be anything
- Back at the initial position, output the current circles as the initial placement, followed by the operations in reverse order
- Walks flip direction (U ↔ D, L ↔ R), and a warp becomes the teleport
J midpoint
- Walks flip direction (U ↔ D, L ↔ R), and a warp becomes the teleport
- The set of possible solutions is the same. The only difference is the direction in which you search
Reverse greedy
- Do exactly what the forward greedy does, but in reverse
- Visit the destinations one by one in reverse order
- For each leg, pick the cheapest of "walk only" and "warp onto one of the circles, then walk"
- Initial circles in reverse: on the next 3 destinations in reverse order
- Result: moves per leg
About times the score of the forward greedy
Right: legs 26–29 of seed=0, traced backward from the end. The blue ring marks the next destination; dotted purple lines show circles moving
points
In reverse, circles become "warp targets"
- In reverse, a teleport lands on the circle's cell itself
- From anywhere, one move reaches any of the 3 circles (+ 0–2 steps for parity)
- It never leaves the board
- In the forward direction, a teleport lands on the opposite side of the circle
- The landing depends on where you are, and a farther circle throws you farther
- It easily leaves the board
Right: landing cells of up to 3 consecutive teleports from the same configuration (● Takahashi, purple rings: magic circles)
Comparison on random configurations
- Place Takahashi, 3 circles, and a destination uniformly at random, and average the best number of moves for the leg over 20,000 trials
- Forward: on average only of the 3 teleports land on the board, and they land at random places, so walking barely decreases
- Reverse: all 3 are usable. Warping to the circle nearest to the destination roughly halves the walking
Used circles go to different places
Circle positions at the start of each leg from the 11th leg on, over the 150 contest cases
- Forward: moves to the departure point
- Circles pile up at the edges and become useless
- Reverse: moves to the midpoint
- The more they are used, the more they gather in the center
- A circle near the center is a warp target fairly close to any destination
Improving the reverse greedy
- Chain up to 3 warps before walking
- Try all 1 + 3 + 9 + 27 = 40 options
- Take 0–2 steps for parity before each warp
- Selection: moves in this leg + estimated moves for the next 12 destinations
- Estimate: for each destination, the cheaper of "walk only" and "warp to the best circle, then walk"
- Circle moves are tracked, and each later destination is weighted by another factor of 0.8
points
| Reverse greedy | Score | Moves per leg |
|---|---|---|
| ≤ 1 warp (previous chapter) | ||
| ≤ 3 warps | ||
| ≤ 3 warps + lookahead |
The improved solution, seen forward
- Walk toward the center, then teleport to near the destination
- Teleports depart cells from the edge on average
(destinations: 20.8 cells on average)
- Teleports depart cells from the edge on average
- After landing, 1–2 steps for parity
- Legs 26–29: moves by walking only → moves
- (W: walking steps, J: teleport)
- , ,
Forward vs. reverse
Improved forward greedy / forward beam search: the same search and evaluation as the reverse ones, run forward
- The same method scores 3–10 times higher just by reversing the direction
- Reversing the direction helps far more than a stronger search
- Seen forward, the reverse greedy's solution has the same "walk, then teleport" shape as forward greedy 2. The difference is whether a circle is there
- The forward beam search avoids piling circles at the edges (% within 8 cells), but still takes moves per leg, about the same as random configurations
Writer's solution: reverse beam search
- State: the current reverse position (the previous destination) and the positions of the 3 circles
- Transitions: the same 40 options as the improved reverse greedy
- Evaluation: moves so far + estimated moves for the next 8 destinations
- Beam width 2,500
- Deduplication: among states whose circle coordinates coincide after halving, keep only the best
- Initial states: evaluate all 4,060 ways to choose 3 of the first 30 destinations in reverse order, and start from the best ones
points
Time: average when running 12 cases in parallel on a local machine
Without deduplication: points at width 2,500 ( s)
Improved reverse greedy vs. writer's solution
seed=0, legs 26–29 ( moves by walking only)
Summary
- Thinking in reverse turns the magic circles into "warp targets" that gather in the center as they are used
- Even the simple greedy halves the number of moves just by running in reverse