Hungry lemurs hackerearth

algorithm
data-structure
dynamic-programming
editorial
factorial
greedy
modulo

#1

Can anyone provide detailed editorial for this problem on hackerearth, hackerearth’s tutorial seriously sucks.

In what tag this kind of problems are fond.

Thanks in advance.


#2

I would say it would be a ad-hoc/maths problem. The way i solved it is by looping over each possible value of k (all the possible value you could increase/decrease monkeys to) and then finding the closest multiple of this selected number to the given n. Now just find the difference between the actual N and K and the values of n/k you calculated and find minimum. Can be done in O(k) as n,k<=10**5

Here is my submission: http://ideone.com/k7ZoNj
(in the loop j denotes k, i denotes n as described above)


#3

can you explain your logic in detail?


#4

let’s take 25 and 7


#5

I dont really see much logic in that solution acording to the themes wordpress of numbers. Parity is never the same.


#6

@ankit217

In your case answer will be 2

8*3=24;
25-1=24;

ans=|8-7|+|25-24|;

Please accept the answer if you understood.


#7

@vsp4
How the solution for the test case 39 16 is 3.


#8

@vsp4

if there are 42 bananas and 16 lemurs then how lemurs would get satisfied.


#9

Damn sorry. It should be 39 16 -> 39 15 -> 39 14 -> 39 13

So 39 % 13 = 0


#10

@vsp4

what approach did you use??


#11

@vsp4

why did you start the loop from j=2*k;


#12

@arpit728 Suppose you choose any no l > 2*k Then difference b/w lemurs would be l - k which would atleast be more then (2k - k = k). So it is better to remove all lemurs (that is possible by k moves).

i = n - (n % j);

This finds the greatest multiple of j less or equal to n

then adding +j to that finds least multiple of j more then n.