HORSES - Editorial

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

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

GOOD SOLUTION

1 Like

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

YEs ITs A Truly gREAT sOLUTION

1 Like

I did it by memoization and heap sort.

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

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.

Nice Explanation. +1 to the editorialist.

3 Likes

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;

}

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

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!! :slight_smile:

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;
}

}

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?

@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.

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))

enter code here
#include <stdio.h>
int main(void) {
int testcase, length, k = 0;
scanf("%d", &testcase);
while (k != testcase) {
scanf("%d", &length);
int number[100];
for (int m = 0; m < length; m++)
scanf("%d", &number[m]);
for (int i = 0; i < length; i++) {
for (int j = i; j < length; j++) {
if (number[i] > number[j]) {
int a = number[i];
number[i] = number[j];
number[j] = a;
}
}
}
int diff = number[1] - number[0];
printf("%d\n", diff);
k++;
}
return 0;
}

I did exactly what it says here yet I am getting wrong answer.
My solution can be found at CodeChef: Practical coding for everyone
Please tell me what’s wrong in my solution.

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

1 Like

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

Even the setters solution is giving time limit exceeded and testers solution is giving run time error SIGABRT . But on submission it accepts answer as 100% correct.What is this nonsense? I wasted my entire day on this.

When you will submit your solution with this approach, it will show time limit exceeded. But when you will submit it, it will be ACCEPTED. Don’t know what the problem is. Maybe different server speed or what else?