PAT Advanced 1093 Count PAT’s: DP + Constant Space

Overview

PAT Advanced 1093 Count PAT’s is solved by dynamic programming (DP) using constant space as the states only depends on previous one, Java is too slow to AC.

PAT Advanced 1093 Count PAT’s

Logo

The string APPAPT contains two PAT‘s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT‘s contained in the string.

Input Specification:

Each input file contains one test case. For each case, there is only one line giving a string of no more than 105 characters containing only P, A, or T.

Output Specification:

For each test case, print in one line the number of PAT‘s contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:

APPAPT

Sample Output:

2

Solution: DP + Constant Space

The key is to find the recursive definition/DP function of the counts of PAT within the given string. And the problem is simplified by the fact that it only contains 3 characters {P, A, T}, so the recursive function is easier to derive by considering the last char within the string, and the results of a string of length n could be calculated from the results of the string of length n – 1, and we do not need to allocate an array to store those temporary results, the following C++ code could be accepted by PAT OJ for this 1093 Count PAT’s problem but the java code with the exact same logic can not pass because Java is still too slow:

#include <iostream>

const long long MOD_NUMBER = 1000000007l;

long long countPATs(const std::string s) {
	long long pCounts = 0L;
	long long paCounts = 0L;
	long long patCounts = 0L;

	int len = s.size();
	if (len < 3) {
		return 0;
	}

	for (int i = 3; i <= len; ++i) {
		pCounts = (s[i - 3] == 'P' ? pCounts + 1 : pCounts);
		paCounts = (s[i - 2] == 'A' ?
				(paCounts % MOD_NUMBER + pCounts % MOD_NUMBER) % MOD_NUMBER: paCounts);
		patCounts = (s[i - 1] == 'T') ? (patCounts % MOD_NUMBER + paCounts % MOD_NUMBER) : patCounts;
	}
	return patCounts % MOD_NUMBER;
}

int main() {
	std::string str;
	std::cin >> str;
	std::cout << countPATs(str);
	return 0;
}

And I give the Java code too, but unfortunately, it cannot be accepted because of TLE, if anyone could give a Java solution to pass the OJ, that would be awesome and greatly appreciated.

import java.util.Scanner;

/**
 * @author Sigmainfy
 * @see <a href="/blog/pat-advanced-1093-count-pats-dp-constant-space.html">http://tech-wonderland.net/blog/pat-advanced-1093-count-pats-dp-constant-space.html</a>
 */

public class Main {

	public static final long MOD_NUMBER = 1000000007L;

	private static long countPATs(final String s) {
		long pCounts = 0L;
		long paCounts = 0L;
		long patCounts = 0L;

		int len = s.length();
		if (len < 3) {
			return 0;
		}

		for (int i = 3; i <= len; ++i) {
			pCounts = (s.charAt(i - 3) == 'P' ? pCounts + 1 : pCounts);
			paCounts = (s.charAt(i - 2) == 'A' ?
					(paCounts % MOD_NUMBER + pCounts % MOD_NUMBER) % MOD_NUMBER: paCounts);
			patCounts = (s.charAt(i - 1) == 'T') ? (patCounts % MOD_NUMBER + paCounts % MOD_NUMBER) : patCounts;
		}
		return patCounts % MOD_NUMBER;
	}

	public static void main(String [] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.println(countPATs(scanner.next()));
		scanner.close();
	}
}

Let me recap the key notes to keep in mind about this 1093 Count PAT’s problem:

  1. Dynamic Programming is the correct way to solve it
  2. The result of a string with length n only depends on some temporary results of the previous state for the substring of length n – 1
  3. Java is too slow and would be TLE, I assume it is the IO problem (note sure exactly which part is the bottleneck for Java)

Summary

PAT Advanced 1093 Count PAT’s is solved by dynamic programming (DP) using constant space as the states only depends on previous one, Java is too slow to AC.

Written on May 23, 2015