# MINABS - Editorial

Author: Ram Gopal Pandey
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh

1836

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))

1 Like

Solve it using DP, But I am confused about whether my solution is really correct in all possibilities.

inc[i] denotes the value to convert A_i to B_i
dec[i] denotes the value to convert B_i to A_i

pos[i][j] is true if it is possible to get score of j-26, if we convert A[0..i-1] to B[0..i-1].
Only considered score values -26 to 26 .

Though I am not sure why it worked, it might be wrong ? Here is why I am confused on why this works :

• To find pos[i][j], I check pos[i-1][j] for j among (j - inc[i],j+dec[i]) , but only if the corresponding score was in range [-26,26] .
• But the required score in the middle of DP could go well beyond this range .
(I mean the optimal solution may depend on some pos[i][j] values in which score = j-26 could be >26 or <-26)
• And I am not calculating those subproblems, so maybe this code will fail in some cases.
1 Like

In editorial it’s written : The answer is thus simply the minimum of (Smod26) and ((-S) mod 26)

But in code’s it’s slight different can anyone explain why it like this

ans = (ans % 26 + 26) % 26;
cout << min(ans, abs(26 - ans)) << "\n";

I solved this question using a different approach.
If we observe we can see that there are only two possibilities.
Either we convert (a[i] to b[i]) or (b[i] to a[i]) if we took only these two possibilities the answer is quite simple.
Just take the score which will give less absolute value after adding or subtracting.

Greedy solution also works

#include <bits/stdc++.h>
#define int long long int

void solve(){
int n;
std::cin >> n;
std::string s1, s2;
std::cin >> s1 >> s2;
std::vector <int> v1(n), v2(n);

for(int i=0; i<n; i++){
v1[i] = ((s2[i]-s1[i])+26)%26;
v2[i] = ((s1[i]-s2[i])+26)%26;
}

int score = 0;
for(int i=0; i<n; i++){
int a = score + v1[i];
int b = score - v2[i];
if(std::abs(a) < std::abs(b)){
score = a;
}
else{
score = b;
}
}

std::cout << std::abs(score) << "\n";
}

signed main() {

std::ios::sync_with_stdio(false);
std::cin.tie(0);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

int t = 1;
std::cin >> t;
while(t--){
solve();
}
}


I guess this will not happen, there will always be a way to have answer between (-26, 26), so it won’t go out of bound

it’s rating should be around 1300-1400. It can be easily solved by greedy approach.
check my solution
https://www.codechef.com/viewsolution/79042648

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define f(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define pb push_back

using namespace std;

void test(){
int n;
cin>>n;

string a,b;
cin>>a>>b;

int ans=0;
for(int i=0; i<n; i++){
int ai = a[i]-96, bi = b[i]-96, x,y;

if(bi>=ai)x=bi-ai, y=-(26-(bi-ai));
else x=26-(ai-bi), y=-(ai-bi);

if(abs(ans+x)<=abs(ans+y))ans+=x;
else ans+=y;

}

cout<<abs(ans)<<"\n";


}

int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests=1;
cin>>tests;
while(tests–){
test();
}
}

I solved it using backtracking and stored the ‘best’ value at each position.

Here is my solution: CodeChef

Editorial answer was in perspective of python , where In Python Inbuilt handle with mode operator .
But to get negative modulus correct we apply this formula : ( ( ans % n ) + n ) % n.
By adding + n to answer & then finding it modulo will have no effect in positive , but this will make sense for dealing with negative number .

This is important to deal with negative mod in c++

( ( ans % n )  + n ) % n


During contest I was not able to make this condition (26-(bi-ai)) , Thank u bro for your solution . It is more better than editorial one’s.

Thanksss