SNCKQL 17 - SNAKPROC Help

help
,
1

I need help in this question : https://www.codechef.com/SNCKQL17/problems/SNAKPROC

I used stack to push when ‘H’ is encountered,pop when ‘T’ is encountered and do nothing when ‘.’ is encountered. Since there weren’t any real elements to push or pop, I simply used 1 as a dummy element that would be pushed or popped whenever required. But still I am get WA. Can anyone point out my mistake? Here’s my solution:

#include <iostream>

using namespace std;
int top = -1;
int push(int a[], int x, int n)
{
    if(top == n-1)
        return 0;
    else
    {
        top += 1;
        a[top] = x;
    }
    return 1;
}
int pop(int a[], int n)
{
    if(top == -1)
        return 0;
    else
    {
        top--;
    }
    return 1;
}
int topElement(int a[])
{
    return a[top];
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n];
        string s;
        cin>>s;
        int len;
        len = s.length();
        bool flag = true;
        for(int i=0;i<len;i++)
        {
            //char x;
            //cin>>x;
            if(s[i] == '.')
                continue;
            else if(s[i] == 'H')
            {
                if(topElement(a) == 1)
                {
                    flag = false;
                    //break;
                }
                else push(a, 1, n);
            }
            else if(s[i] == 'T')
            {
                pop(a,n);
                if(topElement(a) <= -1)
                {
                    flag = false;
                    //break;
                }
            }
        }
        if(flag == true && topElement(a) != 1)
            cout<<"Valid"<<endl;
        else cout<<"Invalid"<<endl;
    }
    return 0;
}
2

2
5
HTHT.
Valid
5
THTHT
Valid

@montycs Your code gives above output . But the answer for the second test case should be Invalid. I think there is an error with your initialization of top=-1

2 Likes
3

1
7
TH…T

Your output: “Valid”

Answer: “Invalid”

2 Likes
4

In this problem you only need to worry about H’s and T’s and can simply ignore all the ‘.’

Now ignoring ‘.’, the string should have these properties:

  1. Starting element should be H
  2. Ending element should be T
  3. No Two H should be together
  4. No Two T should be together

Your code fails the 1st property.

My C++


[1].


  [1]: https://www.codechef.com/viewsolution/13653755
3 Likes
5

@divyansh_gaba7 is correct

6

Probably if suited u can take an array or vector(for ease), by putting some conditions you’ll be good to go. :slight_smile: