[closed]Help required in ZCO 12001(Matched Brackets)

help
, , , ,
1

import java.util.*;
public class Main
{
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
int n=s.nextInt();
int na[]=new int[n];
for(int i=0;i<n;i++){
na[i]=s.nextInt();
}

        calcNdep(na);
        calcMaxSeq(na);
    }

    static void calcNdep(int naa[])
    {
        int dep=0;
        int maxd=0;
        int fpos=0;
        for(int i=0;i<naa.length;i++){
            if(naa[i]==2){
                if(dep>maxd){
                    maxd=dep;
                    fpos=i;
                }    
                dep=0;
            }
            else if(naa[i]==1) {
                dep++;
            }
        }
        System.out.print(maxd+" "+fpos+" ");
    }
    static void calcMaxSeq(int naa[])
    {
        int no=0;
        int nt=0;
        int fpos=0;
        int mxlsq=0;
        for(int i=0;i<naa.length;i++){
            int num=naa[i];
            if(num==1){
                no++;
            }
            else if(num==2){
                nt++;
            }
            if(i%2!=0){
                if(no==nt){
                    int lmsq=no*2;
                    if(lmsq>mxlsq){
                        mxlsq=lmsq;
                        fpos=i-lmsq+2;
                    }
                    no=0;
                    nt=0;
                    lmsq=0;
                }
            }
        }
        System.out.print(mxlsq+" "+fpos);
    }
}

Problem Link:www.codechef.com/ZCOPRAC/problems/ZCO12001

Why does my solution get AC only for few test cases but not for the others?
Precisely, my solution gets accepted only in 5/15 test cases.
Please help!

2

It will be better if you explained your approach. It will be easier for others to help you debug.

3

can you explain your logic?

4

My approach: To calculate the nesting depth of the sequence, I counted the maximum number of consecutive '1’s(opening brackets)
until a ‘2’(closing bracket) is encountered. The first position where it occurred = the array index of the first ‘2’ encountered. To calculate the maximum number of symbols between any 2 matched brackets, I calculated the length of the maximum well-bracketed sequence within the given sequence. To calculate the first position where it occurred: Let’s say the last finishing bracket of the well-bracketed sequence was at index i in the array. Therefore, the first position of the well bracketed sequence= i-length of the sequence+2.

5

“maximum number of consecutive '1’s(opening brackets) until a ‘2’(closing bracket) is encountered.”

Consider case 1 1 1 2 1 1 1 2 2 2 1 2 2 2

According to your explanation, Maximum depth would be 3, but is actually 5.

6

Can you please elaborate, @taran_1407? I am still confused about the definition of “well-bracketed sequence”!

7

A well bracketed sequence is a sequence, which satisfies following in simple words.

For every opening bracket (1 in this problem) There must be an occurrence of closing bracket (2), which always appear after opening bracket. We call the pair of (1,2) bracket as bracket pair.

About max depth, Depth is the number of bracket pair whose opening bracket we have entered, but we haven’t come out of bracket.

You can consider 11121222. In this, we enter 1st bracket, 2nd bracket, 3rd bracket, exit bracket of depth 3, enter bracket of depth 3, exit depth 3, exit depth 2, exit depth 1. Hope it’s clear.

8

Thanks, @taran_1407. Got my solution debugged. :slight_smile:

9

Glad it helped. :slight_smile: