# [Community puzzle] Horse-racing Hyperduals

This topic is about the puzzle Horse-racing Hyperduals.

I see several minor issues in this puzzle.

1. Stub has horse parameters as â€śs, eâ€ť, while the description talks about Vi and Ei.

2. It has D >= 0 but there is not a single case or validator where D == 0.

3. Iâ€™m not sure if it is an issue or by design, but this puzzle is easily solved with O(n2) (not even O(nlog(n)) ) brute force (even in Python), no optimization algo is actually required. Maybe number of cases should be much higher, as in the original HRD?

As far as I remember, a harder version without brute force is on the rails.

Good catch! Itâ€™s changed from â€śspeedâ€ť to â€śvelocityâ€ť mid-term, to avoid more unneeded confusion between _S_trength and _S_peed. Iâ€™ve just corrected the stub. (I never use the stubs, so indeed I seldom think of them)

1. Yeah, I donâ€™t care enough, you can add one if you want, but I canâ€™t think of a single algorithm where it would make a difference, so WTH. Itâ€™s an indication to hint to a datatype, not an edge-case.

[Itâ€™s easy]

1. As nicola hinted, harder one coming up: https://www.codingame.com/contributions/view/46851c0fe09e7e9725ad1f768d091234bf9
More seriously, originally I wrote it as a reaction to the constant flow of people chiming up on the various chat channels saying â€śI donâ€™t understand how itâ€™s even possible to do it in bashâ€ť. So now we have a harder (by some measure) version of the puzzle that still is solvable in bash. Pure bash, too.

Canâ€™t offer you a dedicated achievement if you do solve it in bash, though; sorry!

1 Like

Well, my initial stupid O(n**2) algo that compared each horse to each another horse actually would stumble with such a case because it specifically had to exclude identical horses. Unfortunately, I cannot add it myself, probably because of my low 24th level.

You mean you excluded identical horses by excluding a difference if it was zero?!

Yes.[quote=â€śJBM, post:6, topic:2264, full:trueâ€ť]
You mean you excluded identical horses by excluding a difference if it was zero?!
[/quote]

Yes, in that draft solution I did so.

Well, ok, now you canâ€™t do that anymore.

(but you should know better )

I donâ€™t know much about computational complexity, but I wonder if my solution is O(n) and works in the general case.

I gave the link to the hard version in an earlier post. Just try it out there and youâ€™ll see! (youâ€™ll have a bit of adjusting to do to get the large inputs in, though)

Iâ€™ve just lost a bit of my soul here.

Wasted hours notwithstanding, Iâ€™ve really lost a big chunk of lifeblood here.

Donâ€™t understand what you mean JBM

1 Like

I just realized how much harder than I thought this puzzle was. In a depressing way.

Any approver mind if I update it to â€śVery Hardâ€ť?

5 Likes

After all, your gravity tumbling is still rated â€śmediumâ€ť and it requires to code some kind of big integer library besides a bit of googling

The problem I see with this series of puzzles is, the brute foce approach works very well in C++ until the very last one that uses pseudo-random generator to increase the input size. Maybe thatâ€™s not the case in slower languages though.

Ok, so:

1. this is both off-topic here and a big spoiler there. Donâ€™t do that.
2. well, suggest a change then
3. strictly speaking, neither googling (ask Stilgart) nor bigints are necessary.

More â€śseriouslyâ€ť, I didnâ€™t agree with the linearity of the community puzzle scale since the day it was implemented, have always considered theyâ€™d be better rated simply as codingamersâ€™ success rate, and have published all of my puzzles as Medium difficulty ever since. After all, they canâ€™t be that hard if even I could manage them!

Ok sorry, Iâ€™ve edited the spoiler out.

As for the big ints, they seem to have been the tool of choice for about every solution I saw. Too bad not every language has them as builtins, eh?
And frankly I donâ€™t remember ever seeing the theorem the puzzle is based on in my 5 years of engineering studies. I suppose you could re-discover it if youâ€™re very smart or very lucky, but for more limited mortals I guess Google might come in handy here.

Now that I dared tackle more than medium puzzles, I realize the difficulty level is indeed all over the place. I agree it can prove more misleading than helpful sometimes.

Well, sorry, theyâ€™re still not needed. The entire puzzle can be done in linear time using no arithmetic higher than 8-bit. (actually even less, but youâ€™d be hard-pressed to find ops to do that)

Itâ€™s a multi-layered puzzle: if youâ€™re reaching out for the bigints, well itâ€™s a cop-out that does work, but youâ€™re missing part of the point. In related news: itâ€™s not octal just to be a nuisance.

From what I heard, thatâ€™s not strictly needed either. Many did without, and we still get a message every month complaining why the puzzle has to make everything more complicated with defective tumblers.

Well now Iâ€™ve read it all!

Added a dedicated test case for @MyStackOverflows yesterday. And fixed it today, because apparently I shouldnâ€™t do that so late in the night.

Still seems eerily similar to MMMAAANNNâ€™s issue, but who am I to judge. Enjoy the forced diversity, yâ€™all!

1 Like

Hello,

There is an issue in the test â€śAll your horse are belong to usâ€ť.

At the validation phase I have 100% But the thing is that my code doesnâ€™t pass this test â€śAll your horse are belong to usâ€ť.

I cannot upload the image as it is said that I am new user.

Could you please look into this issue? I will share my code.

``````   import sys
import math
from operator import itemgetter

def Sort(tup, i):
return(sorted(tup, key = lambda x: int(x[i]), reverse = True))

def findDist(tup):
min_ds = 999999999
for i, (v, e) in enumerate(tup, start=0):
if i + 1 < len(tup):
dist = abs(tup[i+1][0] - v) + abs(tup[i+1][1] - e)
if dist < min_ds:
min_ds = dist
return min_ds

tup = []
n = int(raw_input())
for i in xrange(n):
v, e = [int(j) for j in raw_input().split()]
tup.append( (v, e))

tup = Sort(tup, 0)
dist1 = findDist(tup)
tup = Sort(tup, 1)
dist2 = findDist(tup)

if dist1 < dist2:
print dist1
else:
print dist2``````