# [Community puzzle] Horse-hyperracing Hyperduals

This topic is about the puzzle Horse-hyperracing Hyperduals.

1 Like

Hey,
The statement is not clear. I did not get how to calculate with the seed.

N.S

if X(0) = 42424242 (you read that one from the input), then
X(1) = (1103515245 * X(0) + 12345) [mod 2^31] = 46815797804581635 mod 2^31 = 1443152643
and to obtain X(2), input X(1) in the formula.

1 Like

Hi, any hint for this?
data volume seems too huge to handle, or am I missing something?
I saw a solution in Ruby online, but it was timeout when I tried the test cases
Thanks

Or is there any way to view the solutions of the others and give up on this question?
Thanks

Iâ€™m able to solve all test cases with less than 10k horses with a â€śbrute forceâ€ť approach of testing all horses against each other. I assume my general approach is not the right one?
By reducing the number of horses to consider only the once that have a â€śmax diff in velocityâ€ť i am able to solve the one with 10k but not the ones with 100k horses test cases.

Same here!
I can solve 10k case, but 100k is just too much, lol
I found a solution online, but it is timeout also, so I suspect that they have changed the test cases/condition

``````n, m, x = [int(i) for i in input().split()]
print(n,m,x)
for i in range(n):
v, e = [int(j) for j in input().split()]
print(v,e)
``````

I get the input with that code. Are you aware that both â€śHorse OVER 9000â€ť and â€śHorse overflowâ€ť only give you a single line of input?

Awesome puzzle! I passed all tests 100% and also added multithreading to code. It uses all cores and does a grid acceleration for searching neighbors.

Where can I compare performance of my code to others? Will this be added to site?

@tugrul512bit Not on CG, but you can try here and here.

Thanks, I will test same grid structure on the 1second limit version, to see how it accelerates.

Okay, the trivial brute force solution timeouts at 3 of the test cases. (Most likely: as it was intended by the creator )
I am out of ideas now, so please: Any SUBTLE hint how to decrease time complexity from O((n+m)^2)? Thanks in advance.

I take it the current threadâ€™s contents arenâ€™t subtle enough?

For me, not really

I gave up 2.5 years ago.
Recently I am back to CG and picked it up again. This time I cracked it!
It is such a fun puzzle, cheers!

2 Likes