Problem 992: Another Frog Jumping

Project Euler Problem 992 Solution

EulerSolve provides an optimized solution for Project Euler Problem 992, Another Frog Jumping, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The provided C++ solution encodes the following walk-counting problem on a path graph. Consider the vertices $0,1,\dots,n$ in a line. The walk starts at vertex $0$, each move changes the position by exactly $1$, and the boundary condition is $0 \le x \le n$. The last vertex $n$ is auxiliary: it may be visited arbitrarily often and is not tracked. For every tracked vertex $0 \le i \lt n$, the walk must visit $i$ exactly $k+i$ times. Let $W(n,k)$ denote the number of valid walks that satisfy all those visit constraints and end at any endpoint $e \in \{0,1,\dots,n\}$. The program computes $$\Bigl(W(500,1)+W(500,10)+W(500,100)+W(500,1000)+W(500,10000)\Bigr)\bmod 987898789.$$ The checkpoints hard-coded in the file are $$W(3,2)=17,\qquad W(6,1)=1320,\qquad W(6,5)=16793280.$$ Mathematical Approach 1. Fix the Endpoint and Count Edge Crossings For a fixed endpoint $e$, define for each edge $i$ between $i-1$ and $i$ ($1 \le i \le n$): $$R_i=\#\{\text{crossings } i-1 \to i\},\qquad L_i=\#\{\text{crossings } i \to i-1\}.$$ Because the walk starts to the left of every edge, the net balance across edge $i$ is determined by whether the endpoint lies to the right of that edge: $$R_i-L_i=\mathbf{1}_{e \ge i}.$$ This is the key observation: once the endpoint is fixed, the imbalance on every edge is fixed as well. 2....

Detailed mathematical approach

Problem Summary

The provided C++ solution encodes the following walk-counting problem on a path graph. Consider the vertices $0,1,\dots,n$ in a line. The walk starts at vertex $0$, each move changes the position by exactly $1$, and the boundary condition is $0 \le x \le n$. The last vertex $n$ is auxiliary: it may be visited arbitrarily often and is not tracked. For every tracked vertex $0 \le i \lt n$, the walk must visit $i$ exactly $k+i$ times.

Let $W(n,k)$ denote the number of valid walks that satisfy all those visit constraints and end at any endpoint $e \in \{0,1,\dots,n\}$. The program computes

$$\Bigl(W(500,1)+W(500,10)+W(500,100)+W(500,1000)+W(500,10000)\Bigr)\bmod 987898789.$$

The checkpoints hard-coded in the file are

$$W(3,2)=17,\qquad W(6,1)=1320,\qquad W(6,5)=16793280.$$

Mathematical Approach

1. Fix the Endpoint and Count Edge Crossings

For a fixed endpoint $e$, define for each edge $i$ between $i-1$ and $i$ ($1 \le i \le n$):

$$R_i=\#\{\text{crossings } i-1 \to i\},\qquad L_i=\#\{\text{crossings } i \to i-1\}.$$

Because the walk starts to the left of every edge, the net balance across edge $i$ is determined by whether the endpoint lies to the right of that edge:

$$R_i-L_i=\mathbf{1}_{e \ge i}.$$

This is the key observation: once the endpoint is fixed, the imbalance on every edge is fixed as well.

2. Visit Equations Force a Simple Recurrence

Write

$$t_i=k+i\qquad (0 \le i \lt n)$$

for the required visit count of tracked vertex $i$.

At vertex $0$, the walk starts with one visit already counted, and every later visit must come from edge $1$. Therefore

$$1+L_1=t_0=k,$$

$$R_1=L_1+\mathbf{1}_{e \ge 1}=k-\mathbf{1}_{e=0}.$$

For an interior tracked vertex $i$ with $1 \le i \lt n$, every visit to $i$ comes either from the left through edge $i$ or from the right through edge $i+1$. Hence

$$t_i=R_i+L_{i+1}=k+i.$$

Using $R_{i+1}=L_{i+1}+\mathbf{1}_{e \ge i+1}$, we get

$$R_{i+1}=k+i-R_i+\mathbf{1}_{e>i}.$$

This is exactly the recurrence implemented in solve_endpoint. So for a fixed endpoint, all right-crossing counts $R_1,R_2,\dots,R_n$ are forced.

3. Why a Binomial Coefficient Appears

Now cut the path between $i-1$ and $i$, where $1 \le i \lt n$. From the viewpoint of vertex $i-1$, everything on the right side $\{i,i+1,\dots,n\}$ is an excursion block: once the walk crosses from $i-1$ to $i$, it wanders inside the suffix and later either returns to $i-1$ or, on the final excursion, ends on the right side.

