-
-
Save vidyavnv/7060436 to your computer and use it in GitHub Desktop.
/*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 a fight between the children, he would like to pick K out of N packets | |
such that the 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 | |
Sum [abs(X(i) - X(j))] 1<=i<j<=N | |
where |a| denotes the absolute value of a. | |
Input Format | |
The first line contains an integer N. | |
The second line contains an integer K. N lines follow each integer containing the candy in the ith packet. | |
Output Format | |
A single integer which will be minimum unfairness. | |
Constraints | |
2<=N<=10^5 | |
2<=K<=N | |
0<= number of candies in each packet <=10^9 | |
Sample Input #00 | |
7 | |
3 | |
10 | |
100 | |
300 | |
200 | |
1000 | |
20 | |
30 | |
Sample Output #00 | |
40 | |
Explanation #00 | |
Bill Gates will choose packets having 10, 20 and 30 candies.So unfairness will be |10-20| + |20-30| + |30-10| = 40. | |
It will be minimum as compared to any other distribution which can be verified . | |
Sample Input #01 | |
10 | |
4 | |
1 | |
2 | |
3 | |
4 | |
10 | |
20 | |
30 | |
40 | |
100 | |
200 | |
Sample Output #01 | |
10 | |
Explanation #01 | |
Bill Gates will choose 4 packets having 1,2,3 and 4 candies. So, unfairness will be |1-2| + |1-3| + |1-4| + |2-3| + | |
|2-4| + |3-4| = 10 | |
*/ | |
#include <cmath> | |
#include <cstdio> | |
#include <vector> | |
#include <iostream> | |
#include <algorithm> | |
using namespace std; | |
int main() | |
{ | |
long int *a; | |
long int i,n,k,j,diff1,diff2,l; | |
long long int diff,min = 9223372036854775807; | |
//cout<<"enter no of elements: "; | |
cin>>n>>k; | |
a = new long int[n]; | |
for(i = 0;i<n;i++) | |
cin>>a[i]; | |
std::sort(a,a+n); | |
// for(int i = 0;i < n;i++) | |
// cout<<a[i]<<endl; | |
if(n == k) | |
{ | |
diff = 0; | |
for(i = n - 1; i >= 0; i--) | |
{ | |
diff = diff + (long long int) (a[i] * i - a[i] * (n -i -1)); | |
} | |
min = diff; | |
} | |
else | |
{ | |
for(i = 0 ;i < n - k + 1;i++) | |
{ | |
diff = 0; | |
l = 0; | |
for(j = i;j < i + k;j++) | |
{ | |
diff = diff + (long long int) (a[j] * l - a[j] *(k-l-1)); | |
if(min <= diff) | |
break; | |
l++; | |
} | |
if(j == i + k && diff >= 0) | |
min = diff; | |
} | |
} | |
cout<<min<<endl; | |
delete[] a; | |
return 0; | |
} |
@nerdguy06: I made some changes, it's an improvement over the previous one, runs for two more cases but still gives wrong answer for some cases. Any hint?
the problem is 9223372036854775807 the test cases have output greater than long double max value
@sagarverma: I tried using unsigned long long. But in vain. Infact it is now working for just 2 to 3 cases.
I think you should not use merge sort...things like left[i] = 1000000000;
right[j] = 1000000000; might be creating problems
@nerdguy06: I am using std::sort now. Passes 8 cases out 16 cases. For rest of the 7, says wrong answer. Is something wrong with my algorithm?
that code aint working!!!
heres the working code...
credit: k_maro codes
sanjay kumar, arvind p.bright, akil sai
include
using namespace std;
include<stdio.h>
void input(int a[],int n)
{
for(int i=0;i<n;i++)
{cin>>a[i];
}
}
void answer(int a[], int k,int n)
{ int temp;
for( int i=0;i<n;i++)
{for( int j=0;j<n-1;j++)
{if(a[j]>a[j+1])
{temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
}
}
cout<<endl;
cout<<endl;int b[n];
for(int i=0;i<n;i++)
b[i]=a[i];
for( int i=0;i<n;i++)
{cout<<"\n"<<b[i];
}
int min=32000;
for(int i=0;i<n-k+1;i++)
{if(min>((b[k+i-1])-(b[i])))
min=b[k+i-1]-b[i];
}
cout<<"\n"<<min;
}
int main()
{
int n,k;
int a[n];
cin>>n>>k;
input(a,n);
answer(a,k,n);
return 0;
}
@vidyavnv I've asked a question regarding this and got a couple of algorithms. Maybe they can help you too:
@gnima: I can't understand the python code. What is the algorithm?
This solution is wrong....will TLE in some cases