← Problem archive

USAAIO 2025 Round 1 · Problem 1 · Linear recurrence & complexity

Contest: 2025 USA-NA-AIO Round 1 · Round: Round 1 (online, mixed theory + code) · Category: Theory / math reasoning / algorithmic complexity.

Official sources: usaaio.org/past-problems · 2025 Round 1 forum (in partnership with USAAIO) · Problem 1 Part 1 thread.

1. Problem restatement

Define a Fibonacci-like recurrence

F_n = F_{n-1} + F_{n-2}    for all n >= 2
F_0 = 3
F_1 = 1

The problem is broken into many parts (the published Part 1 alone is 10 points of a 100-point set). The published parts ask the contestant to:

1. Part 1 — Manually compute F_2, F_3, F_4, F_5.
2. Later parts (per the Round-1 thread structure) — write recursive and iterative implementations, analyse their time and space complexity, derive a closed-form Binet-style expression for F_n, and use matrix exponentiation to compute F_n mod p for very large n.

Only Part 1 is fully reproduced in the public forum thread; the remaining parts are summarised here from the documented Round-1 structure ("recurrence → recursion → memoisation → closed form → matrix power → modular arithmetic" — the canonical progression for this kind of olympiad problem). The overall problem is non-ML: it tests algorithmic literacy and math that underlies dynamic programming, RNN unrolls, and gradient-flow analysis in deep nets.

2. What's being tested

• Recursion vs iteration vs memoisation — naive recursion is O(phi^n); memoised / iterative DP is O(n). This is the classical first lecture of any algorithms course and the kind of question Round 1 uses to filter out students who can code but not analyse.
• Linear algebra of recurrences — every linear recurrence can be written as a matrix-vector update. Eigenvalues of the transition matrix give the closed form; powers of the transition matrix give an O(log n) algorithm.
• Numerical stability — Binet's formula uses sqrt(5) and overflows beyond n ≈ 70 in double precision. Modular matrix exponentiation handles it correctly.

This maps directly onto the Math page sections on linear algebra and eigenvalues, and onto algorithmic-thinking patterns that recur in the RNN backprop section of the Deep Learning page.

3. Data exploration / setup

There is no dataset — this is a pen-and-paper / numeric-code problem. The "input" is a small integer n (Part 1: n ≤ 5; later parts may push to n = 10^18 with answers taken modulo a prime). The "output" is F_n, possibly modulo p.

The constraint that matters: can you compute F_n in time polylogarithmic in n? For n up to ~50, naive recursion is fine. For n up to ~10^7, iterative DP. For n up to 10^18 (the range where matrix exponentiation is forced), only the O(log n) approach works.

4. Baseline approach

Part 1 is a manual computation. Plug in:

F_0 = 3
F_1 = 1
F_2 = F_1 + F_0 = 1 + 3 = 4
F_3 = F_2 + F_1 = 4 + 1 = 5
F_4 = F_3 + F_2 = 5 + 4 = 9
F_5 = F_4 + F_3 = 9 + 5 = 14

This matches the official key (F_2 = 4, F_3 = 5, F_4 = 9, F_5 = 14).

For the iterative version that handles small n efficiently:

def fib(n, F0=3, F1=1):
    if n == 0: return F0
    if n == 1: return F1
    a, b = F0, F1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

assert [fib(i) for i in range(6)] == [3, 1, 4, 5, 9, 14]

Time complexity: O(n). Space: O(1) if you keep only the two previous values; O(n) if you store the full array.

5. Improvements that move the needle

5.1 · Naive recursion (and why not to submit it)

def fib_naive(n):
    if n == 0: return 3
    if n == 1: return 1
    return fib_naive(n - 1) + fib_naive(n - 2)

Time complexity: O(phi^n) where phi = (1 + sqrt(5))/2 ≈ 1.618. For n = 40 this is ~10^8 calls and already painful; n = 50 takes minutes. Useful for grading "do you know it is exponential", not useful for any real computation.

5.2 · Memoised recursion

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n == 0: return 3
    if n == 1: return 1
    return fib_memo(n - 1) + fib_memo(n - 2)

Brings the cost down to O(n) time, O(n) space (call stack + cache). Pythonic and clean. The "improvement that moves the needle" relative to naive: exponential to linear.

5.3 · Closed-form (Binet-style)

The recurrence F_n = F_{n-1} + F_{n-2} has characteristic equation x^2 = x + 1 with roots phi = (1+sqrt(5))/2 and psi = (1-sqrt(5))/2. Any solution is F_n = A * phi^n + B * psi^n. Solve for A, B from initial conditions F_0 = 3, F_1 = 1:

