2015 Open Gold Problem 2 Palindromic Paths

Official Problem Statement

Palindromic Paths

Problem

The problem titled 'Palindromic Paths' is from the USACO 2015 Open Gold contest. The problem is about a rectangular pasture of M by N cells (1 <= M,N <= 15) where each cell contains a digit from 0 to 9. Starting at the top-left cell, Bessie the cow wants to walk to the bottom-right cell. At each step, Bessie can either move to the right or move downward.

However, Bessie wants the digits along her walk to form a palindrome, that is, they should read the same forwards and backwards. She wonders how many palindromic walks of the grid there are. We are tasked with computing the number of these palindromic paths modulo 1,000,000,007.

Solution

A direct depth-first search (DFS) approach to solving this problem will not work due to the large size of the grid. A more efficient approach is to use dynamic programming with a bit of state compression.

The key observation here is that for a path to be palindromic, the first half of the path must mirror the second half of the path. Also, since Bessie can only move to the right or down, the length of the path is always M + N - 1.

Based on these observations, we can divide the palindromic path into two halves. The first half starts from the top-left cell and the second half starts from the bottom-right cell. We can then simultaneously move inwards from both ends towards the middle. At each step, we need to ensure that the digits from both ends match.

To implement this idea, we can use dynamic programming. The state dp[i][j][k] represents the number of ways to choose some cells in the first i rows and last j rows, such that the total number of cells chosen is k and the digits of the cells chosen form a palindromic sequence.

To transition between states, we iterate over all possible ways to choose cells from the current row of the first half and the current row of the second half, and update our dp table accordingly.

Finally, we return the sum of dp[M][N][k] for all k from 0 to (M + N) / 2 modulo 1,000,000,007, which represents the total number of palindromic paths in the grid.

Code

C++

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

const int MOD = 1e9 + 7;
int gridSize;

vector<vector<long long>> calculateNextDP(vector<vector<char>>& grid, vector<vector<long long>>& dp, int num) {
    vector<vector<long long>> nextDP(gridSize, vector<long long>(gridSize));
    for (int a = 0; a < gridSize; a++) {
        int rowA = a;
        int colA = num - 1 - a;
        if (colA < 0) continue;
        for (int b = 0; b < gridSize; b++) {
            int rowB = b;
            int colB = 2 * gridSize - num - rowB - 1;
            if (colB >= gridSize || grid[rowA][colA] != grid[rowB][colB]) continue;

            nextDP[rowA][rowB] = dp[rowA][rowB];
            if (rowA + 1 < gridSize) nextDP[rowA][rowB] += dp[rowA + 1][rowB];
            if (rowB - 1 >= 0) nextDP[rowA][rowB] += dp[rowA][rowB - 1];
            if (rowA + 1 < gridSize && rowB - 1 >= 0) nextDP[rowA][rowB] += dp[rowA + 1][rowB - 1];
            nextDP[rowA][rowB] %= MOD;
        }
    }
    return nextDP;
}

int main() {
    ifstream cin("palpath.in");
    ofstream cout("palpath.out");

    cin >> gridSize;
    vector<vector<char>> grid(gridSize, vector<char>(gridSize));
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridSize; j++) {
            cin >> grid[i][j];
        }
    }

    vector<vector<long long>> dp(gridSize, vector<long long>(gridSize, 0));
    for (int i = 0; i < gridSize; i++) {
        dp[i][i] = 1;
    }

    for (int num = gridSize - 1; num >= 1; num--) {
        dp = calculateNextDP(grid, dp, num);
    }

    cout << dp[0][gridSize - 1] << "\n";
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class PalindromicPath {
  static int gridSize;
  static final long MOD = 1000000007;

  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new FileReader("palpath.in"));
    PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("palpath.out")));
    
    gridSize = Integer.parseInt(reader.readLine());
    
    char[][] grid = new char[gridSize][gridSize];
    for (int i = 0; i < gridSize; i++) {
      String row = reader.readLine();
      for (int j = 0; j < gridSize; j++) {
        grid[i][j] = row.charAt(j);
      }
    }
    
    long[][] dp = new long[gridSize][gridSize];
    for (int i = 0; i < gridSize; i++) {
      dp[i][i] = 1;
    }

    for (int num = gridSize - 1; num >= 1; num--) {
      dp = calculateNextDP(grid, dp, num);
    }
    
    writer.println(dp[0][gridSize - 1]);
    writer.close();
  }

  private static long[][] calculateNextDP(char[][] grid, long[][] dp, int num) {
    long[][] nextDP = new long[gridSize][gridSize];
    
    for (int a = 0; a < gridSize; a++) {
      int rowA = a;
      int colA = num - 1 - a;
      
      if (colA < 0) {
        continue;
      }

      for (int b = 0; b < gridSize; b++) {
        int rowB = b;
        int colB = 2 * gridSize - num - rowB - 1;
        
        if (colB >= gridSize || grid[rowA][colA] != grid[rowB][colB]) {
          continue;
        }

        nextDP[rowA][rowB] = getUpdatedDPValue(dp, rowA, rowB);
      }
    }
    
    return nextDP;
  }

  private static long getUpdatedDPValue(long[][] dp, int rowA, int rowB) {
    long nextValue = dp[rowA][rowB];

    if (rowA + 1 < gridSize) {
      nextValue += dp[rowA + 1][rowB];
    }

    if (rowB - 1 >= 0) {
      nextValue += dp[rowA][rowB - 1];
    }

    if (rowA + 1 < gridSize && rowB - 1 >= 0) {
      nextValue += dp[rowA + 1][rowB - 1];
    }

    return nextValue % MOD;
  }
}

Python

MOD = 10**9 + 7

def calculate_next_dp(grid, dp, num):
    next_dp = [[0]*len(grid) for _ in range(len(grid))]
    for a in range(len(grid)):
        rowA = a
        colA = num - 1 - a
        if colA < 0:
            continue
        for b in range(len(grid)):
            rowB = b
            colB = 2*len(grid) - num - rowB - 1
            if colB >= len(grid) or grid[rowA][colA] != grid[rowB][colB]:
                continue
            next_dp[rowA][rowB] = dp[rowA][rowB]
            if rowA + 1 < len(grid):
                next_dp[rowA][rowB] += dp[rowA + 1][rowB]
            if rowB - 1 >= 0:
                next_dp[rowA][rowB] += dp[rowA][rowB - 1]
            if rowA + 1 < len(grid) and rowB - 1 >= 0:
                next_dp[rowA][rowB] += dp[rowA + 1][rowB - 1]
            next_dp[rowA][rowB] %= MOD
    return next_dp

def main():
    with open('palpath.in', 'r') as fin:
        gridSize = int(fin.readline().strip())
        grid = [list(line.strip()) for line in fin]

    dp = [[0]*gridSize for _ in range(gridSize)]
    for i in range(gridSize):
        dp[i][i] = 1

    for num in range(gridSize - 1, 0, -1):
        dp = calculate_next_dp(grid, dp, num)

    with open('palpath.out', 'w') as fout:
        fout.write(str(dp[0][gridSize - 1]) + '\n')

if __name__ == "__main__":
    main()