Eddy: Created page with "=Problem Statement= Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has N packets of candies and would like to distribute one packet to each of t..."

2014-12-01T23:25:49Z

Created page with "=Problem Statement= Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has N packets of candies and would like to distribute one packet to each of t..."

New page

=Problem Statement=
Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has N packets of candies and would like to distribute one packet to each of the K children in the village (each packet may contain different number of candies). To avoid any fighting among the children, he would like to pick K out of N packets, such that unfairness is minimized.

Suppose the K packets have (x1, x2, x3,....xk) candies in them, where xi denotes the number of candies in the ith packet, then we define unfairness as

max(x1,x2,...xk) - min(x1,x2,...xk)

where max denotes the highest value amongst the elements, and min denotes the least value amongst the elements. Can you figure out the minimum unfairness and print it?

===Input Format===
The first line contains an integer N.
The second line contains an integer K. N lines follow. Each line contains an integer that denotes the candy in the ith packet.

===Output Format===
An integer that denotes the minimum possible value of unfairness.

===Constraints===
1<=N<=105
1<=K<=N
0<= number of candies in any packet <=109

===Sample Input #00===
<source lang="text">
7
3
10
100
300
200
1000
20
30
</source>

===Sample Output #00===
<source lang="text">
20
</source>

===Explanation #00===
Here K = 3. We can choose packets that contain 10,20,30 candies. The unfairness is

*max(10,20,30) - min(10,20,30) = 30 - 10 = 20

===Sample Input #01===
<source lang="text">
10
4
1
2
3
4
10
20
30
40
100
200
</source>
===Sample Output #01===
<source lang="text">
3
</source>

===Explanation #01===
Here K = 4. We can choose the packets that contain 1,2,3,4 candies. The unfairness is

*max(1,2,3,4) - min(1,2,3,4) = 4 - 1 = 3

==Soluzione di Eddy==

<source lang="C">
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 100000
#define MAX_VAL 1000000001

int candies[MAX];

void MergeSort (int *candies, int primo, int ultimo);
void Merge (int *candies, int primo, int ultimo, int mezzo);
int Unfairness (int *candies, int len, int k);

int main() {

int N,K;
int i;
FILE *fin;

if ((fin=fopen("input.txt","r")) == NULL)
exit(2);
fscanf(fin,"%d %d",&N,&K);
for(i = 0;i < N;i++)
fscanf(fin,"%d",candies + i);
MergeSort (candies, 0, N-1);
int unfairness = Unfairness (candies, N, K-1);

printf("%d\n",unfairness);
return 0;
}

/* IDEA:
* siccome l'array e` ordinato max = i-esima pos + (k-1), min = i-esima pos,
* mi basta scorrere l'array pagando O(n), ma avevo ordinato: O(nlog(n))
*/
int Unfairness (int *candies, int len, int k)
{
int i, min, tmp;
i=0; min=candies[len-1];
while (i+k < len){
tmp = candies[i+k] - candies[i];
if (tmp < min) min = tmp;
i++;
}
return min;
}

void MergeSort (int *candies, int primo, int ultimo)
{
if (primo < ultimo){
int mezzo = (primo+ultimo)/2;
MergeSort(candies, primo, mezzo);
MergeSort(candies, mezzo+1, ultimo);
Merge(candies, primo, ultimo, mezzo);
}
}

void Merge (int *candies, int primo, int ultimo, int mezzo)
{
int i, j, k, h;
int tmp[MAX];
i = primo; j = mezzo+1; k = primo;
/* "compongo tmp" fino a quando non esaurisco una meta` */
while (i <= mezzo && j <= ultimo){
if (candies[i]<=candies[j])
tmp[k++] = candies[i++];
else
tmp[k++]=candies[j++];
}
j=ultimo;
/* se sono rimasti degli elementi nella prima meta` saranno i maggiori */
for (h=mezzo; h>=i; h--)
candies[j--]=candies[h];
for (j=primo; j<=k-1; j++)
candies[j]=tmp[j];
}
</source>
[[User:Eddy|Eddy]] ([[User talk:Eddy|talk]]) 00:59 Mon, 02 Dic 2014 (CET)

Angry Children - Revision history

Eddy: Created page with "=Problem Statement= Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has N packets of candies and would like to distribute one packet to each of t..."