KINGSHIP.c

/* CHEF AND KINGSHIP, Codechef, easy
 * 
 * This is probably the easiest problem I have posted here. The logic is very 
 * simple. To minimize the cost i.e. the sum of product of population of cities
 * the optimal way is to construct roads from the city with minimum population 
 * to every other city. :D (think and try to mathematically prove why).
 *
 * Hence now the solution is as easy as finding the minimum population and sum of
 * all other populations and just multiply the sum and the min.
 *
 * Mathematically: (This is how to define a problem in writings)
 *
 * There are N cities C1, C2, C3... Ci... Cn with population P1, P2, P3 ... Pi ... Pn.
 * The cities are vertices of an complete graph and the weight of an edge between  
 * Ci and Cj is Pi * Pj. (where i != j, i.e. Ci and Cj are distinct vertices)
 * The problem requires computing the sum of weights of edges of the Minimal Spanning Tree.
 *
 */

#include <stdio.h>
#define INF 99999999                        // define a very large value to be   
                                            // used as infinite
int main(){
    int T, N, min, sum, temp;
    scanf("%d",&T);                         // read the number of test cases
    while(T--){                             // iterate T times, explain why this loop works yourself
        scanf("%d",&N);
        min = INF;                          // initialise min to infinite
        sum = 0;                            // initialise sum to zero
        while(N--){                         // iterate N times
            scanf("%d",&temp);              // read the number  
            if(temp < min) min = temp;      // update the min is necessary
            sum += temp;                    // update the sum
        }
        printf("%d\n",(sum-min)*min);       // print the result
    }
    return 0;
}