350 - Pseudo-Random Numbers

[yellow]

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]

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]

oh yeah, i see it now, i will fix it tonite! Thanksss

[yellow]

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]

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]

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]

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

Why way outputs is:
500
220

[Solaris]

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!

[mohsincsedu]

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

[Jan]

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. 

[mohsincsedu]

I got Acc.....

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

[stcheung]

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]

I think you should post your code or post some i/o generated by your code. Then I can help you.

[stcheung]

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[10000];
    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]

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.