TACNTSTR - editorial

PROBLEM LINK:

Practice
Contest

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)

Author’s/Tester’s Solutions:

Setter’s solution
Tester’s solution

2 Likes

my solution CodeChef: Practical coding for everyone

O(N)

3 Likes

Solution in O(2*N)

Here’s the link : CodeChef: Practical coding for everyone

2 Likes

Alternate Approach :

Define F(i) to be number of valid strings T which have i as the last position where it differs from S .

And G(i) be number of strings of length i which are >= prefix of S (prefix till i).

Then ,

Let X = S[i]-A

F(i) = G(i-1)*(25-X) and G(i) = G(i-1)*26-X+1 .

\sum_{i=0}^{n-1} F(i) is what we need .

7 Likes

Editorials should be more pictorial. Since, visualizing things like dp makes it more clear.

why this problem is not available for the practice.
when i am trying to open practice link getting message “Problem is not visible now. Please try again later.”

1 Like

what is wrong with this approach:

MOD = 10^9 + 7;

num = 1;

for i from 0 to n

  num = (num * (91 - string[i]))%MOD;

endfor

num = num - 1;

print num

somebody please upvote me , i have questions to ask
thank you

1 Like

Typo :
"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. " It should be ok2 = 1 in one of the two places .

2 Likes

is it correct " F(i) to be number of valid strings T which have i as the last position where it differs from S, and greater than S(till ‘i’) " ?

Can you please explain your approach?

G(i)=G(i-1)*26-X only !!

Try that and you will get a WA :slight_smile:

1 Like

Here is a case.
Suppose the given string is ACCK.
Your answer won’t consider the case like - BAAX.

1 Like