Simulation

Quick Revisit

• USE WHEN: Problem gives explicit step-by-step rules and N <= 10^6 allows direct simulation
• INVARIANT: Each step updates state exactly as described; trace samples by hand before coding
• TIME: O(N) per step or O(N*steps) total | SPACE: O(N) for state
• CLASSIC BUG: Mutating an array/state while iterating over it (use a copy or separate next-state array)
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

Read the rules. Implement them step by step. No clever algorithm—just do exactly what the problem says. Simulation is the bread and butter of Codeforces Div 2 A/B, and the technique most beginners underestimate.

Difficulty: [Beginner]Prerequisites: Arrays and Strings

---

Contents

• Intuition & Concept
• Visual Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading

---

Intuition & Concept

A simulation problem gives you a set of rules and asks: what happens when you apply them? There's no shortcut to find. You model the process in code and run it.

Consider a robot on a 1D number line starting at position 0. It receives commands: RRLLL. Each R moves right (+1), each L moves left (-1). Where does it end up?

Start: pos = 0
R  -> pos = 1
R  -> pos = 2
L  -> pos = 1
L  -> pos = 0
L  -> pos = -1

Answer: $-1$. No dynamic programming, no graph theory—just read each character, update state, report the result.

That's simulation in its purest form. The challenge isn't algorithmic—it's translational. Can you convert the English description into code without introducing bugs?

On Codeforces, simulation shows up as tags implementation and brute force, typically rated 800–1400. The problems test whether you can:

• Parse and follow multi-step rules without mistakes
• Handle edge cases in modular arithmetic and boundary conditions
• Recognize when brute simulation is fast enough vs. when you need to find a pattern

The trap at the ~1100 level: you understand the problem perfectly, you know exactly what to do, but your code has an off-by-one in the loop, or you mutate an array while iterating over it, or you miss that step counts can overflow int. Simulation bugs are logic bugs, and they're the hardest to spot under contest pressure.

The Real Difficulty

The problem is reading, not coding. A simulation that produces wrong output is almost always wrong because the state transition was misread from the problem statement—not because of a coding error. The fix is discipline: read the statement twice, highlight every rule, then trace the sample input by hand before writing a single line. Most contestants skip this and pay for it in debugging time.

  Workflow that catches 90% of simulation bugs:
  +-----------------------------------------------+
  |  1. Read statement                             |
  |  2. Read statement AGAIN (you missed something)|
  |  3. List every rule as bullet points           |
  |  4. Trace sample input by hand on paper        |
  |  5. Compare your trace to expected output       |
  |  6. NOW code it                                |
  +-----------------------------------------------+
       |
       v
  Most people jump from step 1 straight to step 6.
  That is why they get WA.

Look for mathematical shortcuts before simulating. Whenever a problem says "simulate N steps" where N reaches ${10}^9$ or ${10}^{18}$, the intended solution is never O(N) simulation. Look for: periodicity (the state repeats), a mathematical recurrence (you can compute step N from step N-1 with a formula), or an O(1) direct computation. The code for cycle detection is mechanical—the insight is recognizing when to apply it.

  Step count tells you the approach:
  +------------------+---------------------------+
  | N <= 10^6        | Simulate directly O(N)    |
  | N <= 10^9        | Find cycle or O(sqrt(N))  |
  | N <= 10^18       | Matrix exp / formula      |
  +------------------+---------------------------+

Simulation problems have high implementation difficulty relative to algorithmic difficulty. The algorithm is obvious: "just simulate." The real difficulty is implementing five to ten specific rules correctly, handling all edge cases, and never letting subtle state corruption slip in. Treat simulation like a translation exercise, not an algorithm design exercise.

When to Reach for Simulation

The signals are usually obvious once you know what to look for:

• The problem gives explicit step-by-step rules ("move the robot", "apply the operation", "repeat the process").
• It asks "what is the state after K steps?" or "simulate the process."
• N is small enough for direct execution—roughly $N\le {10}^5$, or $N\times \text{cost-per-step}$ fits in ~${10}^8$ operations.
• No obvious closed-form, formula, or mathematical shortcut jumps out.
• The state transitions are fully described in the problem statement—you just need to implement them faithfully.

If the step count is huge (${10}^9$+) but the state space is small, simulation is still the starting point—but you will need cycle detection on top of it (see Pattern 4).

---

With the core ideas in place, let's see what simulation looks like in action on a grid.

Visual Intuition

