×

SNAKPROC - Editorial

Contest

Practice

Author: Praveen Dhinwa

Editorialist: Aulene De

Cakewalk

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 - https://pastebin.com/LEfk2hsy

This question is marked "community wiki".

5★aulene
313
accept rate: 0%

2.5k53137170

 0 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 answered 26 May '17, 19:41 0★montycs 105●7 accept rate: 0%
 0 Using a DFA we can implement this. Regex : (\\.*(H\\.*T\\.*)?)* My Solution answered 07 Jul '17, 10:47 3★spartax 1●1 accept rate: 0%
 0 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 answered 04 Nov '17, 17:12 0★tirrojk 1●1 accept rate: 0%
 0 bekar editorial diya hai answered 03 Oct '18, 17:12 1★koder772 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

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:

×15,852
×1,688
×849
×643
×41

question asked: 24 May '17, 17:47

question was seen: 1,617 times

last updated: 03 Oct '18, 17:12