SNAKPROC - Editorial

PROBLEM LINKS:

Contest

Practice

Author: Praveen Dhinwa

Primary Tester: Hasan Jaddouh

Editorialist: Aulene De

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

A string is given in the form of ‘H’, ’T’ and ‘.’ characters, where H denotes the head, T denotes the tail and ‘.’ denotes the time between a snake passing or a the time between one snake and another. Given a string, check if it is a valid sequence of ordering of snakes.

EXPLANATION:

Let’s see… the ‘.’ characters don’t look useful. Do they? Nah. They’re just signifying empty spaces… which doesn’t help us at all. Ignore them.

Now, we have a string made up entirely of ‘H’ and ’T’ characters. This string denotes the ordering of the snakes. Alright, so when is a string invalid?

So, like most animals, a snake can’t have two heads or tails. Thus, we can’t have two ‘H’ or ’T’ characters together. What else?

Let’s see, we can’t have a tail appearing before a head, that’s preposterous! Similarly, we can’t have a head without a tail. Could these two cases appear anywhere in our string?

Sadly, they can. The first case will appear only at the beginning of the string. The second will appear towards the end.

Thus, we can simply check if any of the above conditions is true, thus making our answer ‘Invalid’. Otherwise, our answer is ‘Valid’. We have a cute solution.

Simply put, the only way a string is valid is when it is of the form “HTHTHTHT”. Starts with an ‘H’, ends with a ’T’ and no character should repeat right after itself.
PS: Finding edge cases is always important. Take whatever is in a problem statement at face-value and don’t assume that a case isn’t possible. To put it in Sherlock’s words - “If you eliminate the improbable, whatever remains must be the truth”. Always be on the lookout for cases where your code could fail.

SOLUTIONS:

Editorialist’s solution - // SNAKPROC// Aulene De#include<iostream>#include<fstream>#include<cst - Pastebin.com

1 Like

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:

https://www.codechef.com/viewsolution/13791366

Using a DFA we can implement this.

Regex : (\\.*(H\\.*T\\.*)?)*

My Solution

Could anyone tell me what is wrong with my code?
I just tried to logic out the problem.
My code handles both the given examples and my own input fine, but it tells me my solution isn’t correct.
So it would be great if someone could point out any errors i might have made.

(PYTHON 2.7)
My solution:
https://www.codechef.com/viewsolution/16066772

This post was flagged by the community and is temporarily hidden.

can i get test cases for the problem?

1 Like

use
if(flag == true && top==-1)
instead of
if(flag == true && topElement(a) != 1)

because when the whole string is checked
then for valid string top will track back to value -1 it was set initially in the pgm

one the other hand,
topElement(a) can show any garbage value when top =-1 (for the valid case )
if that garbage value is 1 then code will print “Invalid” even in the case of “Valid” string

Hope it helps

What is wrong with this code? I tried solving it using stack.
stackstk;

    int n,cnt=0;string str;cin>>n>>str;
    for(int i=0;i<str.size();i++){
        if(stk.empty() && (str[i]=='H' || str[i]=='T')){
            stk.push(str[i]);
        }else if(str[i]=='T' && stk.top()=='H'){
            stk.pop();
        }else if(str[i]=='.'){
            cnt++;
        }
    }
    if(stk.empty() || cnt==str.size()){
        cout<<"Valid\n";
    }else{
        cout<<"Invalid\n";
    }