ROTMIN - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: kugo
Tester: yash_daga
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Greedy algorithms, binary search

PROBLEM:

You’re given a string S. In one move, you can pick and index i and replace S_i with either S_i + 1 (upwards move) or S_i - 1 (downwards move), where the values are cyclic from \texttt{a} to \texttt{z}.

You can perform at most P upwards moves and at most Q downwards moves.
What’s the lexicographically smallest string you can obtain?

EXPLANATION:

Since our objective is lexicographic minimization, the obvious choice is to try and make the first character \texttt{a}, then make the second character \texttt{a}, and so on.

Let’s try to find the largest prefix of S that can be turned into \texttt{a}'s.

Suppose we want to check whether the first k characters of S can be turned into \texttt{a}.
First, compute the values up_i and down_i for each 1 \leq i \leq k, where up_i is the number of upward moves required to turn S_i into \texttt{a}, and down_i is defined similarly.

Now, we want to choose up_i for some indices and down_i for the rest, such that the sum of chosen up_i is at most P, and the sum of chosen down_i for the rest is at most Q.

This can be done greedily!
That is, sort the pairs (up_i, down_i) in ascending order of up_i value. Then, greedily keep taking the smallest up_i values as long as you don’t exceed P, after which you take the down_i values for everything else.
Finally, check if the sum of taken down_i values is \leq Q.

Proof of correctness

The key to why this works is the fact that up_i and down_i are complementary.
That is, up_i + down_i = 26 (unless S_i = \texttt{a}, in which case up_i = down_i = 0 and we can just ignore this index).

This means that smaller values of up_i correspond to larger values of down_i, and vice versa.
So, if we sort the pairs and have up_1 \leq up_2 \leq \ldots \leq up_k, that also means we’ll have down_1 \geq down_2 \geq \ldots \geq down_k.

Intuitively this already makes it obvious why taking a prefix of the up_i values is good, since it’ll make us take a suffix of the down_i values which is the best we can do there too.

It’s also possible to prove this algebraically, using an exchange argument.
Suppose we choose up_x, but don’t choose up_y where y \lt x (in sorted order); meaning we chose down_y.

Suppose we replaced up_x with down_x and down_y with up_y.
Then, since up_x \geq down_x and down_y \geq up_y, this reduces (or rather, doesn’t increase) both the sum of up_i values and the sum of down_i values, which is obviously good.
Repeating this replacement operation makes us end up with a prefix of up values and a suffix of down values, as claimed.

So, we can now check whether the first k characters can be all turned into \texttt{a}, in \mathcal{O}(k\log k) time. It’s possible to implement this in \mathcal{O}(k + 26) time, but unnecessary to get AC.
Our aim is to find the maximum such k.

Notice that if the first k characters can be turned into \texttt{a}, so can the first k-1 characters.
So, we can use binary search!
This allows us to find the largest valid k in \mathcal{O}(N\log ^2 N) time.

In addition, note that our method also tells us how many moves are remaining of each type, since it minimizes both the number of upward and downward moves.
We need to use these remaining moves to deal with the positions from k+1 onwards.

First, we know that S_{k+1} cannot be made into \texttt{a}, so the best we can do is to perform downward moves on it as much as possible. This uses up all our downward moves.

Finally, for each index i from k+2 to N, check whether S_i can be turned into \texttt{a} using the remaining upward moves; and if it can, do so.

It is also possible to implement this without binary search, by maintaining a set/priority queue of lowest up_i values and removing the largest of them whenever the sum exceeds P.

In fact, it’s even possible to implement this solution in \mathcal{O}(N); doing so is left as a challenge to the reader :smile:

TIME COMPLEXITY

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

CODE:

Setter's code (C++)
#include "bits/stdc++.h"
using namespace std;
 
typedef long long           lol;
typedef std::pair<int,int>  pii;
#define pb                  push_back
#define ub                  upper_bound
#define lb                  lower_bound
#define fo(i,l,r,d)         for (auto i=(l); (d)<0?i>(r):((d)>0?i<(r):0); i+=(d))
#define all(x)              x.begin(), x.end()
#define ff                  first
#define ss                  second
 
