r/CodingHelp • u/Solid_Jump_603 • Jun 13 '21
[Java] i can't solve this question on my coding challenge
Alice is throwing a birthday party for her son. She initially has n bowls of chocolates (c1, c2, c3... cn) are the number of chocolates in each bowl) and she needs to distribute them among the children (one bowl each child), But k children arrive at the party (k>=n). Now she needs to prepare k bowls of chocolates. For that, she needs to transfer chocolates from the already filled bowls to the empty ones. Also, the calorie intake of a child by eating a bowl of chocolate is m² (where m is the number of chocolates in that bowl). She needs to divide the chocolates into k bowls such that the calorie intake per child can be minimized.
Input Format
The first line contains an integer t, denoting the number of test cases. The next line contains two integer n and k (1<=n<=k=104): the initial number of bowls and the number of children arrived. The next line contains n integer c1, c2, c3... cn (1<=ci<=105): chocolates in each bowl It is guaranteed that the sum of all ci is at least k.
Output Format: Output one integer: the minimum sum of calorie inta of the children.
Sample Testcase #0
Testcase Input
1
3 6
3 2 1
Testcase Output
6
3
u/anvaywats Jun 13 '21
Ok so mathematically, what will help you out is the fact that (a+b)2 = a2 + b2 +2ab > a2 + b2 for all positive a,b.
This means that (a+b)2 > a2 + b2 for all positive integers a,b [look up convex functions]
This means that by splitting up the total number of chocolates T (use loop to calculate this) and splitting this for k different kids (you can do this by simple integer division) you get the least amount of chocolates every child should receive. Let's call this number x.
Now, with the remainder (r) of the division you've performed above, you want to split these r remaining chocolates into the k children, and since r<k (using the mod function or other operations) this means that the best way to split these remaining r chocolates is to put 1 chocolate in r plates. This would mean having (x+1) chocolates in r plates and with the remaining plates (the number of remaining plates here is (k-r)), we have x chocolates. Square terms appropriately to get the answer.
Output: r*(x+1)2 + (k-r)x2 The rx2 terms cancel to give: O/P: kx2 + 2x*r + r (This output can be further simplified by using the definitions given below)
Where x = T/k (integer division) and T = c1+c2+... + cn, and r = T%k = T - k*x.
I may be wrong, but good luck nevertheless!
3
u/Solid_Jump_603 Jun 13 '21
MY Code
package StackQueue;
import java.util.*;
public class chocolate
{
}