#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Posts
    24
    Rep Power
    0

    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(Xi-Xj) = 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 |10-20| + |20-30| + |30-10| = 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,n-1);
    
      for(i=0;i<(n-k);i++)
       {
        for(j=i;j<(k-1+i);j++)
         {
           for(l=j+1;l<=(k-1+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,j-1);
             quicksort(pack,j+1,last);
    
        }
    }
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2013
    Location
    Saint-Petersburg, Russia
    Posts
    237
    Rep Power
    29
    sigma(Xi-Xj) 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 N-K 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...
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Posts
    24
    Rep Power
    0
    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 N-K 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...
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2013
    Posts
    24
    Rep Power
    0
    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,n-1);
    
    
      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<(n-k);i++)
       {
        for(j=i;j<(k+i-1);j++)
         {
         key1 += abs(packs[j] - packs[k+i-1]);
         key2 += abs(packs[j] - packs[i-1]);
         }
         key1 = key1-key2 ;
       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,j-1);
             quicksort(pack,j+1,last);
    
        }
    }

IMN logo majestic logo threadwatch logo seochat tools logo