COEX03-Editorial

editorial
, ,
1

Problem links:
Contest
Practice

Difficulty:
Medium

Problem:
Each character in string(given as input) has to be replaced with character that lies (n­-1) position behind the character in the string if we consider their alphabetical order (assume that after ‘z’ ‘a’,‘b’,‘c’ and so on appears). And to minimize the cost of replacement the character with maximum frequency should be replaced first, since all similar characters can be replaced in single pass and replacement cost per character increases by one in each pass.

Explanation:
Step 1: First of all you need to find the character with maximum frequency.For string s,store the frequency of each character in string in the array cnt.

for(j=0;j&ltlength;j++)  
    cnt[int(s[j])]++;

Calculate the maximum value from array cnt. Index of this maximum value will be the ASCII value of
character with the maximum frequency.
Step 2: Now you have to calculate cost of replacement for this pass and add it to total­cost.
total­cost=total­cost+pass*(maximum frequency value)
pass=pass+1
Step 3: Now you have to find the replacement for each character to get the decoded string. ASCII values of characters can be used to represent the character’s position.
For small case letters ASCII value range from 97 to 122.
So replacement for any character will be character whose ASCII value is (ASCII value of actual character – (n­-1)).
But there is a corner case before ‘a’, ‘z’ is supposed to appear. So if the above computation gives ASCII value that is less than 97(means it is out of the range of character’s ASCII value) so we need to add 26 to it, so that it can get into the range of character’s ASCII values)



temp=(int(s[j]))­(n­-1)

if(temp<97)

temp=temp+26

s[j]=char(temp);

Solution:
Author’s solution can be found here.
Tester’s solution can be found here.