Computing Olympiad Problem Doubt!

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 Brackets

A 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 be

the 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 format

The 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 format

Your 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.
Testdata

You may assume that 2 ? N ? 105. In
30% of the test cases, 2 ? N ? 103.
Sample Input

20 1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 1 2 1
2 2

Sample 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: http://www.iarcs.org.in/inoi/2012/zco2012/zco2012-1a.php
Test server site: http://www.iarcs.org.in/zco2013/index.php

It seems to me, that your code is not working…

3 Likes

Thank you for the prompt answer. I however can’t seem to figure out what’s the problem as it seems to be giving me the right answers on my machine. However please note I am using a windows PC. The test servers I assume run Linux. Therefor I have used a Linux GCC compiler using CODE Blocks to program. Is there anything else I need to do to ensure compatibility with Linux or is the problem with the code itself. Can you please look through my code?

Once again, Thank You.

Mixing cin and something else is problematic (I’m not telling impossible, but I saw a lot of problems here). I changed cin and fgets with scanf, but the idea of the algorithm is yours.

It’s not working as expected - http://ideone.com/6IzqKF

If it is possible, always try to understand the example from statement and verify on paper that you understood it well. Your algorithm is not working for simpler input

6
1 2 1 1 2 2

where depth is 2, but on 4th position, and max number of symbols is from position 3 to position 6 (length is 4)…

1 Like

I think u can implement it using Stack concepts…
No error in codepad.org.
(P.S-intialize n before running it as it doesn’t have any special input window as in ideone )
Just work on your algo. as @betlista said.
Happy Coding!!!
All d best for ZCO…

2 Likes

Thanks again for the answer betlista and xpertcoder. @Betlista It seems the modifications that you made to the source is what is responsible for the wrong output as on my PC I am getting the right answer for the example that you gave with the original source code but getting the wrong one with the modified one.

Just like you mentioned, I always approach the problems through pen and paper and I had verified that the algorithm works for various different inputs. However, using your code at least gives some output at Ideone.com unlike the ‘0 0 0 0’ output which my original code was giving irrespective of the input.

I guess the culprit is my cin and fgets functions. Could you please try and run my original code in your local PC and check? Since I can’t seem to find out the flaw in my program as I am getting the right answers to various different inputs on my PC.

Hi , This was my ZCO Question . My Friend got this accepted . He used a Static Stack implementation on this . He used a huge size of 100001 . He used this and he got it accepted and was also selcted. Using a Dynamic Stack data structure will be better . .

1 Like

Hi , This was my ZCO Question . My Friend got this accepted . He used a Static Stack implementation on this . He used a huge size of 100001 . He used this and he got it accepted and was also selcted. Using a Dynamic Stack data structure will be better . .

@august12 I did use a dynamic stack. Thanks for the input though. The problem I guess is not with the algorithm. Cause it works on my PC for various different examples. I think the problem lies elsewhere.

You are correct, I didn’t change the way you are handling indexes in your array.

When I replaced

rn = fgets(arr, (2*n), stdin);

with

rn = fgets(arr, (2*n), stdin);
rn = fgets(arr, (2*n), stdin);

it works fine now, but I have strange feeling about dep++, you are never decreasing that. I’m somehow lost in your c and o variables what is their meaning?

sorry, comments are too short…

I thought that o stands for “number of opened” and c for “number of closed” (or something like that), but I lost in

if(arr[i]=='1') {
    o++;
    if(c>0)
        c--;
    else {
        dep++;
        pos_d = (i/2)+1;
    }
}

pseudo desription

if there is characted for opened bracket
   increase opened count
   if closed count is bigger than 0
      decrement closed count // why?
   else
      increase depth // depth depends on number of closed, how?
      save position

@xpertcoder Thanks for mentioning the site codepad.org. It seems my program is right. The issue is with the input. As in codepad.org, there is no input window, I had to initialize the string and other variables. And it WORKS! So the problem is with the INPUT functions. Can you please tell me whats wrong with the using cin or fgets or gets?

@Betlista I figured out why you were getting wrong output with the modified code using scanf. its not because of a flaw in the algorithm. Its because in your version of the code, you don’t read spaces. however my position, max length and position of max length depends on the number of spaces. That is the reason only the 1st output was always right in your version of code. Could you also please suggest what’s the problem regarding using cin or gets or fgets, etc… as my code seems to work when I initialize the string rather than taking input. However, taking input does work on my PC though…

problem is that after cin it doesn’t jump to second line and fgets reads the rest of first line to \n, so using fgets twice is working solution

@xpertcoder Thanks for mentioning the site codepad.org! Since the iste does not have an input windows, I initialized the string and other variables and guess what? It worked !! So the culprit is the input function. Can you tell me what is the problem with using cin or gets or fgets? The program works even on Ideone when the string is initialized but not when accepting input from stdin. However, the code still works on my PC for some reason when accepting from stdin!

@betlista I figured out the reason for the wrong output for the modified code you provided. Its because my position, max length and max length position variables depend on the number of spaces. However, your program does not take in spaces. Hence the 2nd, 3rd and 4th output would be wrong but the 1st one would always be right. Also can you tell me what was wrong with my implementation of cin or fgets in the program since I nailed the wrong outputs to be caused by input functions. However if I initialize the string without accepting input from stdin, the output works! However, the code still works on my PC for some reason when accepting from stdin!

