This topic is about the puzzle Horse-racing Hyperduals.
Feel free to send your feedback or ask some help here!
I see several minor issues in this puzzle.
-
Stub has horse parameters as “s, e”, while the description talks about Vi and Ei.
-
It has D >= 0 but there is not a single case or validator where D == 0.
-
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)
- 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]
- 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:
- this is
bothoff-topic hereand a big spoiler there. Don’t do that. - well, suggest a change then
- 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