A robot starts at S on a 5x5 grid and follows commands RRDDL. Walls block movement (the robot stays in place if it would go out of bounds).

  Initial state           After RRDDL
  col 0 1 2 3 4           col 0 1 2 3 4
     +-+-+-+-+-+             +-+-+-+-+-+
  0  |S| | | | |          0  | | | | | |
     +-+-+-+-+-+             +-+-+-+-+-+
  1  | | | | | |          1  | | | | | |
     +-+-+-+-+-+             +-+-+-+-+-+
  2  | | | | | |          2  | |E| | | |
     +-+-+-+-+-+             +-+-+-+-+-+
  3  | | | | | |          3  | | | | | |
     +-+-+-+-+-+             +-+-+-+-+-+
  4  | | | | | |          4  | | | | | |
     +-+-+-+-+-+             +-+-+-+-+-+

  Trace:  (0,0) -R-> (0,1) -R-> (0,2) -D-> (1,2) -D-> (2,2) -L-> (2,1)
                                                                     ^
                                                                     E

Each step: check bounds, update (r, c). Nothing fancy.

For circular problems, modular arithmetic is the key. With $n=5$ people in a circle and every $k=2$nd person eliminated, starting at person 0:

  Round 1: Count 2 from person 0

    0---1             0---1             0---1
   /     \           /     \           /     \
  4       2   ->    4       X   ->    4       .
   \     /           \     /           \     /
    3---              3---              3---

  Eliminated: person 2       (i = (0 + 2 - 1) % 5 = 1... wait)

Actually, the standard Josephus indexing: start counting from the person after the last eliminated. Using 0-indexed positions in a list:

  People:  [0, 1, 2, 3, 4]    start index = 0

  Step 1:  idx = (0 + 2 - 1) % 5 = 1   -> eliminate person 1
           [0, 2, 3, 4]                  start index = 1

  Step 2:  idx = (1 + 2 - 1) % 4 = 2   -> eliminate person 3
           [0, 2, 4]                     start index = 2

  Step 3:  idx = (2 + 2 - 1) % 3 = 0   -> eliminate person 0
           [2, 4]                        start index = 0

  Step 4:  idx = (0 + 2 - 1) % 2 = 1   -> eliminate person 4
           [2]                           Winner: person 2

The core operation is idx = (idx + k - 1) % remaining_size. That % n is what makes circular problems tick.

Matrix rotation maps to a clean index formula:

  Original 3x3:         Rotated 90 CW:

  1  2  3               7  4  1
  4  5  6       ->      8  5  2
  7  8  9               9  6  3

  Rule: new[j][n-1-i] = old[i][j]

  Example: old[0][1] = 2  ->  new[1][2] = 2   (j=1, n-1-i = 2)
           old[2][0] = 7  ->  new[0][0] = 7   (j=0, n-1-i = 0)

Spiral traversal works by shrinking boundary pointers after each pass around the edge:

  Matrix:               Traversal order:

  1  2  3  4            1 --> 2 --> 3 --> 4
  5  6  7  8                              |
  9  10 11 12           5  6 --> 7    8   v
  13 14 15 16           ^         |   |
                        9   10<--11   v
  Output:               |            12
  1,2,3,4,8,12,16,      v            |
  15,14,13,9,5,         13<--14<--15<-+
  6,7,11,10             then 16

  Boundaries shrink after each full spiral:
  top=0, bottom=3, left=0, right=3
  -> top=1, bottom=2, left=1, right=2
  -> done

---

C++ STL Reference

These are the standard library tools you will reach for most often in simulation problems.

Function / Class	Header	What it does	Time Complexity
vector<int> v(n)	<vector>	Create array of $n$ zeros	$O(n)$
vector<vector<int>> g(r, vector<int>(c))	<vector>	Create $r\times c$ grid	$O(r\cdot c)$
queue<T> q	<queue>	FIFO queue for BFS-style simulation	Push/pop $O(1)$
priority_queue<T> pq	<queue>	Max-heap for event-driven simulation	Push/pop $O(\log n)$
deque<T> dq	<deque>	Double-ended queue, fast front/back ops	Push/pop $O(1)$
list<T> lst	<list>	Doubly-linked list for $O(1)$ erasure mid-sequence	Erase at iterator $O(1)$
rotate(b, mid, e)	<algorithm>	Left-rotate range so mid becomes first	$O(n)$
swap(a, b)	<utility>	Swap two values	$O(1)$
next_permutation(b, e)	<algorithm>	Advance to next permutation	$O(n)$
set<T> / multiset<T>	<set>	Ordered container for tracking active elements	Insert/erase $O(\log n)$

---

Implementation (Contest-Ready)

Grid Robot Simulation—Minimal Template

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    string cmd;
    cin >> cmd;

    // Direction vectors: U, D, L, R
    map<char,pair<int,int>> dir = {
        {'U',{-1,0}}, {'D',{1,0}}, {'L',{0,-1}}, {'R',{0,1}}
    };

    int r = 0, c = 0;
    for(char ch : cmd){
        int nr = r + dir[ch].first;
        int nc = c + dir[ch].second;
        if(nr >= 0 && nr < n && nc >= 0 && nc < m){
            r = nr; c = nc;
        }
    }
    cout << r << " " << c << "\n";
}

