[Community puzzle] Horse-hyperracing Hyperduals

Puzzles
#1

This topic is about the puzzle Horse-hyperracing Hyperduals.

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

1 Like
#2

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

N.S

#3

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
#4

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

#5

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

#6

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.

#7

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

#9 
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?

#12

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?

#13

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

#14

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

#15

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.

#16

I take it the current thread’s contents aren’t subtle enough?

#17

For me, not really :frowning:

#18

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