delamath For those who are not using Java to solve this problem, the following is some related source code from the java.util.Random library. ;)
public synchronized void setSeed(long seed) { this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1); haveNextNextGaussian = false; } protected synchronized int next(int bits) { seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); return (int) (seed >>> (48 - bits)); } public int nextInt(int n) { if (n <= 0) throw new IllegalArgumentException("n must be positive"); if ((n & -n) == n) // i.e., n is a power of 2 return (int) ((n * (long) next(31)) >> 31); int bits, val; do { bits = next(31); val = bits % n; } while (bits - val + (n - 1) < 0); return val; }
karthik018 what could be the initial seed value ?
thexguy Test case #4 clearly violates the definition of the problem. In the description it says "The first line of input is a number N<10..." while Test case #4 provides exactly 10 test cases.
asailijhijr Yeah, it makes sense in the real world to check your inputs against the constraints given, you should throw an error in your code if someone else's code isn't functioning properly and that'll cause an error in your code. On the other hand, code that's as robust as possible and "just works" virtually no matter what without using too much memory has its own place in the scheme of things.
qwrtyuiuytres N<=10
zouhair_madid Hello, Is it even possible to solve this challenge in C++?
dayteed Nope, doesn't look like it. No matter what I have tried you cannot get the same sequences... The exercice should be constrained to Java...
zouhair_madid I want to see the other submissions, I will submit the code in JAVA and then check if someone was able to solve it in c++.
zouhair_madid I had to solve it in java, most solutions were in java or java8, few python and only 5 solution in c++, they had to implement the nextInt() of java by themselves. I hope this help!
BugshotGG May I ask you, which functions should we implement from the java.util.Random? I am lost, it has so many and I do not know which of these are useful etc.
Tuxdude Look at
setSeed(long)andnextInt(int)BugshotGG Should final AtomicLong seed; be a long long in c++?
code_eagle what about python?
Tuxdude Yep you can, but you need to implement a Random number generator exactly how
java.util.Randomdoes, both the seeding as well as generating the next random number
This is one thing which really puzzled me in this problem. The problem as it is, is not that hard to solve for people using Java or other languages which probably use the identical PRNG implementation.
I still have the question, whether the authors intended the problem to be solved this way or there is a better approach which is not obvious.
martin_kipfer I solved it using C++. Basically you just have to implement the Random class from java. It's a waste of time, but I did it as an exercise... It gave me headaches until I realized java and c++ don't use the same length for long integers...had to use long long.
sherifmowafy Couldn't help but notice that all the submitted codes for this problem do not match the current problem statement input, they had extra "start time" and "end time" inputs which makes the problem much easier. Has anybody solved this problem lately without these inputs?
pliptor I just finished solving it. I'm not sure if I'm missing something to not have a solution as short as others solving the old problem with "start time" and "end time".
Chandika Is it even possible to solve this challenge in Python?
YiSH Hi, I followed dfionov's suggestion and implemented a JavaRandom in python. It works on all test cases except the last one(No.4), which is a Time Limit Exceeded. I was stucked here. And I looked at the last test case. It is a ten single-seed input. So the execution time is just measuring the performance of that self-implemented PRNG, i.e. for 10 seeds, each generates about 20 randint(1000). Could use anyone's help. Thx. Maybe it would be better just relax the time limit on that last testcase of python.
denalilumma Would you share your code with me? I have a partially working Python 2 solution, but I am stuck.
codeharrier This challenge could be improved greatly. It assumes java, forcing everyone else to write the RNG themselves, and some of the test-case inputs aren't even numerical.
Gabbek I have no idea what to think of last two test cases as they are just random strings and there's no numerical input... it seems it's a fresh bug, as pretty much any solution doesn't have hard-coded solutions to the said two strings (most likely meaning that the bug had to appear lately)
amart42 Go to hell with it, please. If you constrain this challange strictly to Java and it's Random library, please do it explictly, not the implict way.
haveagr8day Is this problem still solveable? The past solutions all refer to timestamps which don't seem to exist in the input of the current version of the problem.
pliptor Yes, all testcases within 0.2 seconds in C++. It took me a while to crack it though.
tsite 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]
Edit:
Got the fourth test case to work; used lcm(1L<<20,1000) for the second loop instead of 1L<<20
[/spoiler]
mrussotto Yep, I just solved it the same way. Using the mod 125 part is necessary for that last test case.
kmdism Got every testcase with the exception of 4. Don't follow this recommendation. Could you please elaborate?
mrussotto 1000 = 125 * 8.
By the Chinese remainder theorem, if
X = Y (mod 1000),
then X = Y (mod 8)
and
X = Y (mod 125)
You can get all the other testcases by ignoring the second fact and concentrating on the first. To get that last one you need to use the second fact. tsite's idea about lcm(2^20, 1000) is the same (note that lcm(2^20, 1000) = 125 * 2^20).
Medes I think we can use just 1000 * 2^20, can't we?
However my Python 3 implementation fails with timeout error on testcase 4 even with this optimization :(
UPD: Rewrote my program to C++ and it successfully passed all cases.
yogesh_suthar I know C,Python 3 I don't know Java and C++ How can i solve this ?
Sort 48 Discussions, By:
Please Login in order to post a comment