Help me in solving ZCO12001 problem

help
,
1

My issue

The code is attached. The code is passing only one test case. I am unable to find the error in logic. It seems fine to me but it’s not working for all the test cases

My code

# cook your dish here
n = int(input())
brac_list = list(map(int, input().split()))

MAX_DEPTH = -1
MAX_DEPTH_START = -1

MAX_LEN = -1
START_MAX = -1

depth = 0
start = 0

max_len = 0
start_m = 0

temp_stack = []

for i in range(n):
  if not temp_stack:
    if MAX_LEN < max_len:
      MAX_LEN = max_len
      START_MAX = start_m
    
    start = i
    depth = 1
    temp_stack.append(1)
    
    start_m = i
    max_len = 1
    
  else:
    if brac_list[i] == 1:
      depth += 1
      max_len += 1
      temp_stack.append(1)
      
      if MAX_DEPTH < depth:
        MAX_DEPTH = depth
        MAX_DEPTH_START = i
      
    else:
      depth -= 1
      max_len += 1
      del temp_stack[-1]

print(MAX_DEPTH, MAX_DEPTH_START+1, MAX_LEN, START_MAX+1)

Problem Link: CodeChef: Practical coding for everyone

2

@roumak
Plzz refer the following python solution for better understanding of the logic.

n= int(input())
x=list(map(int, input().split()))
s,c=0,0
nsd,psd=0,0
maxim,maxpos=0,0
for i in range(n):
    if x[i]==1:
        s+=1
        c+=1
        if s>nsd:
            nsd=s
            psd=i+1
    else:
        c+=1
        s-=1
        if s==0:
            if c>maxim:
                maxim=c
                maxpos=i-c+2
            c=0
print(nsd,psd,maxim,maxpos)
3

I mean that’s not what I asked for. I too can just tap on the “submissions” tab and click on the most popular one. I wanted to know what’s wrong in my version of code.

Anyways, Thanks for your reply.

4

@roumak
know that too buddy but , I don’t have good hands on python so can’t help u with debugging your code.
If U want We can discuss the logic that U have came up with to figure out the missing cases.

1 Like
5

Sure, I should’ve explained my approach beforehand.

temp_stack - refers to the variable for storing the stack that contains the opening brackets.

MAX_DEPTH, MAX_DEPTH_START, MAX_LEN, and START_MAX are the variables in which I want to store the final values and print them.

Next, I’m iterating over every item on the list, given in the input.

Case 1: Stack is not empty
If the current element is 1, then I am adding it to the stack and incrementing the value of depth and max_len (temporary variables) by 1. I am also checking that if the current depth is greater than MAX_DEPTH, then I set the value of MAX_DEPTH as the current depth and the MAX_DEPTH_START (which stores the index of the first opening bracket where the maximum depth is reached).

If the current element is 2, then I decrease the value of the current depth by 1 but increase the value of max_len by 1 (as per the requirement of the question). Also, I am deleting the last element from the stack.

Case 2: The stack is empty
This means that we have successfully iterated over a “well-bracketed” sub-part. So, I checked whether the current max_len is greater than MAX_LEN or not. And change it accordingly. Then I reset the values of other temporary variables.

After iterating through all the elements I am just printing the values of
MAX_DEPTH, MAX_DEPTH_START, MAX_LEN, and START_MAX.

I also did a little change in the code and added

if MAX_LEN < max_len:
  MAX_LEN = max_len
  START_MAX = start_m

after iterating through all values. Now it’s failing only two tasks, out of 15.

UPDATE:
Wooah!!

Never thought that explaining my approach would result in me finding the mistake I made in the logic. Thanks, I figured it out!!

1 Like
6

@roumak
Great bro :+1:

7

Thanks dear!