×

# 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".

179617
accept rate: 12%

18.4k348492529

 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 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●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%
 0 Could someone help me figure out what is wrong with this solution: https://www.codechef.com/viewsolution/13973763 Thanks in advance. answered 04 Jun '17, 01:21 1 accept rate: 0%
 0 Here's my code in Java : https://www.codechef.com/viewsolution/14120288 . Apparently, it is the wrong answer. I can't seem to find any mistake in it. Can anyone help me in finding my errors. answered 07 Jun '17, 01:20 1 accept rate: 0%
 0 hey what's wrong with this code. its giving me wrong answer. https://www.codechef.com/viewsolution/14135108 answered 07 Jun '17, 18:21 0★suddu 1 accept rate: 0% @suddu, In the first loop you may look for snakes outside the string. (07 Jun '17, 19:36)
 0 What I did was I moved from left to right until n-1 and check if i th and i+1 th characters are different. If they are different I skip this check for i+1 th index and increase a counter by 1. In the end I count 's' and 'm' and subtract counter value from 's' and check what is greater and write the answer. But this approach gave me a wrong answer can someone tell me why? answered 07 Jun '17, 20:26 21●1●3 accept rate: 0%
 0 i have written code in c.what is wrong with these code? https://www.codechef.com/viewsolution/14162288 answered 08 Jun '17, 22:02 0★dimpu123 1 accept rate: 0%
 0 My code in java : https://www.codechef.com/viewsolution/14163077. It is giving wrong answer. I am not able to find out the reason. Sir, can you please help me out to find the error. Thank You. answered 08 Jun '17, 22:53 0★drabzee 1 accept rate: 0%
 0 @drabzee your code goes wrong for this input 1 msmmssss answer is tie but your code is giving mongooses answered 08 Jun '17, 23:14 1.7k●2●10 accept rate: 14%
 0 Here is my C# answer : https://www.codechef.com/viewsolution/14176253 Unfortunately I am receiving runtime error here. Can anyone please help me out? answered 09 Jun '17, 15:18 1●1 accept rate: 0%
 0 why i am getting run time error, my code is: https://www.codechef.com/viewsolution/14254014 since this code executed successfully in visual studio with proper output. answered 14 Jun '17, 20:55 1 accept rate: 0%
 0 Hey what's wrong with this code. Its giving me wrong answer.. https://www.codechef.com/viewsolution/14270370 answered 17 Jun '17, 18:23 1 accept rate: 0%
 0 Here is my solution in C++, getting output correctly but in codechef it is showing wrong answer. Please have a look. https://www.codechef.com/viewsolution/14271038 answered 17 Jun '17, 20:27 0★ankagirm 1 accept rate: 0%
 0 hi have a small problem here my solution is present in the link https://www.codechef.com/viewsolution/14382866 i am getting wrong answer as the result but my c compiler is not giving any wrong output i am scratching my head at this please tell me for which case my answer is wrong appreciate any help thanks answered 01 Jul '17, 14:28 1 accept rate: 0%
 0 @deeptamandas There are cases where you are subtracting the same snake twice from your total snake count. For Example consider the testcase: 1 msmmssss Expected Output : "tie". Your Output : "mongooses" (because you subtracted the count for the first snake twice) . answered 01 Jul '17, 18:01 5★rathi_22 11●2 accept rate: 0%
 0 MY code is working fine in blueJ for all possible outputs but it is still giving runtime error NZEC https://www.codechef.com/viewsolution/14688892 answered 27 Jul '17, 22:44 17●3 accept rate: 0%
 0 Can someone please have a look at my solution and tell why it is wrong? It seems to pass all test cases. https://www.codechef.com/viewsolution/15592785 answered 03 Oct '17, 19:43 2★sprea27 1 accept rate: 0%
 0 https://www.codechef.com/viewsolution/15954256 can anybody help me out ...why i m getting wrong ans answered 25 Oct '17, 14:35 1 accept rate: 0%
 0 try 1 msssssmsm tie this test case will solve your doubt answered 28 Mar, 01:12 2★buzz_95 1 accept rate: 0%
 0 Someone help me!!!!!!! https://www.codechef.com/viewsolution/18228793 answered 13 Apr, 12:26 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:

×13,928
×3,037
×843
×828
×58
×15

question asked: 31 May '17, 22:41

question was seen: 3,416 times

last updated: 13 Apr, 12:26