Grid Robot—Explained Version

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;       // grid dimensions: n rows, m columns
    cin >> n >> m;
    string cmd;     // movement commands
    cin >> cmd;

    // Map each command character to a (dr, dc) offset.
    // This avoids a chain of if-else statements.
    map<char,pair<int,int>> dir = {
        {'U',{-1,0}}, {'D',{1,0}}, {'L',{0,-1}}, {'R',{0,1}}
    };

    int r = 0, c = 0;  // starting position (top-left corner)
    for(char ch : cmd){
        int nr = r + dir[ch].first;
        int nc = c + dir[ch].second;
        // Only move if the new position is within bounds.
        // If the robot hits a wall, it stays in place.
        if(nr >= 0 && nr < n && nc >= 0 && nc < m){
            r = nr;
            c = nc;
        }
    }
    cout << r << " " << c << "\n";
}

Circular Elimination (Josephus Simulation)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> people(n);
    iota(people.begin(), people.end(), 0);  // [0, 1, ..., n-1]

    int idx = 0;
    while(people.size() > 1){
        idx = (idx + k - 1) % (int)people.size();
        people.erase(people.begin() + idx);
        if(idx == (int)people.size()) idx = 0;
    }
    cout << people[0] << "\n";
}

Matrix Rotation 90 Degrees Clockwise

#include <bits/stdc++.h>
using namespace std;

// Rotate an n x n matrix 90 degrees clockwise.
// new[j][n-1-i] = old[i][j]
vector<vector<int>> rotate90(vector<vector<int>>& mat){
    int n = mat.size();
    vector<vector<int>> res(n, vector<int>(n));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            res[j][n - 1 - i] = mat[i][j];
    return res;
}

int main(){
    int n;
    cin >> n;
    vector<vector<int>> mat(n, vector<int>(n));
    for(auto& row : mat)
        for(auto& x : row)
            cin >> x;

    auto rotated = rotate90(mat);
    for(auto& row : rotated){
        for(int j = 0; j < n; j++)
            cout << row[j] << " \n"[j + 1 == n];
    }
}

Spiral Order Traversal

#include <bits/stdc++.h>
using namespace std;

vector<int> spiralOrder(vector<vector<int>>& mat){
    vector<int> res;
    int top = 0, bot = mat.size() - 1;
    int lft = 0, rgt = mat[0].size() - 1;

    while(top <= bot && lft <= rgt){
        for(int c = lft; c <= rgt; c++) res.push_back(mat[top][c]);
        top++;
        for(int r = top; r <= bot; r++) res.push_back(mat[r][rgt]);
        rgt--;
        if(top <= bot){
            for(int c = rgt; c >= lft; c--) res.push_back(mat[bot][c]);
            bot--;
        }
        if(lft <= rgt){
            for(int r = bot; r >= top; r--) res.push_back(mat[r][lft]);
            lft++;
        }
    }
    return res;
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> mat(n, vector<int>(m));
    for(auto& row : mat)
        for(auto& x : row) cin >> x;

    auto ans = spiralOrder(mat);
    for(int i = 0; i < (int)ans.size(); i++)
        cout << ans[i] << " \n"[i + 1 == (int)ans.size()];
}

Process Simulation with Queue

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example: n people in a queue, each needs a[i] seconds of service.
    // Server processes one person at a time.
    // If a person's remaining time > time_slice, they go to the back.
    int n, time_slice;
    cin >> n >> time_slice;

    queue<pair<int,int>> q; // {id, remaining_time}
    for(int i = 0; i < n; i++){
        int t; cin >> t;
        q.push({i, t});
    }

    int clock = 0;
    while(!q.empty()){
        auto [id, rem] = q.front();
        q.pop();
        int work = min(rem, time_slice);
        clock += work;
        rem -= work;
        if(rem > 0){
            q.push({id, rem});
        } else {
            cout << "Person " << id << " done at time " << clock << "\n";
        }
    }
}

