×

# SNELECT - Editorial

Author: Praveen Dhinwa
Editorialist: Sidhant Bansal

DIFFICULTY -
Easy

PREREQUISITES -
Loops

PROBLEM -
An array of $N$ animals, consisting only of snakes and mongooses in a particular order is given to you. Given that each mongoose can eat at most one snake immediately adjacent to it, determine whose frequency is greater given that the mongoose eat optimally so as to minimise the frequency of the snakes.

QUICK EXPLANATION -

The question is of ad - hoc and greedy type. The question states It can be easily solved if each mongoose uses the greedy strategy of first checking if its immediate left neighbour and if not possible to eat it then check its right neighbour.

EXPLANATION -

Iterate over all the mongoose from left to right and for each mongoose check if its immediate left neighbour can be eaten, if yes, then increment the answer and move to the next mongoose. Otherwise, check if its immediate right neighbour can be eaten, if yes, then increment the answer and move on. By checking a neighbour we mean, we need to check that the particular position is occupied by a snake which is NOT eaten already.

The pseudocode will be -

bool eaten[N]
int T
input T
FOR i = 1 to T:
string S
input S
int snakes = 0, mongooses = 0, answer = 0
FOR j = 0 to S.length() - 1:
eaten[j] = 0
FOR j = 0 to S.length() - 1:
if(S[j] == 'm'):
mongooses++
if(eat(j - 1)):
else if(eat(j + 1)):
else:
snakes++
if(snakes > mongooses):
print "snakes"
else if(mongooses > snakes):
print "mongooses"
else:
print "tie"

bool eat(int x):
if(x < 0 or x >= S.length()):
return false
if(S[x] == 's' and eaten[x] == 0):
eaten[x] = 1
return true
return false


Time Complexity -
Time complexity per test case is $O(N)$, therefore the total time complexity is $O(N * T)$

# AUTHOR'S AND TESTER'S SOLUTIONS:

AUTHOR's solution: Here
TESTER's solution: Here

This question is marked "community wiki".

179718
accept rate: 12%

19.3k348495534

 0 Here is my solution in java: https://www.codechef.com/viewsolution/13924424 It was giving me wrong answer. But when I wrote the same code in c++, it got accepted. Was there any mistake in input format?? answered 01 Jun '17, 21:48 56●2 accept rate: 9%
 0 Is the following logic correct? Maximum number of snakes that can be eaten = number of occurrences of substring "sm" +number of occurrences of substring "ms" - the number of occurrences of substring "sms". Overlapping substrings are considered different and counted. For example "smsms" number of occurrences of substring "sm"=2 number of occurrences of substring "ms"=2 the number of occurrences of substring "sms"=2 answered 02 Jun '17, 04:43 11●2 accept rate: 0%
 0 Here is my solution in c++: https://www.codechef.com/viewsolution/13948382 It was giving me wrong answer. why it is wrong. answered 02 Jun '17, 12:20 1●1 accept rate: 0%
 0 Here is my solution in c++: https://www.codechef.com/viewsolution/13948382 It was giving me wrong answer. answered 02 Jun '17, 12:22 1●1 accept rate: 0% For the below Input: 1 sssmm The output of your solution is: mongooses Whereas, the expected output should be: tie Because, the mongoose at position 4 will eat the snake at position 3.Therefore, only 2 snakes would be left and the number of mongooses is also 2. Hence, the output should be tie. (02 Jun '17, 13:23) Hey refer my solution below, did using boolean array to keep track of eaten and non-eaten snakes. :) (02 Jun '17, 13:30)
 0 Here's my simple cpp solution: https://www.codechef.com/viewsolution/13909341 answered 02 Jun '17, 13:29 419●1●10 accept rate: 7%
 0 This is my solution https://www.codechef.com/viewsolution/13924801 it says wrong answer can anyone tell me where did I do wrong because the provided test case have been verified. answered 02 Jun '17, 14:36 1 accept rate: 0%
 0 Here's a solution without maintaining any record array's. https://www.codechef.com/viewsolution/13915068 answered 02 Jun '17, 17:26 1★jatin69 1 accept rate: 0%
 0 Here is my solution, it is giving correct output to me but giving wrong answer on codechef.com Please have a look of my code. both are two different solution and giving wrong answer on codechef.com answered 02 Jun '17, 17:50 1 accept rate: 0%
 0 here's my solution in c. Can anybody tell me why it is giving me wrong answer.plzzzzz https://www.codechef.com/viewsolution/13990446 answered 02 Jun '17, 20:00 1 accept rate: 0%
 0 https://www.codechef.com/viewsolution/13999283 hey what's wrong with this code. its giving me wrong answer. Plz help answered 03 Jun '17, 00:54 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,005
×3,396
×919
×887
×58
×15

question asked: 31 May '17, 22:41

question was seen: 3,753 times

last updated: 13 Apr, 12:26