You are not logged in. Please login at www.codechef.com to post your questions!

×

# Computing Olympiad Problem Doubt!

 0 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 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<

 3 It seems to me, that your code is not working... http://ideone.com/pAwWRm answered 09 Nov '12, 03:23 16.9k●49●115●225 accept rate: 11% 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. (09 Nov '12, 12:00) 1 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)... (09 Nov '12, 12:47) 2 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... (09 Nov '12, 13:14) 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. (09 Nov '12, 17:29) 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 . . (09 Nov '12, 17:59) august120★ 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? (09 Nov '12, 18:17) 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  (09 Nov '12, 18:21) @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.... (09 Nov '12, 18:32) 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 (09 Nov '12, 18:35) @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... (09 Nov '12, 19:24) showing 5 of 10 show all
 1 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 . . answered 09 Nov '12, 17:57 0★august12 16 accept rate: 0%
 1 @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! answered 09 Nov '12, 19:08 11●2●3●5 accept rate: 0%
 0 @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. answered 09 Nov '12, 18:11 11●2●3●5 accept rate: 0%
 0 You dont need a stack. You just need a couple of variables #include 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; }  answered 07 Sep '14, 23:35 11●1 accept rate: 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<stdio.h>

using namespace std;

int stack;

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; }

answered 03 Dec '14, 21:21 53718
accept rate: 27%

 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<
 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)  answered 30 Oct '16, 02:09 2.6k●1●10●34 accept rate: 7%
 0 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;i0) { if(a[i]==1) { h++; i++; } else { h--; i++; } if(c1c2) { c2=c2x; s2=s2x; } }while(i
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,285
×427
×365
×198
×71

question asked: 09 Nov '12, 00:35

question was seen: 6,411 times

last updated: 27 Nov '16, 20:03