HORSES - Editorial

gamabunta · September 11, 2012, 3:10pm

PROBLEM LINK:

DIFFICULTY

CAKEWALK

PREREQUISITES

PROBLEM

You are given a list of integers. Find the pair of integers whose value is closest among all the pair of integers in this list.

QUICK EXPLANATION

You can sort the integers and then consider all (N-1) consecutive pairs of integers. One of these pairs is surely the closest. Their difference is the answer.

EXPLANATION

First, let us consider the complexity of a naive brute force solution.

If we consider each possible pair of integers, we will end up with an O(N*N) solution - given there are N integers.

For a file with T test cases, the over all complexity is O(N\*N\*T). This will mean about 250 million calculations. This will be too slow to pass within 3 seconds on the CodeChef servers.

As with any brute force solutions, this solution is doing a lot of extra work. It is considering the difference between several pairs of integers that can be ignored.

Consider the case where the list of integers - we will call it A - is sorted.

Lemma:

The closest pair of integers is one of the N-1 pairs, which appear consecutively in A

Alternately, if A[i] and A[j] are the closest pair of integers, then i is equal to j-1.

Proof:

We will use Proof by Contradiction.

Let us assume that the pair of closest integers is A[i] and A[j] and i < (j-1)

Consider A[k] ∀ k > i and k <= (j-1)

Since A is sorted, A[k] >= A[i] and A[k] <= A[j]
From (2) we get A[k] - A[i] >= 0
Adding A[j] - A[k] on both the sides in (3) we get
A[j] - A[i] >= A[j] - A[k]

Hence, A[k] and A[j] are either a better or an equally good choice for pair of closest integers.

This means, at least one of the assumptions is false.

Either A[i] and A[j] are not the closest integers
Or, i is equal to j-1

Approach:

Now, we just need to sort the numbers efficiently and consider the consecutive pairs in one parse. Sorting can be done in place using the Quick Sort algorithm, which sorts in O(N log N) time. Quick Sort is available in the standard library in almost all languages.

The rest can be resolved in a single parse. The code will look like

Sort A
minval = infinity
for i = 1 to N-1, inclusive
	if minval > A[i] - A[i-1] then minval = A[i] - A[i-1]
print minval

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here

kuruma · September 11, 2012, 4:00pm

This is probably one of the best “easy” problems I’ve ever seen, and I was wondering if I could use it in my future classes where I will be teaching computer science combined with mathematics and the use of the Microsoft spreadsheet Excel…

