You are not logged in. Please login at www.codechef.com to post your questions!

×

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
TESTER's solution: Here

This question is marked "community wiki".

asked 31 May '17, 22:41

sidhant007's gravatar image

6★sidhant007
179617
accept rate: 12%

edited 01 Jun '17, 21:56

admin's gravatar image

0★admin ♦♦
18.4k348492529


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

link

answered 01 Jun '17, 21:48

coolrohan123's gravatar image

4★coolrohan123
562
accept rate: 9%

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

link

answered 02 Jun '17, 12:22

devagarwal's gravatar image

2★devagarwal
11
accept rate: 0%

edited 02 Jun '17, 12:22

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) pankaj_chopra3★

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

(02 Jun '17, 13:30) godslayer122★

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

link

answered 02 Jun '17, 13:29

godslayer12's gravatar image

2★godslayer12
41910
accept rate: 7%

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.

link

answered 02 Jun '17, 14:36

harikesh409's gravatar image

1★harikesh409
1
accept rate: 0%

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

link

answered 02 Jun '17, 17:26

jatin69's gravatar image

1★jatin69
1
accept rate: 0%

edited 02 Jun '17, 17:27

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

link

answered 02 Jun '17, 17:50

manojshukla146's gravatar image

3★manojshukla146
1
accept rate: 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

link

answered 02 Jun '17, 20:00

raghav_313's gravatar image

3★raghav_313
1
accept rate: 0%

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

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

link

answered 03 Jun '17, 00:54

cyberinfinity's gravatar image

4★cyberinfinity
1
accept rate: 0%

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

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

Thanks in advance.

link

answered 04 Jun '17, 01:21

dumbooctopus's gravatar image

2★dumbooctopus
1
accept rate: 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.

link

answered 07 Jun '17, 01:20

aabhas9999's gravatar image

0★aabhas9999
1
accept rate: 0%

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

link

answered 07 Jun '17, 18:21

suddu's gravatar image

0★suddu
1
accept rate: 0%

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

(07 Jun '17, 19:36) tony_hager5★

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?

link

answered 07 Jun '17, 20:26

manjrekarom29's gravatar image

3★manjrekarom29
2113
accept rate: 0%

i have written code in c.what is wrong with these code? https://www.codechef.com/viewsolution/14162288

link

answered 08 Jun '17, 22:02

dimpu123's gravatar image

0★dimpu123
1
accept rate: 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.

link

answered 08 Jun '17, 22:53

drabzee's gravatar image

0★drabzee
1
accept rate: 0%

@drabzee

your code goes wrong for this input

1

msmmssss

answer is tie but your code is giving mongooses

link

answered 08 Jun '17, 23:14

hruday968's gravatar image

4★hruday968
1.7k210
accept rate: 14%

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

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

link

answered 09 Jun '17, 15:18

dpsatapathy's gravatar image

1★dpsatapathy
11
accept rate: 0%

edited 09 Jun '17, 15:39

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.

link

answered 14 Jun '17, 20:55

purnima29's gravatar image

2★purnima29
1
accept rate: 0%

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

link

answered 17 Jun '17, 18:23

swati_122's gravatar image

0★swati_122
1
accept rate: 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

link

answered 17 Jun '17, 20:27

ankagirm's gravatar image

0★ankagirm
1
accept rate: 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

link

answered 01 Jul '17, 14:28

deeptamandas's gravatar image

0★deeptamandas
1
accept rate: 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) .

link

answered 01 Jul '17, 18:01

rathi_22's gravatar image

5★rathi_22
112
accept rate: 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

link

answered 27 Jul '17, 22:44

humurabbi's gravatar image

2★humurabbi
173
accept rate: 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

link

answered 03 Oct '17, 19:43

sprea27's gravatar image

2★sprea27
1
accept rate: 0%

https://www.codechef.com/viewsolution/15954256 can anybody help me out ...why i m getting wrong ans

link

answered 25 Oct '17, 14:35

golu_nits's gravatar image

1★golu_nits
1
accept rate: 0%

try

1

msssssmsm

tie

this test case will solve your doubt

link

answered 28 Mar, 01:12

buzz_95's gravatar image

2★buzz_95
1
accept rate: 0%

link

answered 13 Apr, 12:26

siddharths's gravatar image

2★siddharths
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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