USACO 2015 US Open, Gold Problem 2. Palindromic Paths




(Analysis by Nick Wu)

This is a DP problem where we iteratively count the number of palindromes that we can build from the middle.

Let f(a,r1,r2) be the number of palindromic strings that we can build of length 2a+1, where the start of the string is on row r1, the end of the string is on row r2, and the middle of the string is on the diagonal of the grid that goes from the top-right to the bottom-left of the grid. We initialize f(0,i,i)=1 for all possible rows. Because of the constraints of the DP state, the beginning and ending squares are uniquely determined by their row. Therefore, f(a,r1,r2) affects at most four other quantities:f(a+1,r1,r2), f(a+1,r1−1,r2),f(a+1,r1,r2+1), and f(a+1,r1−1,r2+1).

This gives an O(N^3) algorithm which can be implemented in O(N^2) memory because you only need to keep track of f(a,r1,r2) and f(a+1,r1,r2) concurrently over all possible pairs (r1,r2).

Here is my code.

import java.util.*;
public class palpathG {
  static int n;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader(""));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("palpath.out")));
    n = Integer.parseInt(br.readLine());
    char[][] grid = new char[n][n];
    for(int i = 0; i < n; i++) {
      String s = br.readLine();
      for(int j = 0; j < n; j++) {
        grid[i][j] = s.charAt(j);
    long[][] dp = new long[n][n];
    for(int i = 0; i < n; i++) {
      dp[i][i] = 1;
    final long MOD = 1000000007;
    for(int num = n-1; num >= 1; num--) {
      long[][] next = new long[n][n];
      for(int a = 0; a < n; a++) {
        int rowA = a;
        int colA = (num-1-a);
        if(colA < 0) continue;
        for(int b = 0; b < n; b++) {
          int rowB = b;
          int colB = 2*n-num-rowB-1;
          if(colB >= n) continue;
          if(grid[rowA][colA] != grid[rowB][colB]) continue;
          next[rowA][rowB] += dp[rowA][rowB];
          if(rowA+1 < n) next[rowA][rowB] += dp[rowA+1][rowB];
          if(rowB-1 >= 0) next[rowA][rowB] += dp[rowA][rowB-1];
          if(rowA+1 < n && rowB-1 >= 0) next[rowA][rowB] += dp[rowA+1][rowB-1];
          next[rowA][rowB] %= MOD;
      dp = next;