- Prepare
- Algorithms
- Dynamic Programming
- Equal
- Discussions
Equal
Equal
+ 36 comments I think we don't need to use dynamic programming here. First of all, if you give chocolate bars to all but chosen one, it is equivalent to take away the chocolate bar(s) from each chosen one until every one is equal. So the challenge becomes decrease from each individual 1, 2 or 5 until all are equal. Second to calculate the ops we need to use to decrease an integer n until it reaches 0 (call it the function f) is equivalent to convert 1, 5 (no need to use dynamic programming here). Finally, to solve this challenge, we find the min (call it m) of the given list, then for i from 0 to 4, we find min of ops[i]=sum(f(c-min+i)) where c is each individual colleague and thus no need to use dynamic programming here :)
+ 4 comments SPOILER! Hint if you're stuck:
Giving chocolate to everyone except the chosen person is the same as taking chocolate away from the chosen person. We don't care about how much chocolate they end up with, only that each person's amount is equal.
For example:
Give 5: 1 3 5 6 8 5 <- Take 5: 1 3 5 1 3 0 <- The two results are the same relative to themselves, just shifted: 1 3 0 + 5 5 5 --------- 6 8 5
The problem becomes much simpler now.
Also remember to look for caching opportunities.
+ 10 comments 100% correct Java 8 Solution
import java.io.; import java.util.;
public class Solution {
public static long find_min_actions(int[] cookies) { Arrays.sort(cookies); long sum = Long.MAX_VALUE; for(int base = 0; base < 3; base++) { int current_sum = 0; for(int i = 0; i < cookies.length; i++) { int delta = cookies[i] - cookies[0] + base; current_sum += (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1; } sum = Math.min(current_sum,sum); } return sum; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); while(n-->0) { int m = in.nextInt(); int cookies[] = new int[m]; for(int cookie_i=0; cookie_i < m; cookie_i++){ cookies[cookie_i] = in.nextInt(); } System.out.println(find_min_actions(cookies)); } }
}
+ 0 comments Video solution with explanation: https://youtu.be/rdlzz2GOcq4
+ 2 comments Why does the problem say 3 chocolates when all of the discussions and editorial use 2?
Sort 422 Discussions, By:
Please Login in order to post a comment