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

×

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

This question is marked "community wiki".

asked 24 May '17, 17:47

aulene's gravatar image

5★aulene
313
accept rate: 0%

edited 08 Jul '17, 16:50

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170


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

link

answered 26 May '17, 19:41

montycs's gravatar image

0★montycs
1057
accept rate: 0%

Using a DFA we can implement this.
Regex : (\\.*(H\\.*T\\.*)?)*
My Solution

link

answered 07 Jul '17, 10:47

spartax's gravatar image

3★spartax
11
accept rate: 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

link

answered 04 Nov '17, 17:12

tirrojk's gravatar image

0★tirrojk
11
accept rate: 0%

edited 04 Nov '17, 17:13

bekar editorial diya hai

link

answered 03 Oct '18, 17:12

koder772's gravatar image

1★koder772
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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