I have been getting WA despite checking on many test cases. Please help me.
https://www.codechef.com/viewsolution/31888730
Idea: Whenever I encounter a closing bracket ‘)’ and my stack is not empty then I change the value of flag to 0. This tells me that me that if next I encounter ‘(’ then the depth does not increase. Whenever the stack becomes empty I check for the maximum depth.
ssjgz
April 14, 2020, 9:10pm
2
Your solution gives the wrong answer for the following test input:
66
1 1 2 1 2 1 1 1 1 2 2 2 1 2 2 2 1 1 2 2 1 2 1 2 1 2 1 1 1 2 2 1 2 1 1 2 1 1 2 1 2 1 1 1 1 2 2 1 2 1 2 2 1 1 1 1 1 2 2 2 2 2 2 2 2 2
(The correct answer is 9 57 40 27
).
3 Likes
Thank you. It worked. I wanted to know how can we come up with such test cases?
1 Like
ssjgz
April 15, 2020, 1:42pm
4
Random testcase generator
// Simon St James (ssjgz) - 2020-03-09
//
// Solution to: https://www.codechef.com/ZCOPRAC/problems/ZCO12001/
//
#include <iostream>
#include <vector>
#include <cassert>
#include <sys/time.h> // TODO - this is only for random testcase generation. Remove it when you don't need new random testcases!
using namespace std;
template <typename T>
T read()
{
T toRead;
cin >> toRead;
assert(cin);
return toRead;
}
int main(int argc, char* argv[])
{
ios::sync_with_stdio(false);
if (argc == 2 && string(argv[1]) == "--test")
{
struct timeval time;
gettimeofday(&time,NULL);
srand((time.tv_sec * 1000) + (time.tv_usec / 1000));
const int initialN = 1 + rand() % 75;
vector<int> s;
int nestingDepth = 0;
for (int i = 0; i < initialN; i++)
{
bool openBracket = ((rand() % 2 + 1) == 1);
if (!openBracket && nestingDepth == 0)
{
openBracket = true;
}
if (openBracket)
{
s.push_back(1);
nestingDepth++;
}
else
{
s.push_back(2);
nestingDepth--;
}
}
while (nestingDepth > 0)
{
s.push_back(2);
nestingDepth--;
}
const int N = s.size();
cout << N << endl;
for (int i = 0; i < N; i++)
{
cout << s[i];
if (i != N - 1)
cout << " ";
}
return 0;
}
const int N = read<int>();
string s;
for (int i = 0; i < N; i++)
{
if (read<int>() == 1)
s += '(';
else
s += ')';
}
vector<int> positionsOfUnmatchedOpenBrackets;
int nestingDepth = 0;
int largestNestingDepth = -1;
int largestNestingDepthPos = -1;
int largestDistBetweenMatchedBrackets = -1;
int largestDistBetweenMatchedBracketsPos = -1;
for (int pos = 0; pos < N; pos++)
{
if (s[pos] == '(')
{
nestingDepth++;
positionsOfUnmatchedOpenBrackets.push_back(pos);
if (nestingDepth > largestNestingDepth)
{
largestNestingDepth = nestingDepth;
largestNestingDepthPos = pos;
}
}
else
{
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);
}
3 Likes
itrust
June 23, 2020, 4:12am
6
@ssjgz I did not understood why it is 57th position in test case provided by you . As it is not the position of the first opening bracket rather it is the last one. Is not it? Or am I going wrong somewhere?
The nesting depth, and the first position where it occurs–this will be the position of the first opening bracket at this nesting depth, where the positions are numbered starting with 1.
At the 57th position we obtain the nesting depth of 9 for the first time and hence, the answer is 57.