350 - Pseudo-Random Numbers

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

yellow
New poster
Posts: 9
Joined: Tue Oct 26, 2004 6:26 am

Post by yellow »

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

Post by wirjawan »

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

Post by yellow »

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

yellow
New poster
Posts: 9
Joined: Tue Oct 26, 2004 6:26 am

Any suggestion for improvement?

Post by 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
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia

Post by 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
New poster
Posts: 9
Joined: Tue Oct 26, 2004 6:26 am

Post by yellow »

yeah, i see what you mean now :D . Never know about map b4 :cry: , 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

Post by mohsincsedu »

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
Location: Dhaka, Bangladesh
Contact:

Post by 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!
Where's the "Any" key?

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

Thanks...

Post by mohsincsedu »

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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. 

Ami ekhono shopno dekhi...
HomePage

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

Post by mohsincsedu »

I got Acc.....

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

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

I think you should post your code or post some i/o generated by your code. Then I can help you.
Ami ekhono shopno dekhi...
HomePage

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 3 (300-399)”