CODE1604-Editorial

code1604
coit2016
combinatorics
editorial
letter
medium
permutation
strings

#1

PROBLEM LINK:

Practice

Contest

Author: Ashish Ahuja

Tester: Ashish Ahuja

Editorialist: Ashish Ahuja

DIFFICULTY:

MEDIUM

PREREQUISITES:

String processing, Permutations & Combinations

PROBLEM:

The problem is based on the dictionary position of words formed randomly from the given string of letters.

QUICK EXPLANATION:

The programmer is required to place a letter out of the given letters, at the start of the string, and then find out dictionary position of the first and the last word formed with that letter at the beginning.

EXPLANATION:

Here, the only catch is to find out the dictionary position after successfully placing a letter at the start of the string.
For instance, if 5 random letters are given -

 t z k i o 

Then the solution demands that you place one of the letters at the index ‘0’ of the string. Let us take -
o

Now with, ‘o’ at the start there are 4! ways to place the rest of the letters.

We have to find out the first and the last way of these 4! ways, i.e. the first and the last word formed from these 5 letters with ‘o’ at the beginning of the string.

A small code snippet is as follows -
int fact(int n)
{
    
    if(n==1)
        return(1);
    else
        return(n*fact(n-1));
}

This function is used to find the number of ways to place the letters of the string with the position of the first letter fixed. Then, we use this function to give us the position of the first and the last words in the dictionary, which start and end with the specified letter.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.


#2

if n=26, of course you cannot use integer datatype only to compute 25!. It should use BigInteger.