LEXSTRI - Editorial

PROBLEM LINK:

Practice
Contest

Author: Riddhish Lichade
Tester: Ram Agrawal
Editorialist: Prathamesh Sogale

DIFFICULTY:

MEDIUM

PREREQUISITES:

DP

PROBLEM:

Meena loves cricket very much. So, he went to watch the recent world cup match at the stadium, but for this he missed his exams. After pleading a lot, the teacher agreed to pass him on a condition that he completes a task.

Meena is given N strings consisting of lowercase English letters. He has to sort them in lexicographical order (as in the dictionary), but he is not allowed to swap any of them. The only operation he is allowed to do is to reverse any of them (first character becomes last, second becomes one before last and so on).

To reverse the i−th string Meena has to spend E_i units of energy.

Find the minimum energy required by Meena to complete this task.

EXPLANATION:

We will solve the problem with the help of dynamic programming. dp[i][j] is the minimum amount of energy that should be spent to make first i strings sorted in lexicographical order and i-th of them will be reversed if j=1 and not reversed if j = 0. dp[i][j] is updated by dp[i - 1][0] and dp[i - 1][1]. It remains to verify that the i-th string is lexicographically greater than (i - 1)-th (if j = 1 then we should check reversed i-th string, similar to (i - 1)-th). Then we update dp[i][j] = min(dp[i][j], dp[i - 1][0] + c[i] * j), dp[i][j] = min(dp[i][j], dp[i - 1][1] + j * c[i]). The answer is a minimum of dp[n][0] and dp[n][1].

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const ll INF = 1e18;
ll n,a[100010],dp[100010][2],ans;
string s[100010][2];
int main(int argc, char const *argv[])
{
    int t;
    cin>>t;
    while(t--)
    {
    int n ;
    cin >> n;
    for(ll i=1;i<=n;i++) cin >> a[i];
    for(ll i=1;i<=n;i++){
        cin >> s[i][0];
        s[i][1] = s[i][0];
        reverse(s[i][1].begin(),s[i][1].end());
    }
    dp[1][0] = 0 ;
    dp[1][1] = a[1];
    for(ll i=2;i<=n;i++){
        for(int j=0;j<2;j++){
            dp[i][j] = INF;
            for(int k=0;k<2;k++){
                if(s[i][j] >= s[i-1][k])
                    dp[i][j] = min(dp[i][j],dp[i-1][k]+j*a[i]);
            }
        }
    }
    ans = min(dp[n][0],dp[n][1]);
    cout << (ans==INF ? -1 : ans) << endl;
    }
    return 0;
}