Across this cut, the walk makes $R_i$ left-to-right excursions in total. The first such excursion is forced by the existence of the suffix activity. After that, the remaining $R_i-1$ excursions can be attached to any subset of the $t_{i-1}=k+i-1$ visits to vertex $i-1$. Therefore the number of choices contributed by this cut is

$$\binom{k+i-1}{R_i-1}.$$

There is no extra factor for the last edge $n$, because the suffix $\{n\}$ is trivial: once the walk reaches the auxiliary vertex, the only local behavior is an immediate return or the final stop.

4. Product Formula for a Fixed Endpoint

The choices coming from different cuts are nested but independent once the crossing numbers are fixed. Therefore, for a fixed endpoint $e$, the total number of valid walks is

$$\boxed{W(n,k;e)=\prod_{i=1}^{n-1}\binom{k+i-1}{R_i-1}.}$$

Finally we sum over all possible endpoints:

$$\boxed{W(n,k)=\sum_{e=0}^{n} W(n,k;e).}$$

5. Worked Checkpoint: $W(3,2)=17$

Here the tracked visit counts are $t_0=2$, $t_1=3$, $t_2=4$.

If $e=0$, then $R_1=1$, $R_2=2$, and

$$W(3,2;0)=\binom{2}{0}\binom{3}{1}=3.$$

If $e=1$, then $R_1=2$, $R_2=1$, and

$$W(3,2;1)=\binom{2}{1}\binom{3}{0}=2.$$

If $e=2$, then $R_1=2$, $R_2=2$, and

$$W(3,2;2)=\binom{2}{1}\binom{3}{1}=6.$$

If $e=3$, the same crossing numbers occur, so

$$W(3,2;3)=6.$$

Thus

$$W(3,2)=3+2+6+6=17,$$

which matches the checkpoint used by the code.

6. Modular Binomials via Pascal's Triangle

The values $\binom{r}{c}$ become enormous, so the implementation never constructs them exactly. It builds the needed rows of Pascal's triangle modulo

$$M=987898789.$$

For the target computation, the required rows are $k,k+1,\dots,k+n-2$ for $k \in \{1,10,100,1000,10000\}$. The helper build_needed_binomials walks through Pascal's triangle once, stores only the rows that will actually be queried later, and then every endpoint evaluation becomes a product lookup modulo $M$.

How the Code Works

build_needed_binomials precomputes Pascal rows modulo $987898789$. Then solve_endpoint fixes an endpoint $e$, reconstructs the forced sequence of right-crossing counts $R_i$, and multiplies the corresponding binomial factors. The wrapper solve sums those counts over all $e=0,\dots,n$. Finally solve_target evaluates $W(500,k)$ for the five required $k$-values and adds the results modulo $987898789$.

The brute-force routine is only a checkpoint mechanism for tiny instances. It recursively explores all admissible walks for $n \le 6$, memoizes states, and confirms that the closed-form combinatorial count matches explicit enumeration.

Complexity Analysis

Let

$$M=\max(K)+n-2,$$

where $K=\{1,10,100,1000,10000\}$. Building Pascal rows up to $M$ costs $O(M^2)$ modular additions. After that, each endpoint evaluation is $O(n)$, so one call to $W(n,k)$ is $O(n^2)$ because it sums over $n+1$ endpoints. Therefore the full target computation runs in

$$O(M^2 + |K|n^2)$$

time. Memory usage is the total size of the stored Pascal rows, which is far smaller than storing the full triangle because only the queried rows are retained.

Problem 992 source code

C++

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <map>
#include <string>
#include <vector>

