Can anybody tell me how to approach this type of question asked in coding contest

1

Annotation 2020-09-12 222552
Annotation 2020-09-12 222552545×753 74.3 KB

2 Likes
2

may be you can try maintaining three vectors for c,a,t respectively, for storing indexes of their occurrences (occurring in order only) and then applying some logic

ps: share the link of the problem

1 Like
3
1 Like
4

thanku very much harjot

1 Like
5

Can anybody explain the given Setter’s code or atleast add suitable comments in this code:

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+5;

int dp[N][3];

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    memset(dp, 0, sizeof(dp));
    if (s[0] == 'c')
    {
        dp[0][0] = 1;
    }
    for (int i = 1; i < n; i++)
    {
        if (s[i] == 'c')
        {
            dp[i][0] = dp[i - 1][0] + 1;
        }
        else
        {
            dp[i][0] = dp[i - 1][0];
        }
        if (s[i] == 'a')
        {
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1] + 1);
        }
        else
        {
            dp[i][1] = dp[i - 1][1];
        }
        if (s[i] == 't')
        {
            dp[i][2] = min(dp[i - 1][1], dp[i - 1][2] + 1);
        }
        else
        {
            dp[i][2] = dp[i - 1][2];
        }
    }
    int p = 2;
    string ans;
    for (int i = n - 1; i >= 0; i--)
    {
        if (i == 0)
        {
            if (p || !dp[0][0])
            {
                ans += s[i];
            }
        }
        else
        {
            if (p == 2 && s[i] == 't')
            {
                if (dp[i - 1][1] <= dp[i - 1][2] + 1)
                {
                    ans += s[i];
                    p--;
                }
            }
            else if (p == 1 && s[i] == 'a')
            {
                if (dp[i - 1][0] <= dp[i - 1][1] + 1)
                {
                    ans += s[i];
                    p--;
                }
            }
            else if (p == 0 && s[i] == 'c')
            {
                continue;
            }
            else
                ans += s[i];
        }
    }
    reverse(ans.begin(), ans.end());
    
    cout << ans.size() << "\n";
    cout << ans;
    
    return 0;
}