×

# CDZ14B - Editorial

Author: sikander_nsit
Tester: sikander_nsit
Editorialist: sikander_nsit

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.

1. Its length should be less than equal to L.
2. Password[i] <= S[i] for 0 <= i < min( |S|, |password| ).
3. 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.

This question is marked "community wiki".

1.5k82130
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,722
×348
×281
×10
×1

question asked: 11 Feb '14, 03:54

question was seen: 1,019 times

last updated: 08 Jun '16, 06:28