namespace {

using u32 = std::uint32_t;
using u64 = std::uint64_t;

constexpr u32 MOD = 987'898'789U;
constexpr int TARGET_N = 500;
constexpr std::array<int, 5> K_VALUES = {1, 10, 100, 1000, 10000};

u32 mod_add(const u32 a, const u32 b) {
    const u32 sum = a + b;
    return sum >= MOD ? sum - MOD : sum;
}

u32 mod_mul(const u32 a, const u32 b) {
    return static_cast<u32>((static_cast<u64>(a) * static_cast<u64>(b)) % static_cast<u64>(MOD));
}

std::vector<std::vector<u32>> build_needed_binomials(const int n, const std::array<int, 5>& k_values) {
    int max_row = 0;
    std::vector<bool> needed(1, false);
    for (const int k : k_values) {
        max_row = std::max(max_row, k + n - 2);
    }
    needed.assign(static_cast<std::size_t>(max_row + 1), false);
    for (const int k : k_values) {
        for (int row = k; row <= k + n - 2; ++row) {
            needed[static_cast<std::size_t>(row)] = true;
        }
    }

    std::vector<std::vector<u32>> rows(static_cast<std::size_t>(max_row + 1));
    std::vector<u32> current(1, 1U);
    for (int row = 1; row <= max_row; ++row) {
        current.push_back(1U);
        for (int col = row - 1; col >= 1; --col) {
            current[static_cast<std::size_t>(col)] =
                mod_add(current[static_cast<std::size_t>(col)], current[static_cast<std::size_t>(col - 1)]);
        }
        if (needed[static_cast<std::size_t>(row)]) {
            rows[static_cast<std::size_t>(row)] = current;
        }
    }
    return rows;
}

u32 solve_endpoint(const int n, const int k, const int endpoint, const std::vector<std::vector<u32>>& binomials) {
    int right_crossings = k - (endpoint == 0 ? 1 : 0);
    u32 ways = 1U;

    for (int stone = 1; stone < n; ++stone) {
        const int row = k + stone - 1;
        if (right_crossings <= 0 || right_crossings > row + 1) {
            return 0U;
        }
        ways = mod_mul(ways, binomials[static_cast<std::size_t>(row)][static_cast<std::size_t>(right_crossings - 1)]);
        right_crossings = k + stone - right_crossings + (endpoint > stone ? 1 : 0);
    }

    return ways;
}

u32 solve(const int n, const int k, const std::vector<std::vector<u32>>& binomials) {
    u32 total = 0U;
    for (int endpoint = 0; endpoint <= n; ++endpoint) {
        total = mod_add(total, solve_endpoint(n, k, endpoint, binomials));
    }
    return total;
}

u64 brute_force(const int n, const int k) {
    const std::vector<int> target = [&]() {
        std::vector<int> counts(static_cast<std::size_t>(n));
        for (int i = 0; i < n; ++i) {
            counts[static_cast<std::size_t>(i)] = k + i;
        }
        return counts;
    }();

    std::map<std::vector<int>, u64> memo;

    std::function<u64(int, std::vector<int>&)> dfs = [&](const int position, std::vector<int>& counts) -> u64 {
        std::vector<int> state;
        state.reserve(static_cast<std::size_t>(n + 1));
        state.push_back(position);
        state.insert(state.end(), counts.begin(), counts.end());

        const auto it = memo.find(state);
        if (it != memo.end()) {
            return it->second;
        }

        bool complete = true;
        for (int i = 0; i < n; ++i) {
            if (counts[static_cast<std::size_t>(i)] > target[static_cast<std::size_t>(i)]) {
                return 0ULL;
            }
            if (counts[static_cast<std::size_t>(i)] != target[static_cast<std::size_t>(i)]) {
                complete = false;
            }
        }

        if (complete) {
            const u64 total = 1ULL + (position == n - 1 ? 1ULL : 0ULL);
            memo.emplace(std::move(state), total);
            return total;
        }

        u64 total = 0ULL;
        for (const int next : {position - 1, position + 1}) {
            if (next < 0 || next > n) {
                continue;
            }
            if (next < n) {
                ++counts[static_cast<std::size_t>(next)];
                if (counts[static_cast<std::size_t>(next)] <= target[static_cast<std::size_t>(next)]) {
                    total += dfs(next, counts);
                }
                --counts[static_cast<std::size_t>(next)];
            } else {
                total += dfs(next, counts);
            }
        }

        memo.emplace(std::move(state), total);
        return total;
    };

    std::vector<int> counts(static_cast<std::size_t>(n), 0);
    counts[0] = 1;
    return dfs(0, counts);
}

void run_checkpoints(const std::vector<std::vector<u32>>& binomials) {
    for (int n = 1; n <= 6; ++n) {
        for (int k = 1; k <= 3; ++k) {
            assert(static_cast<u64>(solve(n, k, binomials)) == brute_force(n, k));
        }
    }

    assert(solve(3, 2, binomials) == 17U);
    assert(solve(6, 1, binomials) == 1320U);
    assert(solve(6, 5, binomials) == 16'793'280U);
}

u32 solve_target(const std::vector<std::vector<u32>>& binomials) {
    u32 total = 0U;
    for (const int k : K_VALUES) {
        total = mod_add(total, solve(TARGET_N, k, binomials));
    }
    return total;
}

}  // namespace

int main(int argc, char** argv) {
    bool should_run_checkpoints = true;
    for (int i = 1; i < argc; ++i) {
        if (std::string(argv[i]) == "--skip-checkpoints") {
            should_run_checkpoints = false;
        }
    }

    const std::vector<std::vector<u32>> binomials = build_needed_binomials(TARGET_N, K_VALUES);

    if (should_run_checkpoints) {
        run_checkpoints(binomials);
    }

    std::cout << solve_target(binomials) << '\n';
    return 0;
}

Python

from functools import lru_cache
import sys

MOD = 987_898_789
TARGET_N = 500
K_VALUES = (1, 10, 100, 1000, 10000)


def mod_add(a, b):
    total = a + b
    return total - MOD if total >= MOD else total


def mod_mul(a, b):
    return (a * b) % MOD


def build_needed_binomials(n, k_values):
    max_row = 0
    for k in k_values:
        max_row = max(max_row, k + n - 2)

    needed = [False] * (max_row + 1)
    for k in k_values:
        for row in range(k, k + n - 1):
            needed[row] = True

    rows = [None] * (max_row + 1)
    current = [1]

    for row in range(1, max_row + 1):
        current.append(1)
        for col in range(row - 1, 0, -1):
            current[col] = mod_add(current[col], current[col - 1])
        if needed[row]:
            rows[row] = current.copy()

    return rows


def solve_endpoint(n, k, endpoint, binomials):
    right_crossings = k - (1 if endpoint == 0 else 0)
    ways = 1

    for stone in range(1, n):
        row = k + stone - 1
        if right_crossings <= 0 or right_crossings > row + 1:
            return 0
        ways = mod_mul(ways, binomials[row][right_crossings - 1])
        right_crossings = k + stone - right_crossings + (1 if endpoint > stone else 0)

    return ways


def solve(n, k, binomials):
    total = 0
    for endpoint in range(n + 1):
        total = mod_add(total, solve_endpoint(n, k, endpoint, binomials))
    return total


def brute_force(n, k):
    target = tuple(k + i for i in range(n))

    @lru_cache(maxsize=None)
    def dfs(position, counts):
        complete = True
        for i, count in enumerate(counts):
            if count > target[i]:
                return 0
            if count != target[i]:
                complete = False

        if complete:
            return 1 + (1 if position == n - 1 else 0)

        total = 0
        for nxt in (position - 1, position + 1):
            if nxt < 0 or nxt > n:
                continue
            if nxt < n:
                next_counts = list(counts)
                next_counts[nxt] += 1
                if next_counts[nxt] <= target[nxt]:
                    total += dfs(nxt, tuple(next_counts))
            else:
                total += dfs(nxt, counts)
        return total

    counts = [0] * n
    counts[0] = 1
    return dfs(0, tuple(counts))


def run_checkpoints(binomials):
    for n in range(1, 7):
        for k in range(1, 4):
            assert solve(n, k, binomials) == brute_force(n, k)

    assert solve(3, 2, binomials) == 17
    assert solve(6, 1, binomials) == 1320
    assert solve(6, 5, binomials) == 16_793_280


def solve_target(binomials):
    total = 0
    for k in K_VALUES:
        total = mod_add(total, solve(TARGET_N, k, binomials))
    return total


