You are not logged in. Please login at www.codechef.com to post your questions!

×

CDZ14B - Editorial

PROBLEM LINKS:

Practice
Contest

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.

  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".

asked 11 Feb '14, 03:54

sikander_nsit's gravatar image

5★sikander_nsit
1.5k82130
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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