Kickstart 2020 Round B Problem C MLE in Test case 2

help
1

Problem C

#include <bits/stdc++.h>

using namespace std;

string extract(string s)
{   
    int epos = -1, spos = -1;
    for (int i = (s.size()-1); i >= 0; --i)
    {
        if (s[i] == ')')
            epos = i;     
    }
    if (epos == -1)
        return(s);
    for (int i = epos; i >= 0; --i)
    {
        if (s[i] == '(')
        {
            spos = i;    
            break;
        }
    }
    string sub = s.substr(spos+1, epos-spos-1);
    s.replace(spos, epos-spos+1, sub);
    for (int i = 1; i < int(s[spos-1])-48; ++i)
        s.insert(spos, sub);
    s.erase(spos-1, 1);
    if (epos == -1)
        return s;
    else
        return extract(s);   
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    for (int x = 1; x <= t; ++x)
    {
        string comms;
        cin >> comms;
        comms = extract(comms);
        long long vpos = 0, hpos = 0;
        int nc = 0, sc = 0, wc = 0, ec = 0;
        for (int y = 0; y < comms.size(); ++y)
        {
            if (comms[y] == 'N')
                ++nc;
            else if (comms[y] == 'S')
                ++sc;
            else if (comms[y] == 'E')
                ++ec;
            else if (comms[y] == 'W')
                ++wc;
        }
        if (nc > sc)
            vpos = (1000000000-(nc-sc-1));
        else if (sc >= nc)
            vpos = (1+sc-nc);
        if (wc > ec)
            hpos = (1000000000-(wc-ec-1));
        else if (ec >= ec)
            hpos = (1+ec-wc);
       cout << "Case #" << x << ": " << hpos << " " << vpos << '\n';
    }
}

In extract(), I check if there are any brackets. And I handle them one at a time recursively. If there are none, I return the string.
The main function is just some basic if-else with the extracted string.
I’m getting MLE for test case 2. What should I do to fix this?

2

Converting the string to raw commands is making the string too long. in Subtask 1 there’s a constraint that limits total moves to 1e4 but no such constraint in Subtask 2 so the resultant string will probably be a lot larger than 1e4 characters.

I tried making some optimizations without changing the basic logic but it’s still giving MLE.

#include <bits/stdc++.h>

using namespace std;
void extract(string &s)
{
    string sub;
    int epos = -1, spos = -1;
    while(true){
        for (int i = 0; i <= (s.size()-1); ++i)
        {
            if (s[i] == ')'){
                epos = i;
                break;
            }
        }
        if (epos == -1)
            return;
        for (int i = epos; i >= 0; --i)
        {
            if (s[i] == '(')
            {
                spos = i;
                break;
            }
        }
        sub = s.substr(spos+1, epos-spos-1);
        s.replace(spos, epos-spos+1, sub);
        for (int i = 1; i < int(s[spos-1])-48; ++i)
            s.insert(spos, sub);
        s.erase(spos-1, 1);
        if (epos == -1)
            return;
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    for (int x = 1; x <= t; ++x)
    {
        string comms;
        cin >> comms;
        extract(comms);
        long long vpos = 0, hpos = 0;
        int nc = 0, sc = 0, wc = 0, ec = 0;
        for (int y = 0; y < comms.size(); ++y)
        {
            if (comms[y] == 'N')
                ++nc;
            else if (comms[y] == 'S')
                ++sc;
            else if (comms[y] == 'E')
                ++ec;
            else if (comms[y] == 'W')
                ++wc;
        }
        if (nc > sc)
            vpos = (1000000000-(nc-sc-1));
        else if (sc >= nc)
            vpos = (1+sc-nc);
        if (wc > ec)
            hpos = (1000000000-(wc-ec-1));
        else if (ec >= ec)
            hpos = (1+ec-wc);
       cout << "Case #" << x << ": " << hpos << " " << vpos << '\n';
    }
}
1 Like
3

Thanks. I guess I need to change the approach. In extract(), instead of replacing the string, maybe I can update nc, sc, ec and wc after declaring them as global variables. That should work, right?

4

subcommands can be nested so be wary of that.

1 Like