CHODE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vitalij Kozhukhivskij
Tester: Mahbub
Editorialist: Jingbo Shang

DIFFICULTY:

Cakewalk

PREREQUISITES:

Programming Language

PROBLEM:

Given a simple encryption method using the frequency, decrypt n strings.

EXPLANATION:

To solve this problem, the key is to get the mapping. That is:

  1. Get the frequency of each character
    in the input string (bins are used
    here);
  2. Sort them in order;
  3. Find the mapping;
  4. Decrypt it.

The time complexity is O(L), where L is the total length of the input strings.

AUTHOR’S AND TESTER’S SOLUTIONS:

Solutions to be uploaded soon

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

1 Like

(if some of them appear equal number of times, then first in frequency sequence will be lower letter between them).

Dear Author ,

How can one understand this as that they have to give priority based on alphabetical order.

Some one commented that we have to consider aphabetical ordering incase two letters have same frequency. if the comment was not made i would have wasted my time on debugging my code for the whole contest.

Bad description of a question

5 Likes

similar logiC but TLE each time in java
please see my submission : http://www.codechef.com/viewsolution/3088704

I submitted this with frequency hash, Bubble sort, and mapping of the frequency for each character (considering A and a same) got Wa.

http://www.codechef.com/viewsolution/4849923

please can anyone tell me the error in this code

i have tested all the cases found uptill now still WA

very true…same happened with me…really poor description!!!

quite right…this problem cost me 8 WAs…worst problem statement ever read on codechef

only after reading your answer i understood the question…

You are right, it was confusing whether to give priority to lexicographic order or the frequency order for decoding.