We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Someone else mentioned this already, but I agree that the time given for test case four should be increased a bit. My solution is able to pass all the test cases except for this one. I looked over the top scoring solution on the leaderboard to see how they dealt with test case 4. They used the given timestamps to brute force the seed which imo is a much less interesting way to solve the challenge than what I did.
My approach involved using the randomly generated numbers themselves to directly determine the seed, without relying on when these numbers were generated. The parameters of the linear congruence generator used by Java are necessary for this, included below:
unsigned long long m=1L<<48, a=0x5DEECE66D, a1=0xdfe05bcb1365, b=0xB, c=17;
m is the modulus, the lcg is given by state'=(a*state+b)%m
a1 is the modular inverse of a, ie state=a1*(state'-b)%m
c is the number of hidden bits used by the lcg, ie nextInt(n) returns (state'>>c)%n
And of course, the seed is given by state xor a
This should help with solving the challenge in a more interesting way. If you still have difficulty, see the spoiler below
PRNG Sequence Guessing
You are viewing a single comment's thread. Return to all comments →
Someone else mentioned this already, but I agree that the time given for test case four should be increased a bit. My solution is able to pass all the test cases except for this one. I looked over the top scoring solution on the leaderboard to see how they dealt with test case 4. They used the given timestamps to brute force the seed which imo is a much less interesting way to solve the challenge than what I did.
My approach involved using the randomly generated numbers themselves to directly determine the seed, without relying on when these numbers were generated. The parameters of the linear congruence generator used by Java are necessary for this, included below:
unsigned long long m=1L<<48, a=0x5DEECE66D, a1=0xdfe05bcb1365, b=0xB, c=17;
m is the modulus, the lcg is given by state'=(a*state+b)%m
a1 is the modular inverse of a, ie state=a1*(state'-b)%m
c is the number of hidden bits used by the lcg, ie nextInt(n) returns (state'>>c)%n
And of course, the seed is given by state xor a
This should help with solving the challenge in a more interesting way. If you still have difficulty, see the spoiler below
[spoiler]
http://pastebin.com/rA0vXju5
Edit:
Got the fourth test case to work; used lcm(1L<<20,1000) for the second loop instead of 1L<<20
[/spoiler]