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

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

Post by stcheung »

Thanks for the feedback. I don't think the original (multiplier*last + increment)%modulo will overflow because the spec says each number will only be at most 4 digits big and so the largest value this can get is 9999*9999 + 9999 which should be less than 2^31 for an int.

On the other hand, as Solaris pointed out in the same thread, I don't think we should always be counting from the beginning. Instead, it sounds like we should count from the first time the repeated pseudo-random number appears.

If you still have your code, try running it against the sample input and see if you get 501 as opposed to 500 for the 3rd case.

Anyways, I still get WA even if I change my program as recommended. Really strange...

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Code: Select all

        for(int i=0; i<modulo; i++) 
            firstAppearance[i] = -1;
What if L in input is larger than M and previously you've got the same?
Input

Code: Select all

9999 9999 9999 9999
9998 9998 9998 9999
Output

Code: Select all

1
1

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

Post by stcheung »

But the problem explicitly stated that "L will be less than M". I wonder if the input can actually be negative numbers since the problem only mentioned they are integers. But there are so many successful submissions which lead me to wonder if things can get that tricky. I feel that my solution is a standard one already haha.

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

350 RE??

Post by sakhassan »

I cant understand whats the wrong??? I haved complied it in VC more than 100 times :evil:
Last edited by sakhassan on Sat Mar 25, 2006 3:43 pm, edited 1 time in total.

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Re: 350 RE??

Post by sakhassan »

sakhassan wrote: DELETED............


I cant understand whats the wrong??? I haved complied it in VC more than 100 times :evil:
GOT AC... found my Runtime BUG!!!!!!!!!!!
Why doesnt make it clear in the problem !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
that what happen only if M = 0 ??????????????????????
would that be skipped or not???

wfuny
New poster
Posts: 5
Joined: Fri May 12, 2006 3:06 pm

if you get WA on 350 notice that.....

Post by wfuny »

L might bigger than M
add L=L%M in your code
I hope it can help you.

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

350 - WA

Post by abhi »

why wa . plz help me .

Code: Select all

# include <iostream>

# include <cmath>

# include <string>

# include <fstream>



using namespace std;



int main()

{

	long long int Z,L,I,M,i,n,cas=0;

	char arr[10000];

	//ifstream fin("testin");

	//ofstream fout("testout");

	

	while(cin>>Z>>I>>M>>L)

	{

		if(Z == 0 && I == 0 && M == 0 && L == 0)	return 0;

		

		cas++;

		int count = 0;

		for(i=0;i<10000;i++)	arr[i]=0;

		

		arr[L]=1;

		

		L=( (Z % M * L % M) % M + I ) % M;

		

		while(!arr[L])

		{

			arr[L]=1;

			count++;

			L=( (Z % M * L % M) % M + I ) % M;

			//cout<<L<<'\n';

		}

	

		cout<<"Case "<<cas<<": "<<count+1<<'\n';


	}

	

	return 0;

}	

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

Post by Jan »

Dont open a new thread if there is one already. Try posting in the existing threads.
Ami ekhono shopno dekhi...
HomePage

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

Post by abhi »

can anybody please explainto me why the output of
9999 9999 9999 9999
and
9998 9998 9998 9999
s equal to 1 and not 2

well first we have to generate a random number by using the formula
that gives us 0 for this input.
it is the 1st number in the chain.
using this as the seed and using the formula we get 0 again.
since 0 has already appeared we terminate the chain.
so it should be 2.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Yes, since 0 has already appeared we terminate the chain, not including the last 0 since it's already there. So the cycle contains only one number.

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Post by RC's »

I always get TLE for this problem. Does anyone know what test case might lead to it ?

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Post by RC's »

This is my code

Code: Select all

AC
This is my code, but it always gets TLE when submitted.
Does anyone know why ?
Last edited by RC's on Sat Jul 28, 2007 5:15 am, edited 1 time in total.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi »

avoid checking the already appeared values with looping..
try to do this in O(1) time...
Hint: all parameters will have no more than four digits..

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Post by RC's »

I still don't understand what you mean ?
Do you mean I save the z, i, m, l and the cycle of each case ?
Then it will consume a huge amount of memory.

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

Post by Jan »

What about keeping track of L only. Then try ayeshapakhi's hint. Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 3 (300-399)”