 # 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.second << " " << depths.first << " " << symbols.second << " " << symbols.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 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

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 2 Likes

Thanks @ssjgz ! Thanks a lot !!!

1 Like          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) 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>
{
assert(cin);
}

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