When to Use Reverse Simulation: A Mental Checklist

Reverse simulation is a powerful technique in competitive programming. Use it when most of the following conditions hold:

1. Fixed Start, Specific Target
- You know the starting state exactly.
- You’re given a specific target state.
- You need the shortest sequence of operations from start → target.
- But: Forward search is infeasible due to a huge or exponential state space.

2. Operations Are Reversible
- Each forward operation has a clear, deterministic inverse.
- The reverse step can be computed without ambiguity or guessing.
- Common in problems involving:
— Halving / doubling
— Adding / subtracting fixed values
— Bit shifts
— Modular arithmetic with invertible operations

3. Forward Has Branching, Reverse Has No Branching
- Forward direction: Multiple valid moves → exponential paths (e.g., BFS/DFS needed).
- Reverse direction: Exactly one valid predecessor at each step → linear path.
This is the biggest red flag that reverse simulation is the right approach!

4. Constraints Suggest a Small Number of Steps
- The problem guarantees the answer is small (e.g., “≤ 120 steps”).
- Even if values are huge (e.g., k = 60 → numbers up to 2⁶⁰), the number of operations is logarithmic.
- This often indicates bit-level or divide-and-conquer structure, which reverse simulation handles naturally.

5. State Is Compact (1–2 Variables)
- The entire system state can be represented with one or two integers.
- Example: total quantity is conserved → track only one participant’s value.
- Makes reverse computation simple and efficient.

Pro Tip: The Key Question

“If I’m at the target state, can I uniquely determine where I came from?”

• If yes, and the predecessor is easy to compute,
• Then reverse simulation is likely the intended solution.

Remember: Reverse simulation turns an intractable forward search into a deterministic, linear walk backward — then just reverse the operation list to get the answer!