I am a grade 12 student from Mumbai. I am planning to appear for the Zonal Computing Olympiad this Saturday which is for school students. I am facing a problem regarding a particular question from ZCO 2012. There is a test page where users can submit the solution and receive the results. I have submitted my solution however it says that the answer is wrong. It says that the program compiled successfully without any errors or warnings. The problem gives the right answer on my machine for the given example. I provide the question and my code below:
Question:
Zonal Computing Olympiad 2012, 26 Nov
2011 10:00 am-1:00 pm IST Problem 1 :
Matched BracketsA sequence of opening and closing
brackets is well-bracketed if we can
pair up each opening bracket with a
matching closing bracket in the usual
sense. For instance, the sequences (),
(()) and ()(()) are well-bracketed,
while (, ()), (()(), and )( are not
well-bracketed.The nesting depth of a well-bracketed
sequence tells us the maximum number
of levels of inner matched brackets
enclosed within outer matched
brackets. For instance, the nesting
depth of () and ()()() is 1, the
nesting depth of (()) and ()(()) is 2,
the nesting depth of ((())) is 3, and
so on.Given a well-bracketed sequence, we
are interested in computing the
following:The nesting depth, and the first position where it occurs-this will bethe position of the first opening
bracket at this nesting depth, where
the positions are numbered starting
with 1.The maximum number of symbols between any pair of matched brackets,including both the outer brackets, and
the first position where this
occurs-that is, the position of the
first opening bracket of this segment.For instance, the nesting depth of
()(())()(()())(()()) is 2 and the
first position where this occurs is 4.
The opening bracket at position 10 is
also at nesting depth 2 but we have to
report the first position where this
occurs, which is 4.In this sequence, the maximum number
of symbols between a pair of matched
bracket is 6, starting at position 9.
There is another such sequence of
length 6 starting at position 15, but
this is not the first such position.
Input formatThe input consists of two lines. The
first line is a single integer N, the
length of the bracket sequence.
Positions in the sequence are numbered
1,2,âŚ,N. The second line is a sequence
of N space-separated integers that
encode the bracket expression as
follows: 1 denotes an opening bracket
( and 2 denotes a closing bracket ).
Nothing other than 1 or 2 appears in
the second line of input and the
corresponding expression is guaranteed
to be well-bracketed. Output formatYour program should print 4
space-separated integers in a line,
denoting the four quantities asked for
in the following order: nesting depth,
first position that achieves the
nesting depth, length of the maximum
sequence between matching brackets and
the first position where such a
maximum length sequence occurs.
TestdataYou may assume that 2 ? N ? 105. In
30% of the test cases, 2 ? N ? 103.
Sample Input20 1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 1 2 1
2 2Sample Output
2 4 6 9
Time and memory limits
The time limit for this task is 1
second. The memory limit is 32MB.
My submitted solution is:
#include "iostream"
#include<stdio.h>
using namespace std;
int main()
{
unsigned int i,n,o,c,dep,pos_d,pos_m,last_pos,max;
char* arr,*rn;
cin>>n;
fflush(stdin);
arr = new char [2*n];
rn = fgets(arr, (2*n), stdin);
c=o=dep=pos_d=pos_m=last_pos=max=0;
for(i=0;arr[i];i++)
{
if(arr[i]==' ')
continue;
else if(arr[i]=='1')
{
o++;
if(c>0)
c--;
else
{
dep++;
pos_d = (i/2)+1;
}
}
else if(arr[i]=='2')
{
c++;
if(o>0)
o--;
if(o==0)
{
if(((i-last_pos+2)/2)>max)
{
max=(i-last_pos+2)/2;
pos_m = 1+(last_pos+1)/2;
}
last_pos = i+1;
}
}
}
cout<<dep<<" "<<pos_d<<" "<<max<<" "<<pos_m;
return 0;
}
Kindly help me find the problem as I donât see any error and I seem to be getting the right answer for the given example.
Some useful links:
ZCO 2012 Question paper: Indian Computing Olympiad Archives 2012 - IARCS
Test server site: http://www.iarcs.org.in/zco2013/index.php