Step-by-step trace (n=3, time_slice=2, service times: [5, 3, 1]):

  Queue state at each step (front on left):

  Time=0   Queue: [(P0,5) (P1,3) (P2,1)]
           Process P0 for min(5,2)=2 units

  Time=2   Queue: [(P1,3) (P2,1) (P0,3)]     <-- P0 goes to back
           Process P1 for min(3,2)=2 units

  Time=4   Queue: [(P2,1) (P0,3) (P1,1)]     <-- P1 goes to back
           Process P2 for min(1,2)=1 unit

  Time=5   Queue: [(P0,3) (P1,1)]             <-- P2 DONE (rem=0)
           Process P0 for min(3,2)=2 units     Output: "Person 2 done at time 5"

  Time=7   Queue: [(P1,1) (P0,1)]             <-- P0 goes to back
           Process P1 for min(1,2)=1 unit

  Time=8   Queue: [(P0,1)]                    <-- P1 DONE (rem=0)
           Process P0 for min(1,2)=1 unit      Output: "Person 1 done at time 8"

  Time=9   Queue: []                           <-- P0 DONE (rem=0)
                                               Output: "Person 0 done at time 9"

---

Operations Reference

Here is a quick reference for how simulation costs scale with different problem structures.

Operation	Time	Space	Notes
Linear step simulation ($s$ steps, $O(1)$ per step)	$O(s)$	$O(1)$	Most common
Grid simulation ($r\times c$ grid, $s$ steps)	$O(s\cdot r\cdot c)$	$O(r\cdot c)$	Cellular automata
Circular elimination (Josephus brute force)	$O(n^2)$	$O(n)$	vector::erase is $O(n)$
Josephus formula (direct)	$O(n)$	$O(1)$	No simulation needed
Matrix rotation $n\times n$	$O(n^2)$	$O(n^2)$	New matrix or in-place
Spiral traversal $r\times c$	$O(r\cdot c)$	$O(r\cdot c)$	Output buffer
Queue/BFS process simulation	$O(n)$ per round	$O(n)$	Round-robin scheduling
Event-driven with priority queue	$O(e\log e)$	$O(e)$	$e$ = number of events
Cycle detection (Floyd's)	$O(\lambda +\mu )$	$O(1)$	$\lambda$ = cycle len, $\mu$ = tail

When to simulate vs. when to shortcut:

  STEP COUNT N        APPROACH              EXAMPLE
  +----------------+---------------------+-----------------------------+
  | N <= 10^6      | Simulate directly   | "Process N commands"        |
  |                | O(N) is fine        | Just loop and do it.        |
  +----------------+---------------------+-----------------------------+
  | N <= 10^9      | Too slow for O(N)   | "After N rounds..."         |
  |                | Find a CYCLE or     | Detect repeating state,     |
  |                | O(sqrt(N)) trick    | skip ahead with modulo.     |
  +----------------+---------------------+-----------------------------+
  | N <= 10^18     | Need O(log N)       | "Repeat 10^18 times"        |
  |                | Matrix exp or       | Build transition matrix,    |
  |                | closed-form formula | exponentiate in O(log N).   |
  +----------------+---------------------+-----------------------------+

  Rule of thumb: if N > 10^7 and each step is O(1),
  you CANNOT afford to simulate every step. Look for structure.

---

Problem Patterns & Tricks

Pattern 1: Direct State Tracking

The problem says "apply these operations in order." You maintain a state variable (position, score, count) and update it at each step. No data structure needed beyond a few variables.

Typical signals: "for each command", "after all operations", "process the string left to right."

int x = 0, y = 0;
for(char c : s){
    if(c == 'U') y++;
    else if(c == 'D') y--;
    else if(c == 'L') x--;
    else if(c == 'R') x++;
}

CF examples: CF 1560A, CF 1742A

Pattern 2: Grid Mutation with Double Buffering

In cellular-automata problems (Game of Life and its variants), every cell updates simultaneously based on its neighbors. That simultaneity is the catch: if you write the new value of (i,j) before reading all of (i,j)'s neighbors, you corrupt future reads. The fix is double buffering—read from cur, write to nxt, then swap.

auto nxt = cur;  // copy
for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++){
        int alive = countNeighbors(cur, i, j);
        if(cur[i][j] && (alive < 2 || alive > 3)) nxt[i][j] = 0;
        if(!cur[i][j] && alive == 3) nxt[i][j] = 1;
    }
swap(cur, nxt);

Without double buffering, updates "leak" forward through the grid—later cells see neighbors that were already overwritten, not their original values.

  WHY DOUBLE BUFFERING MATTERS (3x3 grid, rule: cell = 1 if any neighbor is 1)

  Initial grid:       WRONG (in-place):        RIGHT (double buffer):
  +---+---+---+       +---+---+---+            +---+---+---+
  | 1 | 0 | 0 |       | 1 | 1 | 0 |            | 1 | 1 | 0 |
  +---+---+---+  -->  +---+---+---+  BUT       +---+---+---+
  | 0 | 0 | 0 |       | 1 | 1*| 1*|  *WRONG!  | 1 | 1 | 0 |
  +---+---+---+       +---+---+---+            +---+---+---+
  | 0 | 0 | 0 |       | 1*| 1*| 1*|            | 0 | 0 | 0 |
  +---+---+---+       +---+---+---+            +---+---+---+

  In-place: when we process (1,0), cell (0,1) is already updated to 1,
  so (1,0) sees a neighbor=1 that did NOT exist in the original grid.
  The "1" leaks rightward and downward through the entire grid!

  Double buffer: we read from 'cur' and write to 'nxt'. Every cell
  sees only the ORIGINAL neighbors. Then swap(cur, nxt).