def main(argv=None):
    argv = sys.argv if argv is None else argv
    should_run_checkpoints = True

    for arg in argv[1:]:
        if arg == "--skip-checkpoints":
            should_run_checkpoints = False
            continue
        print(f"Unknown argument: {arg}", file=sys.stderr)
        return 1

    binomials = build_needed_binomials(TARGET_N, K_VALUES)

    if should_run_checkpoints:
        run_checkpoints(binomials)

    print(solve_target(binomials))
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Euler992 {
    private static final int MOD = 987_898_789;
    private static final int TARGET_N = 500;
    private static final int[] K_VALUES = {1, 10, 100, 1000, 10000};

    private static final class State {
        private final int position;
        private final int[] counts;

        private State(int position, int[] counts) {
            this.position = position;
            this.counts = counts.clone();
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }
            if (!(other instanceof State)) {
                return false;
            }
            State rhs = (State) other;
            return position == rhs.position && Arrays.equals(counts, rhs.counts);
        }

        @Override
        public int hashCode() {
            return 31 * Integer.hashCode(position) + Arrays.hashCode(counts);
        }
    }

    private static int modAdd(int a, int b) {
        int total = a + b;
        return total >= MOD ? total - MOD : total;
    }

    private static int modMul(int a, int b) {
        return (int) (((long) a * (long) b) % MOD);
    }

    private static int[][] buildNeededBinomials(int n, int[] kValues) {
        int maxRow = 0;
        for (int k : kValues) {
            maxRow = Math.max(maxRow, k + n - 2);
        }

        boolean[] needed = new boolean[maxRow + 1];
        for (int k : kValues) {
            for (int row = k; row <= k + n - 2; ++row) {
                needed[row] = true;
            }
        }

        int[][] rows = new int[maxRow + 1][];
        int[] current = new int[maxRow + 1];
        current[0] = 1;

        for (int row = 1; row <= maxRow; ++row) {
            current[row] = 1;
            for (int col = row - 1; col >= 1; --col) {
                current[col] = modAdd(current[col], current[col - 1]);
            }
            if (needed[row]) {
                rows[row] = Arrays.copyOf(current, row + 1);
            }
        }

        return rows;
    }

    private static int solveEndpoint(int n, int k, int endpoint, int[][] binomials) {
        int rightCrossings = k - (endpoint == 0 ? 1 : 0);
        int ways = 1;

        for (int stone = 1; stone < n; ++stone) {
            int row = k + stone - 1;
            if (rightCrossings <= 0 || rightCrossings > row + 1) {
                return 0;
            }
            ways = modMul(ways, binomials[row][rightCrossings - 1]);
            rightCrossings = k + stone - rightCrossings + (endpoint > stone ? 1 : 0);
        }

        return ways;
    }

    private static int solve(int n, int k, int[][] binomials) {
        int total = 0;
        for (int endpoint = 0; endpoint <= n; ++endpoint) {
            total = modAdd(total, solveEndpoint(n, k, endpoint, binomials));
        }
        return total;
    }

    private static long bruteForceDfs(
        int position,
        int[] counts,
        int[] target,
        int n,
        Map<State, Long> memo
    ) {
        State state = new State(position, counts);
        Long cached = memo.get(state);
        if (cached != null) {
            return cached.longValue();
        }

        boolean complete = true;
        for (int i = 0; i < n; ++i) {
            if (counts[i] > target[i]) {
                return 0L;
            }
            if (counts[i] != target[i]) {
                complete = false;
            }
        }

        if (complete) {
            long total = 1L + (position == n - 1 ? 1L : 0L);
            memo.put(state, total);
            return total;
        }

        long total = 0L;
        int[] nexts = {position - 1, position + 1};
        for (int next : nexts) {
            if (next < 0 || next > n) {
                continue;
            }
            if (next < n) {
                counts[next] += 1;
                if (counts[next] <= target[next]) {
                    total += bruteForceDfs(next, counts, target, n, memo);
                }
                counts[next] -= 1;
            } else {
                total += bruteForceDfs(next, counts, target, n, memo);
            }
        }

        memo.put(state, total);
        return total;
    }

    private static long bruteForce(int n, int k) {
        int[] target = new int[n];
        for (int i = 0; i < n; ++i) {
            target[i] = k + i;
        }

        int[] counts = new int[n];
        counts[0] = 1;
        return bruteForceDfs(0, counts, target, n, new HashMap<>());
    }

    private static void runCheckpoints(int[][] binomials) {
        for (int n = 1; n <= 6; ++n) {
            for (int k = 1; k <= 3; ++k) {
                if ((long) solve(n, k, binomials) != bruteForce(n, k)) {
                    throw new IllegalStateException("Checkpoint failed for n=" + n + ", k=" + k);
                }
            }
        }

        if (solve(3, 2, binomials) != 17) {
            throw new IllegalStateException("Checkpoint failed for W(3,2)");
        }
        if (solve(6, 1, binomials) != 1320) {
            throw new IllegalStateException("Checkpoint failed for W(6,1)");
        }
        if (solve(6, 5, binomials) != 16_793_280) {
            throw new IllegalStateException("Checkpoint failed for W(6,5)");
        }
    }

    private static int solveTarget(int[][] binomials) {
        int total = 0;
        for (int k : K_VALUES) {
            total = modAdd(total, solve(TARGET_N, k, binomials));
        }
        return total;
    }

    public static void main(String[] args) {
        boolean shouldRunCheckpoints = true;

        for (String arg : args) {
            if ("--skip-checkpoints".equals(arg)) {
                shouldRunCheckpoints = false;
                continue;
            }
            System.err.println("Unknown argument: " + arg);
            System.exit(1);
        }

        int[][] binomials = buildNeededBinomials(TARGET_N, K_VALUES);

        if (shouldRunCheckpoints) {
            runCheckpoints(binomials);
        }

        System.out.println(solveTarget(binomials));
    }
}