[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!


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.


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


Tests 8,9,12 and 13 (Horse OVER 9000!, Horse overflow, Peak Zexion and Roll JBM) seem to be bugged for Python3 and Python (both for IDE and validation). The code seems to be receiving no input at all; even as I try to output debug messages or simply print out the very first variables even before the horses are determined, nothing is outputted. I am very much confident that my code is correct.
I even went as far as to find existing code for another language (Ruby), the problem still remained.
Any ideas as to why this might be?

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?


As does “More horse”, which works as intended.


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: