K3AU03 - Editorial

editorial
1

PROBLEM LINK:

Cost Maximization

DIFFICULTY:

EASY - MEDIUM

PREREQUISITES:

Stacks or techniques to preserve previous array elements, Greedy

EXPLANATION:

The idea is fairly simple and intuitive. This problem can be solved using the Greedy Approach. The idea here is to first remove all the 01 substrings if their cost is greater else remove 10. There are multiple ways to solve this problem but we will use the approach with stack because it covers many similar and most frequently asked problems in interviews.

So, to do this we first initialize a string t with the substring having maximum cost.

t_{0} → first character of max cost substring
t_{1} → second charater of max cost substring

Now, we start traversing the string and check if t_{1} matches with the current character of the string, and if the stack is not empty and contains t_{0} at the top, then we simply pop the top element and add the max cost to our answer else we push the current character into the stack.

After processing all substrings of the max cost we will be left with the string of form 111...000..., 000..111... or nothing if the stack is empty.

Now if the stack is not empty then we will retrieve the remaining string from the stack.

Procedure to retrieve the remaining string:

  • We add the top character of the stack to an empty string until the stack is not empty.
  • The retrieved string will be reverse of the original string so we will perform the reverse operation to get the required string.

Now, using almost the same procedure as above, we again traverse the obtained string and look for substrings 01 and 10 and add their cost to the final answer.

Now, let’s trace this with an example:

9 3 1

100110110

Here, c_{0} is greater than c_{1} so, t will be assigned 01
t_{0} = ‘0’ and t_{1} = ‘1’
Now, stack at each iteration will look like,

1
10
100
10

At this step current element is equal to t_{1} and the top element of the stack is t_{0}
so, we add max cost 3 to the answer and pop the top element from the stack.

1

At this step same thing happens and the answer becomes 6.

10
1

At this step same thing happens again and the answer becomes 9.

11
110

All maximum cost substrings have been removed and we are left with the remaining string.
To obtain the remaining string we start popping characters from the stack and add them to a string, the string will be 011 ( as 0 is the top character of the stack so the string will be obtained in reverse order )
So, we reverse the string to obtain the required string 110.

Now, we will process this string using the stack again to check for substrings of type 10.
So, now our final answer becomes 10.

Checkout the work function:

SOLUTIONS:

Solution 
// Disclaimer: Don't copy my template, it may lead to plagiarism.
/* Author: Soumy Jain
   Handle: soumy_jain || soumyjain
   "Beautiful flowers too, eventually wither and fall. That's the fate of all living beings."
   "I hate perfection. To be perfect is to be unable to improve any further." - Mayuri Kurotsuchi | Bleach
   "I smile to show the pressure of heroes and to trick the fear inside of me."
   "Gravel may be gravel, but me? I'm the gravel that shatters diamonds."
   "If you were to write a story with me in the lead role, it would certainly be...a TRAGEDY." - Kaneki Ken | Tokyo
   Ghoul
*/
/******************************************************************************/
// clang-format off
#include <bits/stdc++.h>
#define ll        long long
#define ull       unsigned long long
#define SPEEDHACK ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff        first
#define ss        second
#define sz(v)     (ll)(v).size()
#define file      freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define MOD       1000000007      // 998244353
using namespace std;
/******************************************************************************/
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(ll x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(ull x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template<typename T, typename V>
void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}'; }
template<typename T>
void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}"; }
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
// clang-format on

/***********************************MAIN***************************************/
// Are you ready to face the wrath of test cases? Good luck Soumy!

void work()
{
    ll n, c0, c1, ans = 0;
    cin >> n >> c0 >> c1;
    string s;
    cin >> s;
    stack<char> st;
    string t = (c0 > c1) ? "01" : "10";
    for (int i = 0; i < n; i++)
    {
        if (t[1] == s[i] && sz(st) && st.top() == t[0])
        {
            st.pop();
            ans += max(c0, c1);
        }
        else
            st.push(s[i]);
    }
    s = "";
    while (sz(st))
    {
        s += st.top();
        st.pop();
    }
    reverse(s.begin(), s.end());
    for (int i = 0; i < sz(s); i++)
    {
        if (sz(st) && st.top() == '1' && s[i] == '0')
            ans += c1, st.pop();
        else if (sz(st) && st.top() == '0' && s[i] == '1')
            ans += c0, st.pop();
        else
            st.push(s[i]);
    }
    cout << ans;
}

int main()
{
    SPEEDHACK
    // file
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        work();
    }
    return 0;
}
1 Like