October 24th, 2013, 01:14 AM

How to optimise this C code...
Hi guys, I tried solving a Problem... which is..
I have N paclets of candy ...out of which i have to distribute k packets of candy to each person such that unfairness is minimised...
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
sigma(XiXj) = abs(a) where 1<i<j<k
where a denotes the absolute value of a.
constraints 2 < N < 10 pow 5
2<= K <= N
0 <= no.of packets in each candy <= 10 pow 9
Sample Input :
N = 7
K = 3
packets = 10 100 300 200 1000 20 30
Sample Output :
40
Explanation :
I will choose packets having 10, 20 and 30 candies.So unfairness will be 1020 + 2030 + 3010 = 40. It will be minimum as compared to any other distribution which can be verified
Thia is my code.... It runs fine..the problem is it takes too much time for large no. of inputs upto (10 pow 5)... I want to know how to optimize it...Is there at all a way to reduce the no. of loops...???
Code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void quicksort(long int [100000],long int,long int);
int main()
{
long int packs[100000],n,k,i,j;
long int key1=0,key2 = 999999999;
long int temp = 999999999 ;
long int l;
scanf("%ld",&n);
scanf("%ld",&k);
for(i=0;i<n;i++)
scanf("%ld",&packs[i]);
// packs[i] = random(1000000);
quicksort(packs,0,n1);
for(i=0;i<(nk);i++)
{
for(j=i;j<(k1+i);j++)
{
for(l=j+1;l<=(k1+i);l++)
{
// if(key2>key1)
key1 += abs(packs[j]packs[l]);
//else
//continue;
}
}
if( key1 < temp)
key2 = temp = key1;
key1 = 0;
}
printf("%ld",temp);
return 0;
}
void quicksort(long int pack[100000],long int first,long int last){
long int pivot,j,temp,i;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(pack[i]<=pack[pivot]&&i<last)
i++;
while(pack[j]>pack[pivot])
j;
if(i<j){
temp=pack[i];
pack[i]=pack[j];
pack[j]=temp;
}
}
temp=pack[pivot];
pack[pivot]=pack[j];
pack[j]=temp;
quicksort(pack,first,j1);
quicksort(pack,j+1,last);
}
}
October 24th, 2013, 03:05 AM

sigma(XiXj) where 1<i<j<k
where a denotes the absolute value of a.
Where is a in the first line? I could not tell your explanations are clear... :(
I think that after you sorted packets and is processing NK variants of sequential choices of them, you need not recalculate the unfairness from scratch. Rather you should find a way to calculate unfairness of the next sequence of packets via unfairness of previous sequence of packets (with some additional counting). So you should have two nested loops instead of three.
BTW why implementing quicksort yourself instead of using library version? This task is not about reimplementing this, of course...
October 24th, 2013, 04:11 AM

Originally Posted by rodiongork
Where is a in the first line? I could not tell your explanations are clear... :(
I think that after you sorted packets and is processing NK variants of sequential choices of them, you need not recalculate the unfairness from scratch. Rather you should find a way to calculate unfairness of the next sequence of packets via unfairness of previous sequence of packets (with some additional counting). So you should have two nested loops instead of three.
BTW why implementing quicksort yourself instead of using library version? This task is not about reimplementing this, of course...
I edited the post......
Thnq very much......
I got ur idea.... :D . I'll try it and repost...
October 24th, 2013, 07:22 PM

Originally Posted by kurosaki
I edited the post......
Thnq very much......
I got ur idea.... :D . I'll try it and repost...
I tried this... but instead of timed out.. i am getting "wrong answer" errors... plz check the code.. but the code works fine with all the i/p i tried...
Code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void quicksort(long int [100000],long int,long int);
long int main()
{
long int packs[100000],n,k,i,j;
long int key1 = 0,key2 = 0;
long int temp = 0 ;
long int l,m;
scanf("%ld",&n);
scanf("%ld",&k);
for(i=0;i<n;i++)
// scanf("%lld",&packs[i]);
packs[i] = random(1000000);
quicksort(packs,0,n1);
for(l=0;l<k;l++)
for(m=l;m<k;m++)
{
key1 = temp += abs(packs[l]  packs[m]);
}
//printf("\n\n%ld\n\n",temp);
for(i=1;i<(nk);i++)
{
for(j=i;j<(k+i1);j++)
{
key1 += abs(packs[j]  packs[k+i1]);
key2 += abs(packs[j]  packs[i1]);
}
key1 = key1key2 ;
if( key1 < temp)
temp = key1;
key2 = 0;
// printf("\n\n%ld",key1);
}
printf("%ld",temp);
return 0;
}
void quicksort(long int pack[100000],long int first,long int last){
long int pivot,j,temp,i;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(pack[i]<=pack[pivot]&&i<last)
i++;
while(pack[j]>pack[pivot])
j;
if(i<j){
temp=pack[i];
pack[i]=pack[j];
pack[j]=temp;
}
}
temp=pack[pivot];
pack[pivot]=pack[j];
pack[j]=temp;
quicksort(pack,first,j1);
quicksort(pack,j+1,last);
}
}