CF examples: CF 1700A, CF 1840B

Pattern 3: Modular / Circular Indexing

Any time objects wrap around—rotating arrays, circular queues, clock arithmetic—use % n. The key formula is next = (cur + step) % n.

Watch out: in C++, (-1) % 5 gives -1, not 4. Always use ((cur - step) % n + n) % n for backward steps.

// Rotate array left by k positions
rotate(a.begin(), a.begin() + k % n, a.end());

// Manual circular access
int pos = (start + offset) % n;

// Safe backward modular step
int prev = ((cur - 1) % n + n) % n;

CF examples: CF 1579A, CF 1700B

Pattern 4: Simulation with Cycle Detection

When the problem says "repeat ${10}^9$ times" but each step is $O(n)$, brute simulation will TLE. The trick: states are finite, so the process must eventually cycle. Detect the cycle, then skip ahead.

map<State, int> seen;  // state -> step number
int step = 0;
while(step < total_steps){
    State s = getCurrentState();
    if(seen.count(s)){
        int cycle_len = step - seen[s];
        int remaining = (total_steps - step) % cycle_len;
        for(int i = 0; i < remaining; i++) doStep();
        break;
    }
    seen[s] = step;
    doStep();
    step++;
}

This reduces $O(T\cdot n)$ to $O(C\cdot n)$, where $C$ is the cycle length—typically much smaller than $T$.

Worked example: cycle_start != 0, find state at step 10^9

A state machine has transition f(x) = (x*3 + 1) % 7, starting at x=2. We want the state at step N = 1,000,000,000.

  Trace states and record when each was first seen:

  Step:   0   1   2   3   4   5   6   7   8  ...
  State:  2   0   1   4   6   5   2   0   1  ...
                                    ^
                                    |
  Step 6: state=2, but we saw state=2 at step 0!

  +---+---+---+---+---+---+---+---+---+
  | 2 | 0 | 1 | 4 | 6 | 5 | 2 | 0 | 1 | ...
  +---+---+---+---+---+---+---+---+---+
  |<--- tail (mu=0) --->|<- cycle (lambda=6) ->|

  cycle_start = 0  (step where the repeated state was first seen)
  cycle_len   = 6  (step 6 - step 0 = 6)

  To find state at step N = 1,000,000,000:
    N >= cycle_start, so we are in the cycle.
    offset = (N - cycle_start) % cycle_len
           = (1000000000 - 0) % 6
           = 1000000000 % 6
           = 4
    Answer = state at step (cycle_start + offset)
           = state at step 4
           = 6

  Another example with cycle_start != 0:
  Suppose the trace is: 9 -> 3 -> 7 -> 5 -> 2 -> 8 -> 5 -> 2 -> 8 -> ...

  Step:   0   1   2   3   4   5   6   7   8
  State:  9   3   7   5   2   8   5   2   8
                      ^           ^
                      |           |
  Step 5: state=5, but state=5 was first seen at step 3!

  |<-- tail (mu=3) -->|<-- cycle (lambda=2) -->|

  cycle_start = 3, cycle_len = 2

  For N = 10^9:
    N >= 3, so we are in the cycle.
    offset = (10^9 - 3) % 2 = 1
    Answer = state at step (3 + 1) = state at step 4 = 2

CF examples: CF 1560B, CF 1352C

Pattern 5: Matrix Transformations

Rotation, transposition, and reflection come up in grid problems. Memorize these mappings for an $n\times n$ matrix:

Transform	Formula
Rotate 90 deg CW	new[j][n-1-i] = old[i][j]
Rotate 90 deg CCW	new[n-1-j][i] = old[i][j]
Rotate 180 deg	new[n-1-i][n-1-j] = old[i][j]
Transpose	new[j][i] = old[i][j]
Reflect horizontal	new[i][n-1-j] = old[i][j]
Reflect vertical	new[n-1-i][j] = old[i][j]

In practice, the 90° CW case reduces to: transpose, then reverse each row. Easier to remember and easier to code than the index formula:

// In-place rotate 90 CW for n x n matrix
for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++)
        swap(mat[i][j], mat[j][i]);   // transpose
for(int i = 0; i < n; i++)
    reverse(mat[i].begin(), mat[i].end()); // reverse rows

