Horse Racing Duals puzzle discussion

Feel free to send your feedback or ask some help here!

2 Likes

Yop,

Je cherche à résoudre ce problème mais je n’y arrive pas. D’abord j’ai mis du temps à comprendre que le site n’envoie pas la valeur de n au début. Du coup ça me faisait n’importe quoi le reste de mon code x).

Ensuite j’ai essayé la méthode “brute force” qui consiste à tester toutes les valeurs 2 à 2. Ça marche bien sur les deux premiers tests mais ne donne pas de résultat sur le dernier. (Normal vous me direz)
Du coup je me suis dit qu’il fallait trier par ordre croissant d’abord puis parcourir une seule fois le tableau pour tester les couples adjacents. J’obtient le même résultat qu’avec la méthode brute force, même en utilisant un tri de type quicksort… (J’ai fait tri simple et tri à bulle avant)

Voila voila, si quelqu’un a une idée à me proposer, ça m’intéresse. Ça m’embête un peu d’être scotché comme ça par un facile :p.

Merci :smiley:

4 Likes

Salut, pour réussir le puzzle correctement, je te conseille de partir sur une liste chaînée de int, avec un tri par insertion.
En effet, à chaque scanf, tu insère le nombre dans la liste chaînée à la position où il doit se trouver.
C’est rapide dans le cas présent car le système de liste favorise l’insertion rapide et que la taille de liste est petite ( max 100000).

testé et approuvé.

7 Likes

I did, in C++, but I didn’t have any problem in particular with this test, so I don’t really know what your problem is. Horses in desorder is probably much bigger than horses in any order though, so maybe your solution times out with big files. Is your solution “bruteforce” ?

Hello,

I did it in python3, but I successfuly passed the many horses test too, with 99 999 elements… I passed that test in 0.15 second so almost instantly.
In my algo, I get all the horses, I sort them (O(nlogn)) and I compare elements by pair (O(n)).

Thanks for your answer.

11 Likes

Maybe sorting is too slow, is there such a thing as a set in python ? (constantly sorted collection, though I don’t the complexity of an insertion so it might not be helpful). Since you pass the “big” test, a time out would be weird though. Are you sure that all horses are considered ? With a little bad luck, the best dual can imply the first or last horse and you might ignore one.

1 Like

Strange thing, i just passed all the tests, 100% instead of 90%
The only thing I changed is that instead of comparing the difference between 2 adjacent elements with the current minimal difference previously found, I make a list of all differences between pairs and get the minimal out of that list.
It’s a bit slower than my previous algo but it works O_o

Anyway, thanks mate.

6 Likes

Hmm, that’s odd. Well if it works that way it’s alright then. It’s no fun if you know why it’s working XD.

You’re welcome

1 Like

Je l’ai fait en C egalement

I have the same problem.

Desorter, and horse tie can not pass. 88%
Any idea why, or how to check it ?

4 Likes

have any luck in this test? i’m stuck on this too $(

I just make 100%. Luckyly, in PHP, there is a sort($array) function, When is sortered, just compare position x+1 with x and get the minimal strenght distance.
If you use a language wich doen’t have that sort() function… we’ll it’s a some lines more.

2 Likes

It’s nothing much, actually. Simpliest solution is to read all the horses into massive, sort them by ascending/descending and compare elements by pair.

Althought, i couldn’t pass the many horses task with just that… Maybe it’s because i’ve used JS. Anyway, i had to optimize it to pass. I have used reference data type to build a linear structure and sort horses right away. Every horse in this structure remembers it’s own power, address of a weaker horse and adress of a stronger one. When new horse is being read, it travels along the structure, seeking a pair of horses, between which it can be inserted. After it settles between them, the program compares it’s strength with neighbours.

That way i could read, sort and compare horses in a single cycle. And i’ve got my 100%, at last :slight_smile:

3 Likes

The time is the key.

I used Java, and when I was resignated from Hashtable, and I use ArrayList - I can pass 100%.

2 Likes

I also had timing problems. PASCAL really had problems with the huge list, if i assumed it was not ordered (so i needed some kind of sort). Using C++ or Java shows no such problems, using the build in sort functions for lists.

2 Likes

Hi all,

I am a bit puzzled by this “game”, because it looks completely trivial from an algorithmic point of view: the answer is one line of code: min(diff(sort(V))), where V is the data vector. Depending on the language, you may have to write a bit of code for min(), diff(), and/or sort() – perhaps that was the funny part of the game, but some languages come with standard libraries that do these kinds of things.

Perhaps it could have been more interesting to ask for the ID of the horses, or something a bit more complicated.

Salut à tous, j’ai un point assez étonnant: je passe sans problème le test des chevaux dans le désordre (dans l’IDE)
puis au moment d’envoyer le code pour évaluation, le test des chevaux dans le désordre est le seul qui rate (sans raison vu que je trie les données de toute façon, donc reçues dans l’ordre ou pas… ça change rien)

serait ce un bug?


Hello, Something weird: I have all tests green during development part, but if I send the code to evaluation, the unordered Horses test fails (even if I got green on IDE Test…)

Bug?

2 Likes

What language is your solution in? All I can tell is that it isn’t C++ as the std::sort and std::min functions have a different set of parameters from your solution.

You misunderstood my point. The details of the solution depend on the language; obviously, but the point is that there is little coding challenge here.

All right, I take it that your proposal is actually pseudocode that basically outlines the solution strategy rather than an actual implementation in a particular language. As for the solution being trivial, well, this puzzle is among the easy ones. It would be challenging to students learning programming for the first time but not to coding veterans. :smile: