# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Ram Gopal Pandey

*Takuki Kurokawa, Utkarsh Gupta*

**Testers:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

1836

# PREREQUISITES:

None

# PROBLEM:

You have two strings A and B. You’d like to make them equal.

You can either right-rotate A_i to reach B_i for positive cost, or right-rotate B_i to reach A_i, for negative cost.

Find the minimum **absolute** cost possible.

# EXPLANATION:

Let’s first convert every A_i to B_i using right rotations. At the i-th index, this has a cost of:

- B_i - A_i, if A_i \leq B_i
- B_i - A_i + 26, if A_i \gt B_i.

Let this cost for index i be C_i, and S = \sum_{i=1}^N C_i be our initial cost.

Now, we want to use the B_i \to A_i right rotation at some indices instead to make the absolute value of S as low as possible.

Let’s see how this changes S:

- First, we must subtract C_i from S, since we aren’t using the A_i \to B_i rotation anymore.
- Then, we add the cost of the B_i \to A_i rotation to S. Note that this is exactly -(26 - C_i) (you can derive this from the definition of C_i given above).

So, our change is S \to S - C_i - (26 - C_i) = S - 26.

This means it doesn’t matter which index we choose, the score is only going to decrease by 26.

So, the possible scores we can obtain are \{S, S - 26, S - 2\cdot 26, S - 3\cdot 26, \ldots, S - N\cdot 26\}. The answer is thus the minimum absolute value among all these N+1 values, which can easily be found in \mathcal{O}(N).

Note that there is an even simpler implementation: since we can only subtract 26, the value of S can always be brought into the range [-26, 26].

The answer is thus simply the minimum of (S\bmod 26) and ((-S) \bmod 26).

For example, if S = 100, the answer is the minimum of (100\bmod 26) = 22 and (-100 \bmod 26) = 4, which is 4.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

## Setter's code (C++)

```
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
typedef set<string> ss;
typedef vector<int> vs;
typedef map<int, char> msi;
typedef pair<int, int> pa;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
string a, b;
cin >> a >> b;
int ans = 0;
for (int i = 0; i < n; i++)
ans += b[i] - a[i];
ans = (ans % 26 + 26) % 26;
cout << min(ans, abs(26 - ans)) << "\n";
}
return 0;
}
```

## Editorialist's code (Python)

```
for _ in range(int(input())):
n, a, b = int(input()), input(), input()
ans = 0
for i in range(n):
ans += ord(a[i]) - ord(b[i]) + 26
print(min(ans%26, (-ans)%26))
```