UVA Problem 10041 – Vito’s Family Solution

UVA Problem 10041 – Vito’s Family Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This is a sorting problem. It requires us minimize the distance from Vito’s to every other house. That distance must be median because median value minimizes the distance from every side. So the median is the position of Vito’s house.

The problem requires us to find, “minimal sum of distances from the optimal Vito’s house to each one of his relatives”. So this means we calculate distance from Vito’s house ( Median ) to every other house and sum them. Meaning subtract position of every house from Vito’s house and sum their distance.

I have provided Three commented codes below. First one uses STL Sort and doesn’t calculate absolute value for distance. Second one shows the use of Insertion Sort and calculates absolute value to find their distance. The last one uses vector to store data and STL algorithm to find nth element in an array. Here ( for this code ) the calculated nth element is the median.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

2
2 2 4
3 2 4 6

 


Output:

2
4

Code ( Without Calculating Absolute Value ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<cstdio>
#include<algorithm>

static int A[512];

int main(){
	register int n, m, i, j;
	scanf("%d", &n);

	while (n--){
        scanf("%d", &m);

        if (m == 1){
            /**
             * If only 1 input then no need to process
             * For 1 input the distance is always Zero
             */
            scanf("%*d");
            printf("0\n");
        }

        else{
            int dist = 0, median, key;

            for (i = 0; i < m; ++i)
                scanf("%d", &A[i]);

            /**
             * Sort the input using stl sort
             * Instead of using sorting algorithm, Try to implement Selection Algorithm to find Median in O(n) time
             */
            std::sort(A, A + m);

            /**
             * Find median dividing by two or shifting bit to left once
             * here, key is the value of median
             */
            median = m >> 1;
            key = A[median];

            /**
             * here, dist is the summation of distance of every house
             * Any value less than Median can subtracted from median will result in a positive value
             */
            for (i = 0; i< median; ++i)
                dist += key - A[i];

            /**
             * No need calculate for the median so start from (median + 1)
             * In case of value greater than Median, the Median must be subtracted from that value for positive number
             * Also by removing duplicates of median we may speed up the code
             */
            for (i = median + 1; i < m; ++i)
                dist += A[i] - key;

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

 

Code ( Insertion Sort ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>
#include<stdlib.h>

static int A[512];

int main(){
	register int n,m,i,j;
	scanf("%d", &n);

	while (n--){
        scanf("%d", &m);
        int dist = 0, median, key;

        for (i = 0; i < m; ++i){
            scanf("%d", &A[i]);
        }

        /**
         * Insertion Sort:
         * Two portions sorted and unsorted
         */
        for (i = 1; i < m; ++i){
            key = A[i];
            j = i - 1;

            /**
             * Compare every element with sorted portion ( elements to its left )
             */
            while (j >= 0 && A[j] > key){

                /**
                 * While comparing shift items to right until the comparison is false
                 */
                A[j + 1] = A[j];
                --j;
            }

            /**
             * When comparison is False or done, we found the sorted position for that element so we insert it in that position
             */
            A[j + 1] = key;
        }

        /**
         * Find Median value, left shift once is divided by Two
         */
        key = A[m >> 1];

        /**
         * Since elements after Median is bigger than Median So, we need to find absolute value of them
         */
        for (i = 0; i < m; ++i){
            dist += abs(key - A[i]);
        }

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

 

Code ( using vector & n-th element to find median ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>

using namespace std;

int main(){
    register int n, m, i, j;
    int key, num;
    vector<int> v;

    scanf("%d", &n);
    while (n--){
        scanf("%d", &m);

        if (m == 1){
            /**
             * If only 1 input then no need to process
             * For 1 input the distance is always Zero
             */
            scanf("%*d");
            printf("0\n");
        }

        else{
            /**
             * Input an a value and push it to vector
             */
            v.clear();
            for (i = 0; i < m; ++i){
                scanf("%d", &num);
                v.push_back(num);
            }

            /**
             * sort for median
             */
            nth_element(v.begin(), v.begin() + v.size()/2, v.end());

            /**
             * Get the value of median
             */
            key = v[v.size()/2];

            /**
             * Get distance of every value from median
             */
            int dist = 0;
            for (j = 0; j < i; ++j)
                dist += abs(key - v[j]);

            printf("%d\n", dist);

        }
    }
    return 0;
}
Advertisements

One thought on “UVA Problem 10041 – Vito’s Family Solution

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s