PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Ram Gopal Pandey
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh
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))