Problem Code : COMPILER

CodeChef-DSA-learners
1

HELP!
Cant seem to understand which test case fails for the following code.
#include <stdio.h>

#define MAXSIZE 1000001

int main(void) {
// your code goes here
char exp[MAXSIZE];
int c_open, prefix, max, t, i;
scanf("%d", &t);
while(t–){
scanf("%s", exp);
c_open = 0;
prefix = 0;
max = 0;
for(i = 0; exp[i] != ‘\0’; i++){
if(exp[i] == ‘<’ && prefix > 0){
c_open = 1;
prefix = 0;
}
else if(exp[i] == ‘<’)
c_open++;
if(exp[i] == ‘>’ && c_open > 0){
prefix += 2;
c_open–;
}
if(prefix > max)
max = prefix;
}
printf("%d\n", max);
fflush(stdin);
}
return 0;
}

Please help!

2

Check your code for this test case
1
<<>
The correct o/p should be 0 but your code returns 2

1 Like
3

Thankyou so much…your help made me come up with a few different ways, although all are WA.
Previously, I thought we have to o/p longest prefix even if it was an invalid statement…but now i dont know if i was wrong!!
Taking your help i came up with the following, which returns 0 if its an invalid statement:
`#include <stdio.h>

#define MAXSIZE 1000001

int main(void) {
// your code goes here
char exp[MAXSIZE];
int t, i, up, down, prefix;

scanf("%d", &t);
while(t--){
    scanf("%s", exp);
    up = 0;
    prefix = 0;
    down = 0;
    for(i = 0; exp[i] != '\0'; i++){
        if(exp[i] == '<' && down != 0)
        break;
        else if(exp[i] == '<')
        up++;

        if(exp[i] == '>' && up == 0)
        break;
        else if(exp[i] == '>')
        down++;

        if(up == down){
            if(up * 2 > prefix)
            prefix = up * 2;
            up = 0;
            down = 0;
        }
    }
    if(exp[i] == '\0' && up == 0)
    printf("%d\n", prefix);
    else
    {
        printf("0\n");
    }
    
    fflush(stdin);
}
return 0;

}`
but this still shows WA…
Then i saw the example which says <>>> should o/p 2, but this is an invalid statement…
Could you explain the problem statement to me, what it wants…
Does it mean every < should have a > but every > need not have a <
I’ve been spending too much time on this and cant seem to get moving without getting this right,could you please help me one last time and explain the problem statement properly.

4

The problem statement says that for every ‘<’ symbol there should be one ‘>’ symbol but it is not mandatory that it should occur after that, it can occur immediately as well as somewhere in the given string, and for ‘>’ symbol it should always have one ‘<’ symbol corresponding to it.
And now about this test case <>>> as you can see according to the problem statement we want that ‘<’ symbol should have one ‘>’ so it is there and about this ‘>’ symbol should have one corresponding ‘<’ it is present just before >. That’s why this testcase is valid.

5

Hello. Okay so now i think i understand. But let me be sure, so
<<>>>> should return 4 <>< should return 2 <<> should return 0 and <><<>> should return 2 right?
With this understanding i came up with this:
#include <stdio.h>

#define MAXSIZE 1000001

int main(void) {
// your code goes here
char exp[MAXSIZE];
int t, i, open, prefix;

scanf("%d", &t);
while(t--){
    scanf("%s", exp);
    open = 0;
    prefix = 0;
    
    for(i = 0; exp[i] != '\0'; i++){
        if(i == 0 && exp[i] != '<')
        break;
        
        if(exp[i] == '<')
        open++;
        else
        open--;
        
        if(open == 0){
            prefix = i + 1;
            break;
        }
    }
    
    printf("%d\n", prefix);
    
    fflush(stdin);
}
return 0;

}
But yet again, its WA! :sob:
Could you please be so kind to point out the test case for which this fails. Thankyou.

6

Consider the test input:

1
<><>
7

Oh my god, should this output 4!?

8

No :slight_smile:

prefixLength: prefix:  is valid: 
1             <        false
2             <>       true
3             <><      false
4             <><>     true
==========
4
1 Like
9

Oh god, finally! :relieved:
Thank you so much, it took me 15 wrong submissions and 3 days to get it right. You solved the last bit of doubt. Much of the problem was i couldn’t understand the problem statement. No wonder this simple problem had so many wrong submissions.
Thank you so much for your quick help. Can finally sleep in peace tonight.

1 Like