1 Like

@betlista is right…

fgets reads characters from stream into string and stops when it reads either n-1(in your case 2n-1) characters or a \n whichever comes 1st.

So modify accordingly…

You dont need a stack. You just need a couple of variables

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int depth = 0, depthPos = 0;
    int maxLen = 0, maxPos = 0;
    int temp;
    int counter = 0, curMaxLen = 0, curMaxPos;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        if (temp == 1)
        {
            counter++;
            if (depth < counter)
            {
                depth = counter;
                depthPos = i;
            }
            if (counter > 1)
            {
                curMaxLen++;
            }
            else
            {
                curMaxLen = 0;
                curMaxPos = i;
            }
        }
        else
        {
            counter--;
            if (counter > 0)
                curMaxLen++;
            else
            {
                if (maxLen < curMaxLen)
                {
                    maxLen = curMaxLen;
                    maxPos = curMaxPos;
                }
                curMaxLen = 0;
                curMaxPos = 0;
                
            }
        }
    }
    cout << depth << " " << depthPos + 1 << " ";
    cout << maxLen + 2 << " " << maxPos + 1;
    return 0;
}

This may be a silly question, but do you set the same compilation flags as the judge when you compile it on your machine?
I had the same code giving me different answers on my machine and the judge ( USACO ). I then found out it was because i wasn’t setting the -O2 optimization flag locally.
So ideally, You should compile with the same flags as on the judge.

//This is what i made and i am not able to find any logical errors
//it worked fine for the sample input but it didn’t score me any points
//pls suggest

#include
#include<stdio.h>
using namespace std;

int stack[100000];

int TOP=-1;

void PUSH()
{
TOP++;
stack[TOP]=1;
}

void POP()
{
TOP–;
}

int main()
{
int max_nd=-1,max_fpnd=0,max_ms=0,max_fpms=0;
int ms=0;
int a=0,n=0,i=0,pos=0;
cin>>n;
cin.ignore(80,’\n’);

for(i=0;i<n;++i)
{
if(TOP==-1)
{
if(ms>max_ms)
{
max_ms=ms;
max_fpms=pos;
}
ms=0;
pos=i+1;
}

if(TOP>max_nd)
{
max_nd=TOP;
max_fpnd=pos;
}

 cin>>a;

if(a==1)
{
    PUSH();
}

if(a==2)
{
    POP();
}

ms++;

}

if(TOP==-1)
{
    if(ms>max_ms)
    {
        max_ms=ms;
        max_fpms=pos;
    }
    ms=0;
    pos=i+1;
}

if(TOP>max_nd)
{
max_nd=TOP;
max_fpnd=pos;
}

fflush(stdin);
fflush(stdout);
cout<<max_nd+1<<" “<<max_fpnd+max_nd<<” “<<max_ms<<” "<<max_fpms;
return 0;
}

Can somebody help me with this solution to the above problem? Due to less karma I am unable to ask a question. Here is my code:


// SOLUTION OF ZCO MATCHING BRACKETS PROBLEM (zco3)

#include "iostream"

int main()
{
   long long N;
   std::cin>>N;
   long long *arr = new long long[N];
   
   for(long long i = 1; i<=N; i++)
   std::cin>>arr[i];
   
   long long i = 1;
   long long pos = 0;
   long long tempnest = 1;
   long long nest = 0;
   long long templen = 0;
   long long maxlen = 0;
   long long maxnest = 0;
   long long npos = 1;
   long long mpos = 1;
   long long ctr = 0;
   long long temppos = 1;
   
   while(i<=N)
   {
   	pos = i;
   	tempnest = 1;
   	ctr = 1;
   	i++;
   	
        while(ctr > 0)
   	   { 
		 if(arr[i] == 1)
		 {
		  ctr++;
		  tempnest++;
		 }
		 else
		 {
			ctr--;
		    if(tempnest >nest)
		    {
			  nest = tempnest;
		      temppos = i-1;
		    }
		    tempnest = 1;
	     }
		 i++;
	   }
	   if(nest > maxnest)
	   {
 		 maxnest = nest;
		 npos = temppos; 	   
	   }
	   if((i - pos)>maxlen)
	   {
	      maxlen = i-pos;
	      mpos = pos;
	   }
   }
 

std::cout<<maxnest<<’ ‘<<npos<<’ ‘<<maxlen<<’ '<<mpos;
return 0;
}

This was my python code and it worked fine-

n = int(input())
a = list(map(int,input().split()))
ans1 = 0
ans2 = 0
ans3 = 0
ans4 = 0
coun = 0
coun2 = 1
for i in range(n):
    if a[i] == 1:
        coun += 1
    else:
        coun -= 1   
    if coun > 0:
        coun2 += 1
    else:
        coun2 = 1   
    if coun > ans1:
        ans1 = coun
        ans2 = i+1
    if coun2 > ans3:
        ans3 = coun2
        ans4 = (i-coun2)+3
print(ans1,ans2,ans3,ans4)