std::mt19937 rng (std::chrono::high_resolution_clock::now().time_since_epoch().count());
template <typename A, typename B> std::ostream& operator<< (std::ostream &cout, const std::pair<A, B> &p) { return cout << p.first << ' ' << p.second; } template <typename A, size_t n> std::ostream& operator<< (std::ostream &cout, const std::array<A, n> &v) { for (int i = 0; i < n - 1; ++i) cout << v[i] << ' '; return (n ? cout << v.back(): cout << '\n'); } template <typename A> std::ostream& operator<< (std::ostream &cout, const std::vector<A> &v) { for (int i = 0; i < v.size() - 1; ++i) cout << v[i] << ' '; return (v.size() ? cout << v.back(): cout << '\n'); }
template <typename A, typename B> std::istream& operator>> (std::istream &cin, std::pair<A, B> &p) { cin >> p.first; return cin >> p.second; } template <typename A, size_t n> std::istream& operator>> (std::istream &cin, std::array<A, n> &v) { assert(n); for (int i = 0; i < n - 1; i++) cin >> v[i]; return cin >> v.back(); } template <typename A> std::istream& operator>> (std::istream &cin, std::vector<A> &v) { assert(v.size()); for (int i = 0; i < v.size() - 1; i++) cin >> v[i]; return cin >> v.back(); }
template <typename A, typename B> auto amax (A &a, const B b){ if (b > a) a = b ; return a; }
template <typename A, typename B> auto amin (A &a, const B b){ if (b < a) a = b ; return a; }
 
 
 
void darling (const int kase) {
 
    int n, p, q; string a;
    cin >> n >> p >> q >> a;
 
    int l = 0, r = n + 1;
 
    while (l < r - 1) {
    	int m = (l + r) / 2;
    	
		vector<pii> op;
 
		for (int i = 0; i < m; i++)
			op.pb(pii(('z' - a[i]) + 1, a[i] - 'a'));
 
		sort(all(op));
 
		int suf_dn = 0, pre_up = 0;
		for (auto [up, dn]: op)
			suf_dn += dn;
 
		int pbl = (suf_dn <= q);
		for (auto [up, dn]: op)
			pre_up += up, suf_dn -= dn,
			pbl |= (pre_up <= p and suf_dn <= q);
 
    	if (pbl) l = m;
    	else r = m;
    }
 
    if (l == n)
    	return void(cout << string(n, 'a') << '\n');
 
 
    vector<pii> op;
 
	for (int i = 0; i < l; i++)
		op.pb(pii(('z' - a[i]) + 1, a[i] - 'a'));
 
	sort(all(op));
 
	int suf_dn = 0, pre_up = 0;
	for (auto [up, dn]: op)
		suf_dn += dn;
 
	int max_dn_left = (suf_dn <= q ? q - suf_dn: 0);
	int up_left = (suf_dn <= q ? p: 0);
 
	for (auto [up, dn]: op) {
		pre_up += up, suf_dn -= dn;
		if (pre_up <= p and suf_dn <= q)
			max_dn_left = q - suf_dn,
			up_left = p - pre_up;
	}
 
	fo(i,0,l,1)
		a[i] = 'a';
 
	a[l] -= max_dn_left;

	fo(i,l+1,n,1)
		if (a[i] + up_left > 'z')
			up_left -= 'z' - a[i] + 1,
			a[i] = 'a';
 
	cout << a << '\n';
 
}

int main () {
    ios_base::sync_with_stdio(0), cin.tie(0);
 
    int t; cin >> t, assert(t >= 0);
    for (int i = 0; t--; )
        darling(++i);
 
}
Tester's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow   
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14  
//Check ans for n=1 
// #pragma GCC target ("avx2")    
// #pragma GCC optimize ("O3")  
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>                   
#include <ext/pb_ds/assoc_container.hpp>  
#define int long long     
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back 
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int> 
#define pii pair<int, int>
#define ll long long 
#define ff first
#define ss second 
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)    
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=200005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
    int g=__gcd(a, b);
    return a/g*b;
}
int power(int a, int b, int p)
    {
        if(a==0)
        return 0;
        int res=1;
        a%=p;
        while(b>0)
        {
            if(b&1)
            res=(1ll*res*a)%p;
            b>>=1;
            a=(1ll*a*a)%p;
        }
        return res;
    }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}

int32_t main()
{
    IOS;
    int t;
    cin>>t;
    while(t--)
    {
        int n, p, q;
        cin>>n>>q>>p;
        string s;
        cin>>s;
        assert(n == (int)s.size());
        // n=s.size();
        int lb=1, ub=n, all_a=0, p1=p, q1=q;
        while(lb<=ub)
        {
            int md=(lb+ub)/2;
            int up[26], tot_down=0, tot_up=0;
            fill(up, 0);
            rep(i,0,md)
            {
                up[(s[i]-'a')]++;
                tot_down+=(26 - (s[i]-'a'))%26;
            }
            if(tot_down <= q)
            {
                all_a=md;
                lb=md+1;
                p1=p;
                q1=q-tot_down;
            }
            rep(i,0,25)
            {
                rep(j,0,up[i])
                {
                    tot_up+=i;
                    tot_down-=(26-i)%26;
                    if(tot_up <= p && tot_down <= q)
                    {
                        all_a=md;
                        lb=md+1;
                        p1=p-tot_up;
                        q1=q-tot_down;
                        break;
                    }
                }
                if(all_a==md)
                    break;
            }
            if(all_a!=md)
                ub=md-1;
        }
        // cout<<all_a<<" "<<p1<<" "<<q1<<"\n";
        rep(i,0,all_a)
        s[i]='a';
        rep(i,all_a,n)
        {
            while(s[i]>'a' && p1>0)
                s[i]--, p1--;
            if(s[i]>'a' && (26 - (s[i]-'a'))<=q1)
            {
                q1-=(26 - (s[i]-'a'));
                s[i]='a';
            }
        }
        cout<<s<<"\n";
    }
}
Editorialist's code (Python)
from heapq import heappush, heappop

for _ in range(int(input())):
    n, p, q = map(int, input().split())
    s = input()
    
    upsum, downsum = 0, 0
    pq, ans = [], []
    for i in range(n):
        down = ord(s[i]) - ord('a')
        up = (26 - down)%26
        
        heappush(pq, -up)
        upsum += up
        mx = 0
        if upsum > p:
            mx = -heappop(pq)
            upsum -= mx
            downsum += 26 - mx
        
        if downsum <= q:
            ans.append('a')
            continue
        
        upsum += mx - up
        downsum -= 26 - mx
        
        uprem, downrem = p - upsum, q - downsum
        ans.append(chr(ord(s[i]) - downrem))
        for j in range(i+1, n):
            up = (26 - (ord(s[j]) - ord('a')))%26
            if up <= uprem:
                uprem -= up
                ans.append('a')
            else:
                ans.append(s[j])
        break
    print(*ans, sep = '')
3 Likes

Why does this fail? Can someone please explain? Thanks!

t = int(input())
for i in range(t):
    n, p, q = map(int, input().split(" "))
    s = input()
    r = ""
    for k in s:
        if (k != 'a'):
            if (ord(k) + p > ord('z')):
                r += 'a'
            else:
                if (q > 0):
                    if (ord(k) - ord('a') < q):
                        r += 'a'
                        
                    else:
                        r += chr(ord(k) - q)
                    q -= ord(k) - ord('a')
                else:
                    r += k

        else:
            r += k
    print(r)

my idea to solve this problem was to take make iterate through each character, check if upward or downward move is least expensive and make the least expensive move, then go to the next character. do this for every character till the end of string is reached, or p and q are exhausted. can anyone please explain what’s wrong in my approach?

Why my code is giving Wrong ans

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace chrono;

#pragma GCC target (“avx2”)
#pragma GCC optimization (“O3”)
#pragma GCC optimization (“unroll-loops”)
#pragma GCC optimization (“Ofast”)

