PROBLEM LINK:
Author: Tuấn Anh Trần Đặng
Tester: Kamil Dębowski
Editorialist: Tuấn Anh Trần Đặng
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming
Problem
Given the string S count the number of the strings of same length T such that T is lexicographically bigger then S and when we reverse the order of characters in both of the two strings T is still lexicographically bigger than S.
Solution
We will using dynamic programing (dp). Let F[i][ok1][ok2] is the number of the strings T that we can generated if we already got the first i-1 characters of it and ok1 and ok2 represent the following information:
- ok1 = 0 mean the first i - 1 characters of T still match the corresponding t - 1 characters of S. ok1 = 1 mean T is larger then S.
- ok2 = 0 mean in the reversed order the first t - 1 characters in T is already lexicographically larger then the corresponding characters in S. ok2 = 0 if otherwise.
Let N is the length of S The result of course will be F[0][0][0]. We can initialize the dp with FN + 11 = 1. We will calculate F in the decreasing order of i. With each i, ok1, ok2, we try to put all possible character in position i so that T is never lexicographically smaller than S in the original order:
//let s is 0-indexed
for (int i = N - 1; i > 0; i--)
for (int ok1 = 0; ok1 <= 1; ok1++)
for (int ok2 = 0; ok2 <= 1; ok2++) {
//make sure that T is always lexicographically larger than S in original order
for (char c = ok1 == 0 ? s[i] : 'A'; c <= 'Z'; c++) {
int nextOk2 = ok2;
if (c != s[pos]) {
//if we put a character c > s[pos] in position pos of T then T became lexicographically larger than S in reversed order
nextOk2 = c > s[pos];
}
f[pos][ok1][ok2] = (f[pos][ok1][ok2] + f[pos + 1][ok1 || c > s[pos]][nextOk2]) % MOD;
}
}
The complexity will be O(N × 2 × 2 × 26)
