Horse Racing Duals puzzle discussion

j’ai exaaactement le même problème . Help?

Tried 2 diff languages, JS and PHP, same algorithm, but got 2 diff results. In JS I wasn’t able to pass 91%, in PHP I got 100%. After submitting the JS version it keep failing step 02.

Hi, I’m stuck in this problem with C#…
I never have to optimize my code like that :stuck_out_tongue:

I don’t know why it’s too slow, can you help me ?
Edit: Solved

P.S I ll delete my code after an hint :wink:

What’s wrong with :

int[] array = new int[N]; <-- You don’t need to resize it anymore after that
[…]
Array.Sort(array);

thank you, I thinked we can’t do that.
I still have an error but not because my sort is too long, I ll search why ^^

on the last test my answer is always 70 … What did I do wrong?

actuel= temp should be outside the if statement

It’s driving me crazy. Java implementation with TreeSet and single “for” loop, still does not validate test #6 (Horses in disorder). Anyone with a clue about this?

Use a TreeSet to store the Integer values. TreeSets are ordered automatically by their natural ordering. Furthermore, TreeSets do not allow duplicate entries; the add() method returns false if the value is already present in the set, which makes the rest of the process unneccessary (as equal Integers have a difference of 0 :wink: ).

Regarding the use of a regular for-loop to compare values: You might consider using a ListIterator as all the Pi[n] elements are in the for-loop scope until the end of the loop. Although I must admit that I haven’t tested the difference.

Good luck!

Hi Everyone ,

I am stuck on this puzzle and since it can’t access its varibles and other stuff, I am stuck at a whoop 90% coverage

Any help will appreciated.

Thank Suraj

Hey, i can’t pass the Horses in disorder test too and I can’t find anything wrong with my code. Any help is appreciated.
Python 3:

n = int(input())
s = set()

for i in range(n):
    p = int(input())
    s.add(p)
    
ss = sorted(s)
if len(ss) > 1:
    min = ss[1] - ss[0]
    for i in range(2,len(ss)):
        if ss[i] - ss[i-1] < min:
            min = ss[i] - ss[i-1]
    print(min)
else:
    print(0)

I’m getting the same thing.

You defined your initial input collection as a set() and not a list(). What are the two main differences between a set and a list?

I covered the case where there are only horses with the same power with if len(ss) > 1, I can’t think of any other case where having 2 or more horses with the same power would make a difference. Obviously I am missing something, but I have no idea what it is.

If you had 2 or more horses with the same power, what would their difference be? How would they appear in your set() before getting sorted?

len(ss) is going to tell you how many horses there are in the set you have converted to a sorted list. But it doesn’t tell you how many horses there are with the same value, if any.

Try creating a custom test case with a list of horses like 5, 6,8,6,3,1. What should the answer be?

1 Like

Why can’t I see the solutions from other members, they are all locked?

You need to solve the puzzle first.

1 Like

Hey guys any suggestions on how I can improve this code to make it run faster ? Thank you much appreciated !

import java.util.;
import java.io.
;
import java.math.*;

/**

  • Auto-generated code below aims at helping you parse

  • the standard input according to the problem statement.
    **/
    class Solution {

    public static void main(String args[]) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int [] array= new int[N];
    int D=100000,sub=0;
    for (int i = 0; i < N; i++) {
    array[i] = in.nextInt();

     }
     
     for (int j=0; j<(N-1);j++){
         for (int k=1; k<N;k++){
             if (array[j]>array[k])
              sub=array[j]-array[k];
             else
             sub=array[k]-array[j];
             if ((sub<D)&&(sub!=0))
             D=sub;
             }
         }
    
     System.out.println(D);
    

    }
    }

Sort the array so you don’t have 2 for loop.

Hello everyone I'm in need of a little help. I'm writing this in Java. At first I essentially used a brute force algorithm. first 2 cases are fine. Second case of course will time out. because i'm comparing every possible combination pair. So this leads to n + n+1 +n+2... (geometric sequence)=1/2n(n+1)=(n^2+n)/2 so is O(n)=n^2. with n=99999 will yield a very large number.. ok. no big deal

2nd method is to write pretty much a "quick sort" recursive algorithm function that sorts the data in order in average case n*log(n) time then there is only n-1 (hence linear time which is FAST) amount of pairs. first 2 cases are fine. now this time there is an out of memory heap error. I use 2 arrays (Not ArrayLists) where the function returns L * Pivot * R such that L and R are arrays and Pivot is one inger where the base cases are size 2 and 1 that swap positions. If I was writing this in C++ I would be able to "deallocate" my temporary Left and Right Arrays. However Java prides itself of no having to worry about heap memory and have been trouble trying to explicitly call the "garbage collector" at the end of the recursive function. Could anyone who was successful in java be so kind briefly help or tell me how they did it. Thank you in advance.

I think your solution might be too complex. Remember this is an easy puzzle. There is a O(n) solution. 5 lines will be sufficient.