## 350 - Pseudo-Random Numbers

Moderator: Board moderators

yellow
New poster
Posts: 9
Joined: Tue Oct 26, 2004 6:26 am
wirjawan wrote:maybe you want to at least push the generated random number into the vector?

and try to change
[cpp]
while(Z!=0&&I!=0&&M!=0&&L!=0)
[/cpp]

to
[cpp]
while(!(Z==0&&I==0&&M==0&&L==0))
[/cpp]

hope this helps
What do you mean "maybe you want to at least push the generated random number into the vector?" ? I already pushed the generated numbers into the vector!
Yeah, I tried while(!(Z==0&&I==0&&M==0&&L==0)) but there's no difference. I still get the wrong answer. Huhm!

wirjawan
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia
yellow wrote: What do you mean "maybe you want to at least push the generated random number into the vector?" ? I already pushed the generated numbers into the vector!
Yeah, I tried while(!(Z==0&&I==0&&M==0&&L==0)) but there's no difference. I still get the wrong answer. Huhm!
you pushed the first generated random number but not the second, the third, the fourth, etc...

Code: Select all

``````while(1)
{
randomNum=(Z*randomNum+I)%M;
if(Search(numProduced,randomNum))
break;
count++;
}
``````
you are always searching for vector<int> numProduced of size (caseNum).

another problem is that you never clear the numProduced vector. so the data from previous run will still be there.. so on the first run.. you will have 1 randomNum( let's say X), the second run.. you will have 2 randomNum (X and Y) // X is not suppose to be there hope this helps
..

yellow
New poster
Posts: 9
Joined: Tue Oct 26, 2004 6:26 am
oh yeah, i see it now, i will fix it tonite! Thanksss yellow
New poster
Posts: 9
Joined: Tue Oct 26, 2004 6:26 am

### Any suggestion for improvement?

here is my code, any suggestion for improvement is appreciated:
#include <iostream>
#include <stdlib.h>
#include <vector>

using namespace std;

bool Search( vector<int> numProduced, int num);
int main ()
{
int Z,L,I,M;
int caseNum=1;
vector<int> numProduced;

cin>>Z>>I>>M>>L;

while(!(Z==0&&I==0&&M==0&&L==0))
{

int randomNum;
randomNum=(Z*L+I)%M;
numProduced.push_back(randomNum);
int first= randomNum;
int count=1;
while(1)
{
randomNum=(Z*randomNum+I)%M;
if(Search(numProduced,randomNum))
break;
numProduced.push_back(randomNum);
count++;
}

cout<<"Case "<<caseNum++<<": "<<count<<endl;
numProduced.clear();
cin>>Z>>I>>M>>L;
}

return 0;
}

bool Search( vector<int> numProduced, int num)
{
int lenght = numProduced.size();
for(int i = 0; i < lenght; i++)
if(num==numProduced)
return true;
return false;
}

wirjawan
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia
1.
[cpp]
numProduced.push_back(randomNum);
int first= randomNum;
int count=1;
while(1)
{
randomNum=(Z*randomNum+I)%M;
if(Search(numProduced,randomNum))
break;
numProduced.push_back(randomNum);
count++;
}
[/cpp]
this will give you a WA iff the number doesn't start at the first place..
ex. the sequence is 2 4 5 6 7 4
your count = 5 (at 7), then when you check for 4 in your search function, it returns true and you answer is 5 (this is not correct) it should be 4.

2. don't use vector to store the generated randomNumber.. searching through it is a pain (linear search), since the order of number is not sorted. my suggestion is use map<int,int> first is the randomNumber, second is the position.
so from my example above 2 4 5 6 7 4, you will have
(2,0) (4,1) (5,2) (6,3) (7,4) and when u get a 4, you find 4 with a position of 1, at this point you already have 5 numbers in your map. so 5 - 1 = 4 (which is the correct answer)

hope this helps
..

yellow
New poster
Posts: 9
Joined: Tue Oct 26, 2004 6:26 am
yeah, i see what you mean now . Never know about map b4 , gotta check it out now

PS: Thank you so so much. Yeah, you really helps me out

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

### 350 - Pseudo-Random Numbers

Plz Explain for the inputs:
9111 5309 6000 1234
1079 2136 9999 1237

Why way outputs is:
500
220

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
May be u would like to have a better look at the following part of the problem
But be careful: the cycle might not begin with the seed!
Where's the "Any" key?

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

### Thanks...

Plz Explain:
I donot understand What they want!!!:(

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
You are given Z, I, M, L. You have to find how many random numbers you can make.

Code: Select all

``````Suppose..
Z= 7
I= 5
M=12
L= 4

Current Random number | Next random number (ZxL+I)%M
4           |          9
9           |          8
8           |          1
1           |          0
0           |          5
5           |          4

Now you got 4 again. So, the length is 6. And thats the output.

``````
Ami ekhono shopno dekhi...
HomePage

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:
I got Acc.....

Thanks Jan & Solaris............... :)

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:
Does anyone have more test data beyond what's in the problem description? I keep getting WA for this simple problem and I can't figure out why. (I have also read all other threads related to this problem already) Thanks.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Ami ekhono shopno dekhi...
HomePage

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:
Basically for each pseudo-random number, I keep track of when it was first seen with firstAppearance. Then each time I generate a new term I check this array to see if it was encountered before and if so I can break out of the while loop. Thanks for taking a look at it.

Code: Select all

``````#include <iostream>
#include <stdlib.h>
#include <string>

int main() {
int multiplier, increment, modulo, last;
int casenum = 0;
int firstAppearance;
while(true) {
casenum++;
cin >>  multiplier >> increment >> modulo >> last;
if(multiplier == 0 && increment == 0 && modulo == 0 && last == 0)
break;
for(int i=0; i<modulo; i++)
firstAppearance[i] = -1;

int counter=0;
while(true) {
if(firstAppearance[last] >= 0) {
counter = counter - firstAppearance[last];
break;
}
firstAppearance[last] = counter;
last = (multiplier * last + increment)%modulo;
counter++;
}
cout << "Case " << casenum << ": " << counter << "\n";
}
return 0;
}
``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Change the following..

Code: Select all

``````        while(true) {

last = ((multiplier%modulo) * (last%modulo) + increment%modulo)%modulo;
/* last = (multiplier * last + increment)%modulo; you can get overflow error*/
if(firstAppearance[last] >= 0) {
break;
}
firstAppearance[last] = 1;
counter++;
}``````

I think you haven't understood the problem clearly. You should 1st generate a random number and then start calculating. If you get a number which was found previously you should break the loop and print the counter.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage