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