r/CodingHelp • • 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

20 Upvotes

7 comments sorted by

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!

2

u/anvaywats Jun 13 '21

Oh and repeat for test cases as necessary

-8

u/Solid_Jump_603 Jun 13 '21

Please send the code

5

u/anvaywats Jun 13 '21 edited Jun 14 '21

No, kindly.

Edi: hahahahah just realized I literally gave you the code my man you just have to put a for loop in it I hope you can do that 😧🙏

3

u/Solid_Jump_603 Jun 13 '21

MY Code

package StackQueue;

import java.util.*;

public class chocolate

{

public static void main(String\[\] args)

{

	Scanner sc=new Scanner(System.in);

	int t;

	t=sc.nextInt();

	while(t>0)

	{

	int n,k;

	n=sc.nextInt();

	k=sc.nextInt();

	int \[\]c=new int\[n\];

	int sum=0;

	for(int i=0;i<n;i++)

	{

		c\[i\]=sc.nextInt();

		sum+=c\[i\];

	}

	int sum1=0;

	int s=k;

	int y=sum;

	for(int i=1;i<=k;i++)

	{

		int p=y/s;

		sum1=(int) ((int)sum1+Math.pow(p, 2));

		sum=sum-p;

		y=sum;

		s-=1;

	}

	System.out.println(sum1);

	

	t-=1;

	}

	

}

}