HORSES - Editorial

editorial
, ,
21

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

1 Like
22

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

23

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.

24

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?

25

No, you cannot. It will give wrong answer.

27

#pls help me i wrote a code but dont know whats wrong in this.It’s working fine for me…
https://www.codechef.com/viewsolution/25427928

28

Whats wrong in this code, showing wrong answer
(CodeChef: Practical coding for everyone)

29

#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–>0)
{
int n,a[5000],temp,first=0,second=0;
cin>>n;
for(int i = 0; i<n ; i++)
{
cin>>a[i];
}
for(int k = 0; k< n-1; k++) {
for(int i = 0; i < n-k-1; i++) {
if(a[ i ] > a[ i+1] ) {
temp = a[ i ];
a[ i ] = a[ i+1 ];
a[ i + 1] = temp;
}
}
}
second = abs(a[1]-a[0]);
for(int i=2;i<n;i++)
{ first=abs(a[i]-a[i-1]);
second=min(second,first);
}
cout<<second;
}
}

I am getting wrong answer for this code.Can anybody help?

32

can anyone tell me whats wrong

#include
using namespace std;
void sort(int p,int n);
int min(int p,int n);
int m=100000010;
int main()
{
int t,i;
//cout<<“Enter the value of t:”;
cin>>t;
while(t)
{
int n;
//cout<<“Enter the value of n:”;
cin>>n;
int a[n],p=a;
for(i=0;i<n;i++)
{
//cout<<“Enter value at index “<<i<<”:”;
cin>>a[i];
}
sort(p,n);
cout<<min(p,n);
t–;
}
}
void sort(int p,int n)
{
int i,j,temp;
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if((p+j)<(p+j+1))
{
temp=(p+j);
(p+j)=(p+j+1);
(p+j+1)=temp;
}
}
}
}
int min(int p,int n)
{
int i,j,temp;
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(((p+j)-(p+j+1))<m)
{
m=((p+j)-*(p+j+1));
}
}
}
return m;
}

33

I too thought so? but i got wrong answer, why??

34

why is taking the difference between second and first element after sorting, wrong? can anyone tell me the test case where that fails?

35

can anyone please tell me what is wrong in my code:-

#include <stdio.h>

void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}

int partition(int a[], int start, int end) {
int pivot = a[end];
int i = start-1;
int j;

for(j=start; j<=end-1; j++) {
if(a[j]<=pivot) {
i=i+1;
swap(&a[i], &a[j]);
}
}
swap(&a[i+1], &a[end]);
return i+1;
}

void quicksort(int a[], int start, int end) {
if(start < end) {
int q = partition(a, start, end);
quicksort(a, start, q-1);
quicksort(a, q+1, end);
}
}

int main() {
int T, N ;
scanf("%d" , &T);
while(T–)
{
scanf("%d" , &N);
int i;
int a[N];
for(i = 0 ; i<N ; i++)
{
scanf("%d" , &a[i]);
}

    quicksort(a , 0 , N-1);
   
    
    int min = a[1]-a[0];
    for(i = 1 ; i<N-1 ; i++)
    {
        if(min>a[i+1]-a[i])
        {
            min = a[i+1]-a[i];
        }
    }
    
    printf("%d" , min);
}

return 0;

}

36

should be
i<n

37

My program gives the correct output to the sample input but gives a WA when I submit it. I used the inbuilt sort function of C++
Here is the link to my code
https://www.codechef.com/viewsolution/36180293
Can someone please help me to find out what’s wrong with my code

38

Not on my machine, it doesn’t :slight_smile:

[simon@simon-laptop][15:28:01]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling snehalmahima-HORSES.cpp
Successful
[simon@simon-laptop][15:28:05]
[~/devel/hackerrank/otherpeoples]>echo "1                                                       
5
4 9 1 32 13" | ./a.out
0

The reason is that you are not initialising the pre array, so its initial contents are undefined.

Then, in the loop:

         for(int i=1;i<n-1;i++)
            pre[i-1]=arr[i]-arr[i-1];

you are only filling in the first n - 2 values of pre, leaving its final two values uninitialised.

The sort(pre,pre+n-1); sorts the first n - 1 elements of pre, which includes one uninitialised element, leaving the sorted version of pre undefined.

2 Likes
39

I fixed the possible bugs. It works now

for(int i=1;i<=n-1;i++)
pre[i-1]=arr[i]-arr[i-1];

and sort(pre,pre+n-1)

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

Thanks for the suggestions :blush:

1 Like
40

Can someone please explain the proof in a bit more detail.

41

what is wrong with this code? I am getting Wrong Answer

#include <bits/stdc++.h>

using namespace std;

long long arr[5001];
int main() {
	int t;
	cin >> t;
	while(t --) {
		int n;
		cin >> n;
		for (int i = 0; i < n; i ++) {
			cin >> arr[i];
		}
		sort(arr, arr+n);
		long long ans = INFINITY;
		for(int i = 1; i < n; i ++) {
			ans = min(ans, arr[i] - arr[i - 1]);
		}
		cout << ans;
	}
	return 0;
}
1 Like
42

Consider the test input:

2
5
4 9 1 32 13
5
4 9 1 32 13
2 Likes
43

Output is:
3
3
Seems Correct to me.