 # 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] 444
TESTER’s solution: [Here] 555

1 Like

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??

Here is my solution in c++:
https://www.codechef.com/viewsolution/13948382
It was giving me wrong answer.

Here’s my simple cpp solution: https://www.codechef.com/viewsolution/13909341

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.

Here’s a solution without maintaining any record array’s.
https://www.codechef.com/viewsolution/13915068

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

here’s my solution in c.
Can anybody tell me why it is giving me wrong answer.plzzzzz
https://www.codechef.com/viewsolution/13990446

https://www.codechef.com/viewsolution/13999283

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:

https://www.codechef.com/viewsolution/13973763

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.

hey what’s wrong with this code. its giving me wrong answer.
https://www.codechef.com/viewsolution/14135108

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?
https://www.codechef.com/viewsolution/14162288

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.

@drabzee

your code goes wrong for this input

1

msmmssss