CF examples: CF 1772C, CF 1506C

Pattern 6: Event-Driven Simulation with Priority Queue

Instead of simulating every time unit, jump directly to the next event. Store events in a priority queue ordered by time.

// pq stores {time, event_type, ...} — min-heap by time
priority_queue<Event, vector<Event>, greater<>> pq;
pq.push({0, START, ...});

while(!pq.empty()){
    auto [t, type, data] = pq.top();
    pq.pop();
    // process event, possibly push new events
    if(type == ARRIVE) pq.push({t + service_time, DEPART, ...});
}

This matters when the time range is huge (${10}^9$) but events are sparse (${10}^5$). Simulating each tick would TLE; jumping between events is $O(e\log e)$.

CF examples: CF 1353C, CF 1399C

Pattern 7: "Last One Standing" Simulation

Problems where you repeatedly remove elements from a collection until one remains (or until some condition). Use a queue, deque, or set depending on the removal pattern.

// Example: repeatedly remove the smallest, apply some rule
priority_queue<int, vector<int>, greater<>> pq(a.begin(), a.end());
while(pq.size() > 1){
    int x = pq.top(); pq.pop();
    int y = pq.top(); pq.pop();
    if(x != y) pq.push(abs(x - y));
}
cout << (pq.empty() ? 0 : pq.top()) << "\n";

CF examples: CF 1154C, CF 1490D

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|                    SIMULATION CHEAT SHEET                         |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|  - Problem says "apply rules step by step"                       |
|  - Tags: implementation, brute force, *1100-1400                 |
|  - Constraints allow O(n) or O(n^2) brute simulation             |
|                                                                  |
| KEY PATTERNS:                                                    |
|  - Grid move:  nr = r + dr[d]; nc = c + dc[d]; check bounds     |
|  - Circular:   idx = (idx + k) % n                               |
|  - Safe mod:   ((x % n) + n) % n     (handles negatives)        |
|  - Rotate CW:  transpose + reverse rows                          |
|  - Cycle skip: detect repeated state, jump by remaining % cycle  |
|                                                                  |
| WATCH FOR:                                                       |
|  - Mutating grid while reading neighbors -> double buffer        |
|  - (-1) % n is NEGATIVE in C++ -> add n before mod              |
|  - int overflow when step count > 2*10^9 -> use long long        |
|  - "Repeat 10^9 times" -> find cycle, don't brute force          |
|                                                                  |
| COMPLEXITY:                                                      |
|  - Linear sim:  O(steps)          Space: O(state_size)           |
|  - Grid sim:    O(steps * r * c)  Space: O(r * c)                |
|  - Event-driven: O(e log e)       Space: O(e)                    |
+------------------------------------------------------------------+

---

Gotchas & Debugging

Common Mistakes

Mutating while iterating. This is the #1 simulation bug. When you update grid[i][j] based on its neighbors and some of those neighbors were already updated earlier in the same pass, your answer is wrong—you're reading "future" state as if it were the original. Always use a copy (double buffering) when the next state of any cell depends on the current state of multiple cells.

Off-by-one in modular arithmetic. Josephus-style problems are notorious for this. Is the count 0-indexed or 1-indexed? Does k mean "skip k people" or "eliminate the k-th person"? Work through a tiny example by hand ($n=3$, $k=2$) before touching the keyboard.

Negative modular results. (-3) % 5 is -3 in C++, not 2. Whenever you subtract in a circular index, use ((x % n) + n) % n. This trips up so many contestants that it should be muscle memory for any modular arithmetic where the value might go negative.

Integer overflow in step counting. If the problem says "after ${10}^{18}$ steps," your step counter needs long long. Even intermediate products like step * n overflow silently if both variables are int. Use 1LL * step * n or declare all step-related variables as long long from the start.

Infinite loops from missed termination. "Repeat until no changes occur"—if your update rule can oscillate between two states, you'll loop forever. Add a safety check (if(step > MAX_REASONABLE) break;) during debugging. Better yet, reason about whether the process is guaranteed to terminate before you code it.

Wrong direction vectors. In grid problems, confusing row/column with x/y coordinates is a classic mistake. Convention: (r, c) where r increases downward, c increases rightward. So "up" is (-1, 0), not (0, 1).

  Direction map (row, col):

       (-1,0)
         ^
         |
  (0,-1) <--+--> (0,+1)
         |
         v
       (+1,0)

Reading input in the wrong order. Grid problems sometimes give dimensions as "n rows, m columns" and sometimes as "width, height"—and the sample input rarely makes the difference obvious until you're debugging. Read the problem statement twice and verify your input parsing against the sample before writing any logic.

