GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday 2 November 2022

[Solution] Minimum Absolute Score CodeChef Solution



Problem

You are given two strings A and B of length N consisting of lowercase English letters. Your objective is to make both the strings equal.

You can apply one of the following 2 operations at each index i:

  • Convert char A_i to B_i by doing right cyclic shift of character A_i. This increases your score by amount equal to cyclic shifts done.
  • Convert char B_i to A_i by doing right cyclic shift of character B_i. This decreases your score by amount equal to cyclic shifts done.

Your starting score is zero.
If the operations are applied optimally, find the minimum absolute score possible after making both the strings equal.

Note: A single right cyclic shift converts one character to the next in alphabetical order, except for z which goes to a. That is, the sequence looks like

a \to b \to c \to \ldots \to y \to z \to a \to b \to \ldots

So, for example converting a to e requires 4 right cyclic shifts, and converting k to i requires 24.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of three lines of input.
    • The first line of each test case contains one integer N — the length of strings A and B.
    • The second line contains string A.
    • The third line contains string B.

Output Format

For each test case, output on a new line the minimum absolute score possible after making both the strings equal.


Explanation:

Test case 1: The minimum absolute score can be obtained as follows:

  • Apply operation 1 at position 1, converting a to b for a cost of +1.
  • Apply operation 2 at position 2, converting a to b for a cost of -1.
  • Apply operation 2 at position 3, converting z to b for a cost of -2.

The score is then 1 -1 -2 = -2, with absolute value 2. This is the lowest possible absolute value attainable.

Test case 2: Apply operations as follows:

  • Operation 1 at index 1z\to a for a cost of +1
  • Operation 1 at index 2z\to a for a cost of +1
  • Operation 2 at index 3a\to c for a cost of -2

This gives us a final score of 1 + 1 - 2 = 0, which has absolute value 0. It is not possible to do better than this.

No comments:

Post a Comment