#define ordered_set tree<int, null_type,less, rb_tree_tag,tree_order_statistics_node_update>
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL),cout.tie(NULL)
#define PI 3.141592653589793238462
#define MOD 1000000007
#define lli long long int
#define INF 1e18
#define nl ‘\n’
#define pb push_back
#define ppb pop_back
#define f first
#define s second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define py cout << “YES” << nl
#define pn cout << “NO” << nl
#define loop(i,a,b) for (int i = a; i <= b; i++)
#define rloop(i,a,b) for (int i = a; i >= b; i–)
#define tc(t) int t; cin >> t; while (t–)
#define prec(n) fixed<<setprecision(n)
#define ini(a, i) memset(a, i, sizeof(a))

#define us unordered_set
#define um unordered_map
#define ll long long
#define ull unsigned long long
#define maxpq priority_queue
#define pii pair<int, int>
#define minpq priority_queue<int, vector, greater >

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
#else
#define debug(x);
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
void google(int t) {cout << “Case #” << t << ": ";}
template <class T, class V> void _print(pair <T, V> p);
template void _print(vector v);
template void _print(set v);
template <class T, class V> void _print(map <T, V> v);
template void _print(multiset v);
template <class T, class V> void _print(pair <T, V> p) {cerr << “{”; _print(p.f); cerr << “,”; _print(p.s); cerr << “}”;}
template void _print(vector v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(set v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(multiset v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << “]”;}

vector<vector> pre(int N){
vector<vector> divs(N);
loop(i, 1, N-1){
for(int j=i;j<N;j+=i)
divs[j].pb(i);
}
return divs;
}

vector sieve(int n) {intarr = new intn + 1; vector vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll add(ll x, ll y, ll m) {ll res=x+y; return res>=m ? res-m:res;}
ll mul(ll x, ll y, ll m) {ll res=x
y; return res>=m? res%m:res;}
ll sub(ll x, ll y, ll m) {ll res=x-y; return res<0? res+m:res;}
ll power(ll x, ll y, ll m) {ll res=1; x%=m; while(y){ if (y&1) res=mul(res, x, m); y >>=1; x=mul(x, x, m);} return res;}

void solve(){

tc(t){
    ll n,p,q;
    cin>>n>>p>>q;
    string x;
    cin>>x;
    ll ind=0;
    while(ind<n){
        ll num=x[ind]-'a';
        ll num2='z'-x[ind]+1;
        if(num<num2){
            if(q>=num){
                q-=num;
                x[ind]='a';
            }
            else if(p>=num2){
                p-=num2;
                x[ind]='a';
            }
            else{
                num-=q;
                x[ind]=char(num+'a');
                q=0;
            }
        }
        else{
            if(p>=num2){
                p-=num2;
                x[ind]='a';
                
            }
            else if(q>0)
            {
                // num2--;
                num-=q;
                x[ind]=char(num+'a');
                q=0;
            }
                
        }
        ind++;
    }cout<<x<<nl;
}  

}

int main(){
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

#ifndef ONLINE_JUDGE
freopen(“Error.txt”, “w”, stderr);
#endif

fio;
auto start1 = high_resolution_clock::now();
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast(stop1 - start1);

#ifndef ONLINE_JUDGE
cerr << "Time: " << duration . count() / 1000 << endl;
#endif
}

Suppose now, at the same location we can use both upward and downward value to flip.so, we used upward value to flip. Later we find out, that upward value now get exhausted and downward value is not sufficient for that character to make it ‘a’. In other word if we use downward flip in before case, we can use upward flip and make it to ‘a’. Can anyone explain me how to handle it. I thought of dynamic programming but the constraints are too huge

1 Like

That greedy thing was hard to figure out. Nice problem!

One example for the same

String = “acb”, P = 24, Q = 2.
Here is for char ‘c’, we make it 'a; using 2 downward moves. We cannot make char ‘b’ to ‘a’ in 24 upwards moves. So the string is “aab”.

But if used upward move for char ‘c’ to make it ‘a’. We can turn ‘b’ to ‘a’ using 1 downward move and the string will be “aaa”.

1 Like

Editorial should have an explanation of the approaches/concept/algorithm/technique of both the setter’s and the tester’s solutions . Any additional links/reference must be given. You can take the help of the solutions of setter and tester (submitted during the testing phase) to improve your editorials.
regards:Train simulator MOD APK

At present, the sucker rod pumping installations are the most used in the case of the
wells in production, when an eruptive exploitation is not possible.
regards: best camping fan for large tent