PROBLEM LINKS:
Author: sikander_nsit
Tester: sikander_nsit
Editorialist: sikander_nsit
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
Given string S and number L we had to find the number of valid passwords. There are three conditions on the password.
-
Its length should be less than equal to L.
-
Password[i] <= S[i] for 0 <= i < min( |S|, |password| ).
-
The password is lexicographically smaller than S.
EXPLANATION:
Let us take an example to understand it.
Given string is: “DBF” and L=6.
Strings with maximum length 1 which are smaller than “DBF” are “A”, “B”, “C” and “D” so 4.
Number of Strings with maximum length 2 will be 4*2=8.
Similarly number of strings with maximum length 3 will be 4*2*6-1=47 (because we cannot include “DBF”).
Now number of strings with maximum length 4 will be 47*26 (adding a letter at the end).
Similarly number of strings with maximum length 5 and 6 will be 47*26*26 and 47*26*26*26 respectively.
So the total answer becomes 4 + 4*2 + 4*2*6 – 1 + 47*26 + 47*26*26 + 47*26*26*26.
The first part of the answer can be calculated in O(n) where n is length of given string using the following pseudocode.
for(j=0;j<str.length();++j)
{
temp*=(str[j]-96);
ans+=temp;
}
The second part can be calculated using the formula for the sum of GP. Since L can be very large modular exponentiation can be used to do this in O(log L).
Also the term 25 in the denominator while calculating the GP sum would have to be taken care of. For this inverse modulus can be used also logarithmic time.
AUTHOR’S SOLUTION:
Author’s solution can be found here.