Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 63 ยท Ad Hoc and Implementation

Simulation and Cycle Detection

Simulate a process for 10^18 steps without waiting: record visited states, detect the cycle, fast-forward with modular arithmetic and verify against direct simulation.

Many problems describe a process that repeats a rule: apply a function, shuffle a deck, move a token, update a board. Then the statement asks for the state after k steps, where k is 10^12 or even 10^18. Simulating one step at a time would take longer than the age of the universe. Yet the problem is solvable, because a process with a small number of possible states must eventually revisit one, and from that moment it repeats forever.

This lesson shows how to notice the repetition, measure it and jump ahead. The method is short, but it is easy to get off by one, so we verify every example against a direct simulation, the same discipline as in stress testing. For the data-structure view of the same idea, see cycle detection in DSA.

Why a cycle must appear

Suppose the next state depends only on the current state, and there are S possible states. Starting from any state x0, the sequence x0, x1, x2, ... can contain at most S different values. By the pigeonhole principle, within S + 1 steps some state appears twice. Because the rule is deterministic, everything after the second visit repeats everything after the first.

flowchart LR
  x0["x0"] --> x1["x1"] --> x2["x2"] --> x3["x3"]
  x3 --> x4["x4"] --> x5["x5"] --> x6["x6"]
  x6 --> x3

A path of length 3 (the "tail": x0, x1, x2) leading into a cycle of length 4 (x3 to x6).

The shape is always a tail of length mu followed by a cycle of length lam. With these two numbers, the state after k steps is:

  • if k < mu: simulate directly, it is short;
  • otherwise: the state at step mu + ((k - mu) mod lam).

Finding mu and lam with a dictionary

The simplest detector remembers the first step at which each state was seen. When a state repeats, the difference of the two step numbers is the cycle length and the earlier step is where the cycle starts.

Python Detect the cycle and jump to step k

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Starting at 4 and repeatedly replacing a number by the sum of the squares of its digits, the sequence is 4, 16, 37, 58, 89, 145, 42, 20, 4, .... It returns to 4 after 8 steps, so there is no tail (mu = 0) and the cycle length is 8. The state after 10^18 steps is found with a single remainder: 10^18 mod 8 = 0, which is the starting state again.

Two details are worth stating plainly:

  • The function returns mu and lam alongside the state so the example can display them; they are None when k is reached before any repeat. In real contest code you would return only the state.
  • The dictionary stores every state until the repeat. If a state is large (a whole grid), store a compact hashable key such as a tuple or a string, not the mutable object.

Simulating a whole structure

The state does not have to be a number. It can be a list, a grid or a whole configuration, as long as you can turn it into a hashable key and the next state depends only on the current one.

Problem: n people stand in a circle holding numbers. Every minute, each person simultaneously replaces their number with the sum of their own and their right neighbour's, modulo 10. What does the circle look like after 10^15 minutes?

Python A circle of numbers after a huge number of rounds

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each round is applied to the whole tuple at once, which matches the word "simultaneously" in the statement. The bounds also tell you the most work you will ever do: there are only 10^5 possible tuples of five digits, so the cycle is found after at most that many steps, no matter how large k is.

Floyd's algorithm: constant memory

If states are too big to store, or there are far too many of them to remember, Floyd's tortoise-and-hare algorithm finds a cycle using only two pointers. The tortoise moves one step at a time, the hare two. If there is a cycle they must meet inside it. Then:

  1. Reset the tortoise to the start; move both one step at a time. Where they meet again is the first state of the cycle, giving mu.
  2. From that state, move the hare around once, counting steps, to get lam.
Python Floyd's cycle detection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both methods agree. The dictionary approach is simpler and fast enough for almost every contest problem; reach for Floyd only when memory is a real constraint.

Fast-forwarding without a full cycle

Sometimes the state grows without bound, so no exact repeat exists, but the change per round repeats. For example, a counter that goes up by a pattern +1, +3, +2 every three rounds. Then compute the gain over one full pattern, multiply by the number of complete patterns and simulate the leftover steps directly. The principle is identical: find the repeating unit, skip whole repetitions, finish the remainder by hand.

Whenever k is astronomically large and each step is cheap, assume the intended solution involves a cycle, a closed formula or matrix exponentiation. Direct simulation is almost never the plan when k exceeds about 10^8.

Common mistakes

  • Off-by-one on the cycle start. first_seen[x] is the step index of the first visit. Check with k = 0, 1, 2, ... against a direct run, as in the examples.
  • Using time instead of state. If the rule depends on the step number (for example, "on even steps do A, on odd steps do B"), then the step parity belongs in the state key.
  • Mutable keys. Lists cannot be dictionary keys. Convert to tuple or str.
  • Forgetting that a cycle may not exist. If the state space is infinite, the sequence may never repeat. Use a loop limit as a safety net during development.
  • Mixing up k steps and k states. After k steps you are at x_k, so x_0 is the starting state.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why must a deterministic process on a finite set of S states repeat within S + 1 steps?

    With only S different states, among S + 1 consecutive states at least two are equal. After that the process repeats because the next state depends only on the current one.
  2. 2. A sequence has tail length mu = 5 and cycle length lam = 3. Which index holds the state after k = 100 steps?

    Skip the tail (5 steps), then take the remainder of the remaining 95 steps modulo the cycle length: 5 + 95 mod 3 = 7.
  3. 3. When is Floyd's tortoise-and-hare better than a dictionary of visited states?

    Floyd uses O(1) memory. A dictionary is simpler and fine whenever the number of states before the repeat fits in memory.
  4. 4. Each round of a game depends on the round number parity as well as on the board. What belongs in the state key?

    The next state must be a function of the key. If parity changes the rule, parity must be part of the key, otherwise two different situations look identical.

Summary

  • A deterministic process over finitely many states ends in a cycle after a tail.
  • Record the first step at which each state was seen; when one repeats you know mu and lam.
  • The state after k steps is at index mu + (k - mu) mod lam when k >= mu.
  • Make state keys hashable and include everything the next step depends on.
  • Floyd's algorithm finds the cycle in constant memory.
  • Always verify the shortcut against direct simulation for small k.

Next: Grid and Matrix Tricks