Not resetting state between test cases. Multi-test-case problems (t test cases)—make sure you clear and reinitialize all data structures at the start of each test case. Global arrays that work correctly for test case 1 may still contain stale data from it when test case 2 runs.

Mental Traps

Trap 1: "Simulation is always brute force."

Naive simulation is brute force, but simulation problems often hide structure—periodicity, invariants, or mathematical shortcuts—that admits an $O(\log n)$ or $O(1)$ solution. "Simulate ${10}^{18}$ steps" is never solved by raw simulation.

  WRONG THINKING:                     RIGHT THINKING:
  +----------------------------+      +----------------------------+
  | "Simulate N steps"         |      | "Simulate N steps"         |
  |  N = 10^18                 |      |  N = 10^18                 |
  |  -> for i in 1..N: step() |      |  -> N is HUGE, can't loop  |
  |  -> TLE (obviously)        |      |  -> Look for CYCLE or      |
  |                            |      |     FORMULA or MATRIX EXP  |
  |  You tried brute force     |      |  -> Simulate until repeat, |
  |  and blamed the problem.   |      |     then skip ahead.       |
  +----------------------------+      +----------------------------+

Trap 2: "I understand the problem, so coding it is just transcription."

Natural language is ambiguous; code is not. Boundary conditions, tie-breaking rules, and off-by-one errors lurk in every sentence of the problem statement. The translation from English to C++ is where simulation problems are won and lost.

  WRONG THINKING:                     RIGHT THINKING:
  +----------------------------+      +----------------------------+
  | "I get it, let me code"    |      | "I get it, let me VERIFY"  |
  |  -> Skip re-reading        |      |  -> Read statement twice   |
  |  -> Code from memory       |      |  -> Trace sample by hand   |
  |  -> WA on test 3           |      |  -> Check EVERY edge:      |
  |  -> Debug for 30 minutes   |      |     * boundary at 0 and n  |
  |  -> Find a misread rule    |      |     * tie-breaking order    |
  |                            |      |     * off-by-one in loop    |
  +----------------------------+      +----------------------------+

Trap 3: "If it gives the right output on the sample, it's correct."

Simulation bugs often manifest only on specific state sequences—edge cases that never appear in sample inputs. The sample is a sanity check, not a proof. Always stress test.

  WRONG THINKING:                     RIGHT THINKING:
  +----------------------------+      +----------------------------+
  | Sample: 3 test cases       |      | Sample passes? Good start. |
  |  -> All pass!              |      |  -> Now test:              |
  |  -> Submit immediately     |      |     * N = 1 (minimum)      |
  |  -> WA on test 47          |      |     * N = max (overflow?)  |
  |  -> ??? what went wrong    |      |     * Random stress test    |
  |                            |      |     * Adversarial inputs    |
  +----------------------------+      +----------------------------+

---

Self-Test

Before moving on, verify you can do each of these without looking anything up:

• [ ] Describe the "read the problem statement twice and walk through the sample by hand" workflow for simulation—explain why each step matters for catching misread rules, boundary errors, and off-by-one bugs.
• [ ] Given a simulation that cycles, write the code to find the cycle length and compute the answer at step N (for large N) in O(cycle_length) total steps.
• [ ] State what "off-by-one in the termination condition" looks like in a simulation and how to catch it (e.g., < vs <=, 0-indexed vs 1-indexed loop bounds).
• [ ] Name three signal phrases in a problem statement that suggest the naive simulation would TLE and a mathematical shortcut exists (e.g., "repeat 10^9 times", "after K operations where K up to 10^18", "find the state after T seconds").
• [ ] Explain why simulation problems with high step counts (N = 10^9+) almost always use periodicity, matrix exponentiation, or closed-form formulas rather than step-by-step simulation.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Watermelon	CF 4A	800	Simplest simulation—check one condition
2	Elephant	CF 617A	800	Direct step counting with division
3	Robot Return to Origin	CF 1560A	800	Track (x, y) through command string
4	Make It Equal	CF 1352C	1200	Counting simulation with pattern
5	Card Game	CF 1490D	1100	Queue-based elimination simulation
6	Rotate Columns	CF 1209E1	1400	Matrix column rotation + brute force
7	Josephus Problem	CSES	1300	Classic circular elimination
8	Spiral Matrix	LeetCode 54	1300	Boundary-shrinking spiral traversal
9	Robot Simulation	CF 1154C	1300	Grid robot with obstacle handling
10	Game of Life	LeetCode 289	1400	Cellular automata with in-place trick

---

The core insight: the problem is the algorithm. Simulation asks nothing more than faithful translation—rules to code, step by step, without a single misread. The difficulty is precision, not ingenuity. Whenever you see "do exactly as described" and $N\le {10}^6$, reach for simulation first and think about shortcuts second.

Further Reading

