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
179618
accept rate: 12%

edited 01 Jun '17, 21:56

admin's gravatar image

0★admin ♦♦
19.0k348495533


123next »

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%

Is the following logic correct?

Maximum number of snakes that can be eaten = number of occurrences of substring "sm" +number of occurrences of substring "ms" - the number of occurrences of substring "sms".

Overlapping substrings are considered different and counted.

For example "smsms"

number of occurrences of substring "sm"=2

number of occurrences of substring "ms"=2

the number of occurrences of substring "sms"=2

link

answered 02 Jun '17, 04:43

vg_codechef's gravatar image

4★vg_codechef
112
accept rate: 0%

edited 02 Jun '17, 04:47

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

link

answered 02 Jun '17, 12:20

devagarwal's gravatar image

2★devagarwal
11
accept rate: 0%

edited 02 Jun '17, 12:21

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

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

link

answered 02 Jun '17, 13:29

godslayer12's gravatar image

1★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

1★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

1★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

1★cyberinfinity
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:

×14,488
×3,218
×877
×867
×58
×15

question asked: 31 May '17, 22:41

question was seen: 3,577 times

last updated: 13 Apr, 12:26