SNELECT - Editorial

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Hasan Jaddouh
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)):
                       answer++
                  else if(eat(j + 1)):
                       answer++
           else:
                  snakes++
     snakes -= answer
     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.

https://www.codechef.com/viewsolution/13955047
and
https://www.codechef.com/viewsolution/13954434

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

Thanks in advance.

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

answer is tie but your code is giving mongooses

Here is my C# answer : https://www.codechef.com/viewsolution/14176253

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

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.

Hey what’s wrong with this code.
Its giving me wrong answer… https://www.codechef.com/viewsolution/14270370

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