• Competitive Programmer's Handbook—Ch 6: Simulation—Antti Laaksonen's treatment of brute force and simulation
• CP-Algorithms: Josephus Problem—$O(n)$ and $O(k\log n)$ closed-form solutions
• Codeforces Blog: Implementation Tips—avoiding common implementation bugs
• For deeper matrix operations, see: 09-matrix-exponentiation.md (when simulation steps are too many, exponentiate the transition matrix)
• For cycle detection in sequences, see: Floyd's Tortoise and Hare algorithm in any standard algorithms textbook

---

Rating Progression

• CF 1200: Straightforward step-by-step: track a robot, process a queue, apply rules in order.
• CF 1500: Detect cycles or periodic states to skip billions of steps; simulate-then-shortcut hybrid.
• CF 1800: Matrix exponentiation to handle ${10}^{18}$ simulation steps; state compression for large state spaces.
• CF 2100: Simulate complex game mechanics with interleaved greedy/DP decisions; reduce simulation dimension via invariants.

Before You Code Checklist

• [ ] Confirmed the number of simulation steps fits within time limits (or identified a shortcut for large step counts).
• [ ] Identified all state variables and initialized them correctly (position, direction, counters, flags).
• [ ] Checked for mutation-during-iteration bugs—do I need a snapshot of the previous state?
• [ ] Verified loop bounds for off-by-one: does the problem use 0-indexed or 1-indexed? Is the range inclusive or exclusive?
• [ ] Tested edge cases: zero steps, single element, wraparound/modular behavior, and maximum input size.

What Would You Do If...?

1. The problem says "simulate ${10}^{18}$ operations" but the state space has only $n\le {10}^5$ possible states—how would you detect and exploit the cycle?
2. You need to simulate a 2D grid where every cell updates simultaneously based on its neighbors—how do you avoid reading already-updated cells?
3. Your simulation passes sample cases but TLEs on large inputs—what's the first thing you check about the step count and inner loop complexity?

The Mistake That Teaches

A contestant simulated a circular card game by erasing elements from a vector during iteration. On small tests it worked. On $n={10}^5$ it TLEd because each erase was $O(n)$, making the total $O(n^2)$. The fix: use a deque or linked list for $O(1)$ removal, or simulate indices with modular arithmetic on a boolean alive[] array. The lesson—choosing the right data structure is part of the simulation.

Debug This

Bug 1:

// Simulate robot moving on a grid, 'R','L','U','D'
int x = 0, y = 0;
for (char c : commands) {
    if (c == 'R') x++;
    if (c == 'L') x--;
    if (c == 'U') x++;  // Bug here
    if (c == 'D') y--;
}

Answer

'U' should modify y++, not x++. Copy-paste error—one of the most common simulation bugs.

Bug 2:

// Simulate n rounds, 1-indexed
vector<int> a(n);
for (int i = 1; i < n; i++) {
    a[i] = a[i-1] + delta[i];
}
cout << a[n] << "\n";

Answer

a[n] is out of bounds for a vector of size n (valid indices are 0 to n-1). Either use a[n-1] or allocate vector<int> a(n+1).

Bug 3:

// Simulate until state repeats, step count up to 1e9
map<vector<int>, int> seen;
vector<int> state = initial;
for (int step = 0; step < 1000000000; step++) {
    if (seen.count(state)) break;
    seen[state] = step;
    state = next_state(state);
}
// Uses 'step' here but 'step' is out of scope after for-loop

Answer

The variable step is scoped to the for-loop and cannot be used after it. Declare int step before the loop. Also, even with the cycle detected, the code doesn't use the cycle length to compute the answer at step ${10}^9$—it just breaks out.

Simulation as a computational technique dates to the Monte Carlo methods Stanislaw Ulam and John von Neumann developed at Los Alamos in the 1940s. In competitive programming it has appeared since the earliest IOI contests of the late 1980s, always testing implementation discipline over algorithmic ingenuity. The mnemonic holds: "Read the rules, run the rules, trust the rules."

Related Techniques

• How to Solve Problems—the "read, trace, code" discipline is most critical for simulation
• Sorting and Searching—sorted order often simplifies simulation state management
• Two Pointers—when simulation reduces to scanning from both ends or tracking a window
• Constructive Algorithms—simulation validates constructive solutions by replaying the construction step by step
• Debugging and Stress Testing—brute-force simulation is the gold-standard reference for stress testing
• Data Structure Selection Guide—choosing the right container for your simulation state

What to Solve Next

Work through the practice ladder at Ladder 1100–1400 for graded simulation and implementation problems. Then move to Sorting and Searching for problems where simulation alone is too slow and you need to preprocess the input. For worked examples with full explanations, see the Worked Solutions collection.