MINABS - Editorial

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

Accepted Code link

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.
Solution link- Solution

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++ :blush:

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