IOI 2008 - Linear Garden

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

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

    int N, M, K;
    // K is the balance bound (e.g., K=2 in the IOI problem)
    // M is the modulus
    cin >> N >> M >> K;

    string S;
    cin >> S;

    // Balance: L = +1, R = -1
    // Constraint: balance at every position is in [-K, K]

    // Precompute f[len][balance] = number of valid sequences of length len
    // starting from balance b, all intermediate balances in [-K, K]
    // f[0][b] = 1 for all valid b
    // f[len][b] = f[len-1][b+1] + f[len-1][b-1] (if b+1 and b-1 in range)

    int offset = K; // shift so indices are 0..2K
    int states = 2 * K + 1;

    // f[b] for current length (space optimized)
    vector<long long> f(states, 1); // f[0][b] = 1

    // We need f for lengths 0, 1, ..., N
    // Store f[len][b] for all lengths (we'll need f at various positions)
    vector<vector<long long>> F(N + 1, vector<long long>(states, 0));
    for (int b = 0; b < states; b++) F[0][b] = 1;

    for (int len = 1; len <= N; len++) {
        for (int b = 0; b < states; b++) {
            F[len][b] = 0;
            // Choose L (+1): new balance = b + 1 (relative), index b+1
            if (b + 1 < states) F[len][b] = (F[len][b] + F[len-1][b+1]) % M;
            // Choose R (-1): new balance = b - 1, index b-1
            if (b - 1 >= 0) F[len][b] = (F[len][b] + F[len-1][b-1]) % M;
        }
    }

    // Count valid sequences <= S
    long long ans = 0;
    int balance = 0; // current balance (0 = centered)
    bool valid = true;

    for (int i = 0; i < N; i++) {
        if (!valid) break;

        if (S[i] == 'R') {
            // The smaller choice is 'L' (balance += 1)
            int newBal = balance + 1;
            if (abs(newBal) <= K) {
                // Count valid completions of length N - i - 1 from balance newBal
                int remaining = N - i - 1;
                ans = (ans + F[remaining][newBal + offset]) % M;
            }
            // Continue with S[i] = 'R': balance -= 1
            balance -= 1;
        } else {
            // S[i] = 'L', no smaller option at this position
            balance += 1;
        }

        if (abs(balance) > K) {
            valid = false;
        }
    }

    if (valid) {
        ans = (ans + 1) % M; // count S itself
    }

    cout << ans << "\n";
    return 0;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage{geometry}
\usepackage{hyperref}
\geometry{margin=2.5cm}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\bfseries,
  breaklines=true,
  frame=single,
  numbers=left,
  numberstyle=\tiny,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2008 -- Linear Garden}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Statement}
A garden path of length $N$ consists of segments, each either \texttt{L} (left, $+1$) or \texttt{R} (right, $-1$). A sequence is \textbf{valid} if the running balance (cumulative sum) stays within $[-K, K]$ at every prefix. Given a valid sequence $S$, count the number of valid sequences lexicographically $\le S$, modulo $M$.

\section{Solution}

\subsection{Precompute Valid Completions}
Define $F[\ell][b]$ = number of valid binary sequences of length $\ell$ starting from balance $b$, such that the balance stays within $[-K, K]$ at every step. Recurrence:
\[
F[\ell][b] = F[\ell-1][b+1] + F[\ell-1][b-1],
\]
where $F[\ell][b] = 0$ if $|b| > K$, and $F[0][b] = 1$ for $|b| \le K$.

Since $b \in [-K, K]$, we shift indices: let $b' = b + K \in [0, 2K]$.

\subsection{Lexicographic Counting}
Process $S$ from left to right, maintaining the current balance $b = 0$.
\begin{enumerate}
    \item At position $i$, if $S[i] = \texttt{R}$: the smaller choice \texttt{L} (balance $b+1$) is lexicographically smaller. If $|b+1| \le K$, add $F[N-i-1][b+1]$ to the answer (the number of valid completions of length $N-i-1$ from balance $b+1$).
    \item Update balance: $b \gets b + 1$ if $S[i] = \texttt{L}$, or $b \gets b - 1$ if $S[i] = \texttt{R}$.
    \item If $|b| > K$, the prefix is invalid; stop.
\end{enumerate}
Finally, add 1 for $S$ itself (if valid).

\subsection{Complexity}
\begin{itemize}
    \item \textbf{Time:} $O(NK)$ for precomputing $F$, $O(N)$ for the counting sweep. With $K$ constant, total is $O(N)$.
    \item \textbf{Space:} $O(NK)$, or $O(K)$ with rolling arrays.
\end{itemize}

\section{C++ Solution}

\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;

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

    int N, M, K;
    cin >> N >> M >> K;

    string S;
    cin >> S;

    // F[len][b+K] = valid sequences of length len from balance b
    int states = 2 * K + 1;
    vector<vector<long long>> F(N + 1, vector<long long>(states, 0));
    for (int b = 0; b < states; b++) F[0][b] = 1;

    for (int len = 1; len <= N; len++) {
        for (int b = 0; b < states; b++) {
            F[len][b] = 0;
            if (b + 1 < states) F[len][b] = (F[len][b] + F[len-1][b+1]) % M;
            if (b - 1 >= 0)     F[len][b] = (F[len][b] + F[len-1][b-1]) % M;
        }
    }

    long long ans = 0;
    int balance = 0;
    bool valid = true;

    for (int i = 0; i < N && valid; i++) {
        if (S[i] == 'R') {
            // Smaller choice: L (balance + 1)
            int newBal = balance + 1;
            if (abs(newBal) <= K) {
                int remaining = N - i - 1;
                ans = (ans + F[remaining][newBal + K]) % M;
            }
            balance--; // take the R
        } else {
            // S[i] = 'L', no smaller option
            balance++;
        }
        if (abs(balance) > K) valid = false;
    }

    if (valid) ans = (ans + 1) % M; // count S itself

    cout << ans << "\n";
    return 0;
}
\end{lstlisting}

\section{Notes}
This solution combines two standard techniques:
\begin{enumerate}
    \item \textbf{Constrained-path counting DP}: equivalent to counting lattice paths that stay within horizontal barriers.
    \item \textbf{Lexicographic rank computation}: at each position, count valid completions of the ``smaller'' choice and accumulate.
\end{enumerate}

The DP $F[\ell][b]$ correctly enforces the balance constraint at every intermediate step (not just the endpoints), because the recurrence only allows transitions to adjacent balance values within $[-K, K]$.

\end{document}