ENP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Jatin Gupta
Tester: Aanya Jindal
Editorialist: Naman Goyal

DIFFICULTY:

EASY

PREQUISITES

Basic knowledge of modulo operator

PROBLEM:

To find the length of longest palindrome that can be made by taking a subset of given string after decrypting it.

QUICK EXPLANATION:

First decrypt the string by applying inverse operation of the given encrypt function. After this, note that we can take even numbers of each character(Put that character at the beginning and end of the current answer string) and also 1 character separately that can be put in the middle.(if it exists)

EXPLANATION:

First step is to decrypt the given string:

Since we are given a pseudocode in which there is statement for encryption given as follow:
encrp+=charof((val(s[i])+x + i*d)%26);//we are given x and d

So, for decryption we have to do opposite of encryption i.e.,
decrp+=charof(value((s[i])-x-i*d)%26);

But here the problem is that id will make the modulo negative so for keeping it positive we have to add 26 to it so that the resultant lies is positive and also lies in the range of alphabets …
So the new statement is :
decrp+=charof(value(((s[i])-x-id)%26+26)%26);//applying modular arithmetic

After decryption, it is now to find the maximum palindromic subset in the string decrypted above.

First of all it is necessary to know that a palindromic string has two parts-

  1. The characters that are double
    Example: abcba
    In this case a and b are these characters.

  2. The characters that are not double
    Example: abcba
    In this case c is that character.

Single character can at maximum occur once while we can have as many as doubles possible.

Since we have to find the subset and then arrange, so order in string does not matter.
Therefore, we will find the frequency of each alphabet in the string.

Now there can be two cases-

  1. When the frequency of particular alphabet is even: all the occurrences of that character can be used.
  2. When the frequency is odd: All but one occurrence can be used.

If we had even count for any character, we can add 1 to the answer

AUTHOR’S AND TESTER’S SOLUTIONS:

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