It shows how a brute force works and how easy it is to code it, along with serving to introduce nested loops But, at the same time it also shows how inneficient it is and how to overcome it! (On this case by understanding that the shortest pair has to be one formed by consecutive elements of the sorted array…

Absolutely Perfect!!!

Sumudu · September 11, 2012, 4:01pm

I also thought this was a quite nice “easy” problem when I read it

rohit29 · September 11, 2012, 6:13pm

But how come my brute force solution got accepted ??!
i was feeling like hell that how can my brute solution work but it did cross my mind to sort it but couldn’t proceed further !

gamabunta · September 11, 2012, 7:20pm

It is unfortunate that brute force got accepted. The expected complexity for an approach to get accepted was an O(n log n) sort.

vickycod · October 7, 2014, 5:49pm

#include<bits/stdc++.h>
using namespace std;

int main() {
// your code goes here

int t,n,i;
long long a[5000];

cin>>t;

while(t--)

{

	cin>>n;

	for(i=0;i<n;i++)

	{

		cin>>a[i];

	}

	sort(a,a+n);

	int ans=a[1]-a[0];

	int min=0;

	for(i=2;i<=n;i++){

		min=a[i]-a[i-1];

	if(ans>min)

	min=ans;

	}

	cout<<min<<endl;

}

return 0;

}

this code give me correct o/p on ideone but here wrong answer please help me…

sukhada11 · September 28, 2015, 11:35pm

My program giving me correct answer and i think it is logically correct as well but i am getting WA.Please Help

   https://www.codechef.com/viewsolution/8273802

vjs17 · September 29, 2015, 1:19pm

https://www.codechef.com/viewsolution/1307412

GOOD SOLUTION

shashank2543 · September 29, 2015, 1:23pm

https://www.codechef.com/viewsolution/1307412

YEs ITs A Truly gREAT sOLUTION

aijajkhan · May 31, 2016, 11:37pm

I did it by memoization and heap sort.

jeevan17 · September 3, 2016, 10:13pm

My program giving me correct answer and i think it is logically correct as well but i am getting Wrong Answer.

Please Help

heres the link

My code link, Plz click this and help me

or u can copy paste this link

https://www.codechef.com/viewsolution/11337353

cyclicfunction · October 27, 2016, 11:32am

It might just be my wrong implementation of your idea but quicksort is not the best sorting method in this case. The input must be taken space by space so the set up for insertion sort is already in place. This is ofcourse taking into consideration that at max only 5000 numbers are to be sorted.

Insertion Sort (Time ~ 0.29s)

#include <stdio.h>
 
int main(void)
{
	int T;
	scanf("%d", &T);
 
	while(T--)
	{
		int N;
		scanf("%d", &N);
 
		long A[N];
		for(int i = 0; i < N; ++i)		/* insertion sort */
		{
			scanf("%li", &A[i]);
 
			int j = i - 1;
			long key = A[i];
 
			while(j >= 0 && A[j] > key)
			{
				A[j + 1] = A[j];
				--j;
			}
 
			A[j + 1] = key;
		}
 
		long minima = A[1] - A[0];
		for(int i = 2; i < N; ++i)
		{
			minima = A[i] - A[i - 1] < minima ? A[i] - A[i - 1] : minima;
		}
 
		printf("%li\n", minima);
	}
 
	return 0;
}

Quicksort (Time ~ 0.53s)

#include <stdio.h>

void swap(long* a, long* b)
{
    long t = *a;
    *a = *b;
    *b = t;
}

int partition (long arr[], int low, int high)
{
    long pivot = arr[high];
    int i = (low - 1);
 
    for (int j = low; j < high; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(long arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);
 
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main(void)
{
	int T;
	scanf("%d", &T);

	while(T--)
	{
		int N;
		scanf("%d", &N);

		long A[N];
		for(int i = 0; i < N; ++i)		/* insertion sort */
		{
			scanf("%li", &A[i]);
		}

		quickSort(A, 0, N - 1);

		long minima = A[1] - A[0];
		for(int i = 2; i < N; ++i)
		{
			minima = A[i] - A[i - 1] < minima ? A[i] - A[i - 1] : minima;
		}

		printf("%li\n", minima);
	}

	return 0;
}

People have done it in ~0s time like this but I have no clue how that works.

deep9539 · October 27, 2016, 1:49pm

Nice Explanation. +1 to the editorialist.

atul_1511 · November 2, 2016, 8:13pm

why is this code giving run time error?
#include
using namespace std;
int main()
{
long int t,i,j,k,d1,d2=10000000000,s[1000],n,p;
cin>>t;
for(i=0;i<t;i++)
{
cin>>n;
if(n>5000 || n<2)
{
return 0;
}
else
{
for(j=1;j<=n;j++)
{
cin>> s[j];
if(s[j]>1000000000 || s[j]<1)
{
return 0;
}
}
for(j=1;j<=n;j++)
{
for(k=j+1;k<=n;k++)
{
if(s[k]>=s[j])
{
d1=s[k]-s[j];
}
else
{
d1=s[j]-s[k];
}
if(d1<=d2)
{
d2=d1;
}
}

		}
	}
	cout<<d2;
}
return 0;

}

naruto323 · January 29, 2017, 8:39pm

https://www.codechef.com/viewsolution/12667766

This logic is correct but still getting the wrong answer
i sorted it then i found the min value as mentioned but still im getting WA

vijju123 · January 30, 2017, 11:07am

The problem with your answer is simple @naruto323

Look, you assigned all the elements of array a value of “0” at start.

When I entered the sample test case

1
5
4 9 1 32 13

You know what I got?

Output - 0

Problem is that you lets say, I input 3 numbers, 1,8,5. The minimum difference is of course, 3,(8-5) but in your code, after these 3 elements, the rest of the elements are assigned a value of 0. And since 0-0 is 0. And 0 <3 , so output is 0.

Now you will say, “I ran the loop only till n elements so how did 0 came in the picture?”

That’s cause honey, you SORTED THE ARRAY TOO!!

Meaning, during sort, the 1,8,5 are pushed as the last 3 digits (4999, 5000 and 4998th indexes) and all indexes from start to end are 0. Your array looks like this after sorting-

{0,0,0,0,0…1,5,8}

I suggest either iterate from back or add some condition like (a[I] != 0 && a[I-1]!=0) to fix it.

Hope it helped!!

kartikcool712 · July 7, 2017, 3:04am

Any clue as to why this is WA? Example test case gives the right answer and AFAIK it must give correct answer for any case. Help appreciated.I know I can just use sorting, just wanted to know why was this wrong.

public static void main(String[] args) {
    int tCase,horsesN;
    int[] s;
    Scanner in=new Scanner(System.in);
    tCase=in.nextInt();
    while(tCase>0){
        horsesN=in.nextInt();
        s=new int[horsesN];
        for(int i=0;i<s.length;i++){
            s[i]=in.nextInt();
        }
        System.out.println(check(s));
        tCase--;
    }
}

public static int check(int[] arr) {
    int max,min,diff1,diff2,secMax,secMin;
    secMax=secMin=max=min=arr[0];
    for(int i=0;i<arr.length;i++){
        if(arr[i]>max){
            secMax=max;
            max=arr[i];
        }
        else if(arr[i]>secMax&&arr[i]!=max)secMax=arr[i];
                
        if(arr[i]<min){
            secMin=min;
            min=arr[i];
        }
        else if(arr[i]<secMin&&arr[i]!=min)secMin=arr[i];
    }
    diff1=max-secMax; diff2=secMin-min;
    if(diff1>=diff2) return diff2;
    else return diff1;
}

}

vidhi2402 · October 24, 2017, 1:09pm

Can’t this problem be solved by finding minimum and second minimum number and printing thier difference and if
repition of number is there printing zero?

shivtelo · October 24, 2017, 2:01pm

@vidhi2402 You seem to have misunderstood the question.

Example Input Array: 2 9 8

Your Output: 6

Expected Output: 1

Because 8-2=6 which is according to you, but 9-8=1 is the correct answer.

prince54shaw · July 31, 2018, 11:33pm

what is wrong with this code

dif = []
for i in range(int(input())):
n = int(input())
l = list(map(int,input().split()))
l= sorted(l)
for k in range(n-1):
dif.append(abs(l[k+1]-l[k]))
print(min(dif))