SNELECT - Editorial



Author: Praveen Dhinwa
Tester: Hasan Jaddouh
Editorialist: Sidhant Bansal



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.


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.


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'):
                  if(eat(j - 1)):
                  else if(eat(j + 1)):
     snakes -= answer
     if(snakes > mongooses):
          print "snakes"
     else if(mongooses > snakes):
          print "mongooses"
          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 solution: [Here] 444
TESTER’s solution: [Here] 555

1 Like

Here is my solution in java:
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??

Here is my solution in c++:
It was giving me wrong answer.

For the below Input:



The output of your solution is:


Whereas, the expected output should be:


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.

Here’s my simple cpp solution:

Hey refer my solution below, did using boolean array to keep track of eaten and non-eaten snakes. :slight_smile:

This is my solution it says wrong answer can anyone tell me where did I do wrong because the provided test case have been verified.

Here’s a solution without maintaining any record array’s.

Here is my solution, it is giving correct output to me but giving wrong answer on
Please have a look of my code.

both are two different solution and giving wrong answer on

here’s my solution in c.
Can anybody tell me why it is giving me wrong answer.plzzzzz

hey what’s wrong with this code. its giving me wrong answer. Plz help

Could someone help me figure out what is wrong with this solution:

Thanks in advance.

Here’s my code in Java : . Apparently, it is the wrong answer. I can’t seem to find any mistake in it. Can anyone help me in finding my errors.

hey what’s wrong with this code. its giving me wrong answer.

@suddu, In the first loop you may look for snakes outside the string.

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?

i have written code in c.what is wrong with these code?

My code in java : 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.


your code goes wrong for this input



answer is tie but your code is giving mongooses

Here is my C# answer :

Unfortunately I am receiving runtime error here. Can anyone please help me out?