WA for Two Tasks in ZCO12001

I am getting a WA on Task 6 and Task 15 for ZCO12001 (Matched Brackets) whereas I have an AC in all other 13 task. Here is my code:-

#include <bits/stdc++.h>
using namespace std;

bool sortbysecdesc(const pair<int,int> &a,
                   const pair<int,int> &b)
{
        return a.second > b.second;
}

int main()
{
    int n;
    cin >> n;

    vector <int> seq;

    int temp;
    for(int i = 0; i < n; i++)
        {
            cin >> temp;
            seq.push_back(temp);
        }

    vector < pair <int,int> > depths;
    vector < pair <int,int> > symbols;

    int i = 0;
    int dpos, pos, j, c, s, d;
    while(i < n)
    {
        c = 0;
        s = 0;
        pos = i;
        while(seq[i] == 1)
        {
            c++;
            s++;
            i++;
        }
        d = c;
        dpos = i-1;
        j = i;
        while(c != 0)
        {
            if(c > d)
            {
                d = c;
                dpos = j-1;
            }
            if(seq[j] == 2)
            {
                s++;
                c--;
            }
            else
            {
                s++;
                c++;
            }
            j++;
        }
        depths.push_back(make_pair(dpos+1, d));
        symbols.push_back(make_pair(pos+1, s));

        i = j;
    }

    sort(depths.begin(), depths.end(), sortbysecdesc);
    sort(symbols.begin(), symbols.end(), sortbysecdesc);

    cout << depths[0].second << " " << depths[0].first << " " << symbols[0].second << " " << symbols[0].first << "\n";

    return 0;
}

Please suggest any corrections so that I can get an AC on those two tasks as well.

That’s interesting.
Here’s my code that works for only test case 6 and 15!

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
   
    int n,a,m,g,mi,gi,in,cg;
    cin>>n;
    stack<int> arr;
    m=0;g=0;in=0;cg=0;
    for (int i=0;i<n;i++){
        cg++;

        if (arr.empty()){
            if (cg-1>g){g=cg-1;gi=in;}
            cg=1;
            in=i+1;
        }

        if (arr.size()>m){m=arr.size();mi=in+m-1;}

        cin>>a;

        if(a==1)arr.push(1);
        else arr.pop();
    }

    cout<<m<<' '<<mi<<' '<<g<<' '<<gi;
    return 0;

}

you cant see solutions from that contest :frowning:

1 Like

Oh wait, I forgot that ZCOPRAC is a contest.
Why dont they enable viewing other’s solution for ZCOPRAC, INOIPRAC and IARCSJUD? That would be really helpful.

It is always like that
Nowadays we are not able to see
@admin

Can anyone please figure out where am I going wrong after trying so hard for so many hours?

So far, this is the smallest testcase I can find where your program gives the wrong answer:

66
1 1 2 2 1 1 2 2 1 2 1 2 1 1 2 2 1 1 2 2 1 1 1 2 2 1 2 1 2 2 1 1 2 1 2 2 1 2 1 1 1 2 1 2 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 2

Edit:

Since this is an unusually subtle one, I’ll give you a hint: the error is in sortbysecdesc. There’s something you’re forgetting to do. The result might vary according to which version of gcc you use.

2 Likes

Sorry @ssjgz for being rude to you. Can you please explain how can I correct my program logic?

1 Like

See my Edit above :slight_smile:

2 Likes

Thanks @ssjgz ! Thanks a lot !!!

1 Like

:smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley: :smiley:
You are Great !!!

Can you please tell me what is wrong in the function?
I don’t see it.

You’re supposed to print the earliest occurrence of the largest nesting depth/ largest gap between matched brackets, but there’s nothing in his comparator that ensures this.

Interestingly, despite the fact that the contents of depths and symbols are ordered by position before the call to std::sort, it seems that this ordering is destroyed by the call to sort in some circumstances, because std::sort is not stable.

The effect of this is that, in some unusual circumstances, callling sort will order by decreasing nesting depth/ gap between matches (as expected), but, amongst entries with the same nesting depth/ gap, the original ordering in terms of position is lost.

There are two ways to fix this: either fix up the sortbysecdesc, or, I would speculate, to use std::stable_sort instead of sort.

As I said: unusually subtle, and I had to resort to generating loads of random testcases to find one that broke it - trying to contrive a situation that showed the instability of std::sort wasn’t getting me anywhere (and might not expose the error across different versions of gcc’s standard library) :slight_smile:

5 Likes

Since the solutions aren’t public, I’ll just post mine here:

// Simon St James (ssjgz) - 2020-03-09
// 
// Solution to: https://www.codechef.com/ZCOPRAC/problems/ZCO12001/
//
#include <iostream>
#include <vector>

#include <cassert>

using namespace std;

template <typename T>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}

int main()
{
    ios::sync_with_stdio(false);

    const auto N = read<int>();
    vector<int> brackets(N);
    for (auto i = 0; i < N; i++)
        cin >> brackets[i];
    
    vector<int> positionsOfUnmatchedOpenBrackets;
    auto nestingDepth = 0;
    auto largestNestingDepth = -1;
    auto largestNestingDepthPos = -1;
    auto largestDistBetweenMatchedBrackets = -1;
    auto largestDistBetweenMatchedBracketsPos = -1;
    for (auto pos = 0; pos < N; pos++)
    {
        if (brackets[pos] == 1) // Open bracket.
        {
            nestingDepth++;
            positionsOfUnmatchedOpenBrackets.push_back(pos);
            if (nestingDepth > largestNestingDepth)
            {
                largestNestingDepth = nestingDepth;
                largestNestingDepthPos = pos;
            }
        }
        else // Close bracket.
        {
            const auto distBetweenMatchedBrackets = pos - positionsOfUnmatchedOpenBrackets.back() + 1;
            if (distBetweenMatchedBrackets > largestDistBetweenMatchedBrackets)
            {
                largestDistBetweenMatchedBrackets = distBetweenMatchedBrackets;
                largestDistBetweenMatchedBracketsPos = positionsOfUnmatchedOpenBrackets.back();
            }
            positionsOfUnmatchedOpenBrackets.pop_back();
            nestingDepth--;
            assert(nestingDepth >= 0);
        }
    }

    cout << largestNestingDepth << " " << (largestNestingDepthPos + 1) << " " << largestDistBetweenMatchedBrackets << " " << (largestDistBetweenMatchedBracketsPos + 1) << endl;

    assert(cin);
}
2 Likes

ok. It is a open contest like google hashcode extended round. so I think it doesn’t matter.

1 Like

Many days ago it was visible
This has happened multiple times
@admin