It seems to me, that your code is not working…
3 Likes
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
@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.
@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
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 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)
Hey, I was solving the same question using JAVA, but I got a WA in the second last test case of the first sub-task and the last test case of the second sub task. Rest all 13 test cases were AC. Can someone look at my code, I have literally been scratching my head for two hours.
Problem page: https://www.codechef.com/ZCOPRAC/problems/ZCO12001
Code submission and test result: https://www.codechef.com/viewsolution/12146831
import java.util.*;
class ZCO12001
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int a[]=new int[n];
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
}
int c1=0;
int c2=0;
int s1=0;
int s2=0;
int h=0;
int i=0;
do
{
int c2x=0;
int s2x=0;
if(a[i]==1)
{
h++;
i++;
c2x=1;
s2x=i;
while(h>0)
{
if(a[i]==1)
{
h++;
i++;
}
else
{
h--;
i++;
}
if(c1<h)
{
c1=h;
s1=i;
}
c2x++;
}
}
else
{
i++;
}
if(c2x>c2)
{
c2=c2x;
s2=s2x;
}
}while(i<n);
System.out.println(c1+" "+s1+" "+c2+" "+s2);
}
}
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 - 6IzqKF - Online C++ Compiler & Debugging Tool - Ideone.com
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 . .
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
@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…
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.