Problem 208: Robot Walks

Mathematical Development

Heading States

Each step changes the heading by $\pm 72^\circ$, so the heading can be represented by an element of $\mathbb{Z}/5\mathbb{Z}$:

• left turn: $d \mapsto d + 1 \pmod{5}$
• right turn: $d \mapsto d - 1 \pmod{5}$

The walk starts at heading $0$ and must end there as well.

Equal Use of the Five Headings

Let $v_d$ be the number of steps taken while the robot is in heading $d$. Writing the arc displacements in complex form and summing them shows that the total displacement is a fixed nonzero scalar multiple of

where $\omega = e^{2\pi i / 5}$.

The only rational linear relation among $1, \omega, \omega^2, \omega^3, \omega^4$ is

so zero displacement forces

Since the walk has 70 steps in total, each heading must therefore be used exactly

times.

Dynamic Programming State

Once the geometric condition has been reduced to equal heading counts, the remaining task is purely combinatorial. We use memoized dynamic programming on states

where $d$ is the current heading and $c_i$ is the number of remaining times heading $i$ may still be used.

If all $c_i$ are zero, the walk is valid exactly when the current heading is back to $0$.

Transitions

From a state with $c_d > 0$, we consume one use of heading $d$ and branch in the two possible directions:

• turn left and move to heading $(d+1) \bmod 5$
• turn right and move to heading $(d-1) \bmod 5$

Every closed walk corresponds to exactly one path through this state graph, and every path that exhausts the counts and returns to heading 0 is a valid closed walk.

Editorial

The geometry looks awkward until it is compressed into a counting constraint. A closed walk must use the five heading classes equally often, so for 70 steps each heading is used exactly 14 times. After that reduction, the shape of the path no longer needs separate coordinate tracking.

What remains is a finite state search. At any moment we only need to know the current heading and how many uses of each heading are still available. From that state there are at most two legal continuations, corresponding to the next left or right turn, so memoization counts the closed walks without revisiting the same subproblem.

Pseudocode

Define Solve(heading, c0, c1, c2, c3, c4):
    remaining = c0 + c1 + c2 + c3 + c4
    If remaining = 0:
        return 1 if heading = 0, otherwise 0

    If the state was computed before:
        return the cached value

    Let counts be [c0, c1, c2, c3, c4].
    If counts[heading] = 0:
        return 0

    Decrease counts[heading] by 1.

    total =
        Solve((heading + 1) mod 5, updated counts) +
        Solve((heading - 1) mod 5, updated counts)

    Cache total for the state and return it.

Return Solve(0, 14, 14, 14, 14, 14)

Complexity Analysis

• Time: $O(\text{number of reachable memoized states})$, with at most two transitions per state.
• Space: $O(\text{number of reachable memoized states})$ for the cache.

Answer

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

// State: (heading d, c0, c1, c2, c3) where ci = remaining visits for heading i
// c4 = remaining - c0 - c1 - c2 - c3 (but we track all 5)
// Each heading gets exactly 14 visits. Total steps = 70.

// We encode state as (d, c0, c1, c2, c3) since c4 = total_remaining - c0 - c1 - c2 - c3
// But it's easier to track all 5 counts.

// State: d * 15^4 + c0 * 15^3 + c1 * 15^2 + c2 * 15 + c3
// c4 is deduced from remaining steps = c0+c1+c2+c3+c4 and total = 70

// Actually let's use a map or a flat array.
// 5 * 15^4 = 253125 states (small enough for array)
// But we need c4 too. With c4 deducible: remaining = 70 - steps_taken
// c4 = remaining - c0 - c1 - c2 - c3... no, c0..c4 ARE the remaining counts.
// So c4 = (total remaining for heading 4).
// We don't know c4 from just c0..c3 unless we track steps taken.
// Actually: initially c0=c1=c2=c3=c4=14. As we take steps, ci decreases.
// c4 is independent of c0..c3. So we need all 5.
//
// State: (d, c0, c1, c2, c3, c4) -> 5 * 15^5 = 3,796,875 states. Still fine.
//
// Or we note that at each step from heading d, cd decreases by 1.
// So we need cd > 0 to take a step.

// Let's use memoization with a map for simplicity, or pack the state into an integer.
// Pack: d + 5*(c0 + 15*(c1 + 15*(c2 + 15*(c3 + 15*c4))))
// Max index: 5 * 15^5 = 3796875

long long dp[5 * 15 * 15 * 15 * 15 * 15]; // ~30 MB, feasible
bool visited[5 * 15 * 15 * 15 * 15 * 15];

inline int encode(int d, int c0, int c1, int c2, int c3, int c4) {
    return d + 5*(c0 + 15*(c1 + 15*(c2 + 15*(c3 + 15*c4))));
}

long long solve(int d, int c0, int c1, int c2, int c3, int c4) {
    int remaining = c0 + c1 + c2 + c3 + c4;
    if (remaining == 0) {
        return (d == 0) ? 1 : 0;
    }

    int idx = encode(d, c0, c1, c2, c3, c4);
    if (visited[idx]) return dp[idx];
    visited[idx] = true;

    int c[5] = {c0, c1, c2, c3, c4};
    long long result = 0;

    if (c[d] > 0) {
        c[d]--;
        // Left: heading becomes (d+1) % 5
        int nd = (d + 1) % 5;
        result += solve(nd, c[0], c[1], c[2], c[3], c[4]);
        // Right: heading becomes (d-1+5) % 5
        nd = (d + 4) % 5;
        result += solve(nd, c[0], c[1], c[2], c[3], c[4]);
        c[d]++;
    }

    dp[idx] = result;
    return result;
}

int main() {
    memset(visited, false, sizeof(visited));
    cout << solve(0, 14, 14, 14, 14, 14) << endl;
    return 0;
}

"""
Problem 208: Robot Walks

A robot takes 70 steps, each an arc of 1/5 of a circle (72 degrees).
At each step it turns left or right. Count distinct closed paths.

Key insight: for the path to close, each of the 5 heading directions must be
visited exactly 14 times (70/5 = 14). We use DP with state
(current_heading, remaining_visits_per_heading).
"""

from functools import lru_cache

@lru_cache(maxsize=None)
def solve(d, c0, c1, c2, c3, c4):
    """Count closed paths from state (heading d, remaining visits c0..c4)."""
    remaining = c0 + c1 + c2 + c3 + c4
    if remaining == 0:
        return 1 if d == 0 else 0

    c = [c0, c1, c2, c3, c4]
    if c[d] == 0:
        return 0  # can't move from this heading if no visits remain

    c[d] -= 1
    result = 0
    # Left turn: heading -> (d+1) % 5
    result += solve((d + 1) % 5, c[0], c[1], c[2], c[3], c[4])
    # Right turn: heading -> (d-1) % 5
    result += solve((d - 1) % 5, c[0], c[1], c[2], c[3], c[4])
    c[d] += 1  # restore (though with lru_cache args are immutable)

    return result

answer = solve(0, 14, 14, 14, 14, 14)
print(answer)