[Community puzzle] Horse-hyperracing Hyperduals

This topic is about the puzzle Horse-hyperracing Hyperduals.

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

1 Like

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


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

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

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?:confused:
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()]
for i in range(n):
    v, e = [int(j) for j in input().split()]

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 :slight_smile: )
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 :frowning:

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!