# A + B = 3
# A*phi + B*psi = 1
# Solving:
# A = (1 - 3*psi) / (phi - psi) = (1 - 3*psi) / sqrt(5)
# B = (3*phi - 1) / (phi - psi) = (3*phi - 1) / sqrt(5)

import math
sqrt5 = math.sqrt(5)
phi   = (1 + sqrt5) / 2
psi   = (1 - sqrt5) / 2
A     = (1 - 3*psi) / sqrt5
B     = (3*phi - 1) / sqrt5

def fib_closed(n):
    return A * phi**n + B * psi**n

# verify against iterative for small n
assert all(round(fib_closed(i)) == [3, 1, 4, 5, 9, 14][i] for i in range(6))

Time: O(1) (in floating point). Catch: phi^n overflows double precision somewhere around n = 1474, and rounding error makes the result wrong before then. For "compute F_n exactly for very large n" you need the matrix approach below.

5.4 · Matrix exponentiation in O(log n)

Stack the recurrence into a 2×2 transition matrix:

[F_{n+1}]   [1  1] [F_n  ]
[F_n    ] = [1  0] [F_{n-1}]

so  [F_n+1, F_n]^T  =  M^n  [F_1, F_0]^T   with M = [[1,1],[1,0]].

Compute M^n by repeated squaring: O(log n) multiplications. Each entry stays an integer if you keep arithmetic in Python's arbitrary-precision int, so this gives exact F_n for n = 10^18. Doing it modulo a prime is even cheaper.

def mat_mul(A, B, mod=None):
    a, b, c, d = A
    e, f, g, h = B
    out = (a*e + b*g, a*f + b*h, c*e + d*g, c*f + d*h)
    return tuple(x % mod for x in out) if mod else out

def mat_pow(M, n, mod=None):
    result = (1, 0, 0, 1)            # identity
    while n > 0:
        if n & 1:
            result = mat_mul(result, M, mod)
        M = mat_mul(M, M, mod)
        n >>= 1
    return result

def fib_matrix(n, F0=3, F1=1, mod=None):
    if n == 0: return F0 % mod if mod else F0
    if n == 1: return F1 % mod if mod else F1
    a, b, c, d = mat_pow((1, 1, 1, 0), n - 1, mod)
    val = a*F1 + b*F0
    return val % mod if mod else val

# F_5 = 14, F_50 (a large integer), F_{10**18} mod (10**9 + 7) in < 1ms
assert fib_matrix(5) == 14
print(fib_matrix(10**18, mod=10**9 + 7))

5.5 · Connection to ML / RNNs

The matrix view is not just a CS trick — it is exactly the lens the Math page applies to RNN gradient flow. An RNN's hidden state update is h_t = W h_{t-1} + ...; the eigenvalues of W govern whether gradients explode (|lambda| > 1) or vanish (|lambda| < 1). For Fibonacci, phi > 1, so the sequence "explodes" — this is precisely why training a vanilla RNN on long sequences without gating fails: the dominant eigenvalue is > 1. LSTMs and skip connections are engineered fixes for exactly this eigenvalue problem.

6. Submission format & gotchas

• Round-1 numeric answers must be entered exactly; expect the grader to check integer equality, not tolerance. Floating-point closed-form answers must be rounded with round() before submission.
• If a later part asks for F_n mod p for huge n, doing the modulus once at the end on a Python int "works" but takes seconds for n = 10^18 (the multiply-then-reduce gets slower as numbers grow). Always take the mod inside mat_mul.
• Off-by-one on initial conditions destroys you here. The problem uses F_0 = 3, F_1 = 1, not the standard Fibonacci F_0 = 0, F_1 = 1. Verify on the table before writing the matrix formula.
• If asked for the closed-form derivation, show the characteristic-polynomial step, not just the final A, B values. Partial credit hinges on the derivation.

7. What top solutions did

The forum discussion on the Beaver-Edge mirror documents that strong Round-1 solutions for this problem all (i) wrote the characteristic-polynomial derivation explicitly, (ii) implemented matrix exponentiation modulo a prime, and (iii) verified their matrix code against a small-n iterative reference. The published Part-1 solution key (F_2 = 4, F_3 = 5, F_4 = 9, F_5 = 14) is the only officially confirmed scoring data; full Round-1 leaderboard placement metrics are not public, so treat the structural advice above as derived from the published thread structure and from the standard olympiad rubric for this kind of recurrence problem — i.e. [illustrative] in absolute terms.

8. Drill

← Back to problem archive