408 - Uniform Generator

[CDiMa]

Now more interstinglly if I change
[cpp] if( step % i == 0 && mod % i == 0)[/cpp]

Since the point is searching for uniform distribution you should expect to get a lot of inputs with relative primes. If step and mod are relative primes the loop will iterate step-3 times.
Step may be up to 100000.

to:
[cpp] if( step % i == 0 || mod % i == 0)[/cpp]

this will loop up to step only if both step and mod are prime otherwise at worst it will iterate min(sqrt(step),sqrt(mod)) times. sqrt(100000) is 316...

or:
[cpp]if( step % i == 0)[/cpp]
or:
[cpp]if( mod % i == 0)[/cpp]

both will loop up to the size of the variable if prime or up to its square root in the worst case otherwise.

it dosen't time out any more and finshes in less than a second
Of course the code dosen't output the correct answer then.
So what is wrong?

If judge's input is big enough and contains a lot of big relative primes it is easily seen that with the first test it may run >10x slower...

Ciao!!!

Claudio

[Dani Rodrigo]

I think that I that a choice is a "Good Choice" if, and only if,
gcd(mod,step)==1.
Is this correct? Help plezz
Here is my code:

#include <stdio.h>

int mcd (int x, int y)
{
int residuo, aux;
if (y>x)
{
aux=x; x=y; y=aux;
}
while ( residuo!=0 )
{
residuo = x % y;
x = y;
y = residuo;
}
return (x);
}

void main ()
{
int step, mod;

while ( scanf ("%d%d%*c", &step, &mod) == 2 )
{

if ( mcd(step,mod) == 1 )
printf ("%10d%10d Good Choice\n\n", step, mod);
else
printf ("%10d%10d Bad Choice\n\n", step, mod);
}
}

[Piotrek Mazur]

Hmm... Try to change this lines:
[c]/* ... */
while ( scanf ("%d%d%*c", &step, &mod) == 2 )
/* ... */
printf ("%10d%10d Good Choice\n\n", step, mod);
else
printf ("%10d%10d Bad Choice\n\n", step, mod);
/* ... */[/c]
1) scanf - there is no need to read '%*c' <- this * is a bug? Any way you don't read this %*c - no pointer for that in variables list
2) you will have P.E. I think, after %10d%10d there is more than one space - %10d aligns number to left, this means the extra spaces will be added on left side of number, on right side there is 4 spaces.

[jaracz]

Hi I don't know why i'm gettin PE....

Anyone do?
here's a part of my code

Code: Select all

while(scanf("%d%d",&step,&mod)==2)
{
    printf("%10d%10d%15s\n\n",step,mod,choice(step,mod));
}

Regards!

[shamim]

I think the "choice" should be left justified.

[jaracz]

Yes I changed it a little bit
there was one unnecessary space

now is good

Code: Select all

while(scanf("%d%d",&step,&mod)==2)
{
    printf("%10d%10d    %s Choice\n\n",step,mod,choice(step,mod));
}

where "choice" returns "Good" or "Bad"
thx man, got AC:>

[xish]

I solve this problem using Ad Hoc algorithm and got 1.041 second, I feel there is a faster algorithm to solve it. But I don't know, is there any faster algorithm to solve the problem?

[nukeu666]

unless you can make a faster form of seed=(seed+x)%y or can correlate the inputs to possible output...i dont hink you can decrease the time too much as for each mod value, it'll have to parse the whole 0-mod once

one possible improvement is checking if gcd of step and mod is 1
fastest way for this would be the eular's algorithm(or was it euclid's algorithm)

[genti]

Hi, I tried to post my program twice, once I got WA then after adding the delete [] array instruction to free memory I got Runtime Error. Anyone can help and tell me what's wrong with this code? I've gone through all the test cases I could find here, and my program got them right. Is there anything wrong with the formatting of the output??? Help would be appreciated!

Code: Select all

[rio]

Your forgeting this.

After each output test set, your program should print exactly one blank line.

cin.eof() sometimes doesn't work well (i don't know why), so instead of

Code: Select all

while (!cin.eof())

try

Code: Select all

while (cin >> step >> mod)

I think you don't need delete[] (it's causing a error. I don't know why it occurs).

----
Sory for my poor English

[genti]

Thank you for the answer, rio. I did the changes and posted it again but this time I got a Presentation Error. The modified code looks like this:

Code: Select all

while(cin>>step>>mod)
    {
                     array = createTable(step, mod);
                     good = goodChoice(array, mod);
                     if(good) 
                     {
                              answer = "Good Choice";
                              stringl = 15;
                     }
                     else 
                     {
                          answer = "Bad Choice";
                          stringl = 14;
                     }
                     cout << setw(10) << setfill(' ') << step << setw(10) << setfill(' ') << mod << setw(stringl) << setfill(' ') << answer << "\n" <<endl;
    }
    return 0;

[rio]

``Good Choice" or ``Bad Choice" left-justified starting in column 25

so try

Code: Select all

 cout << setw(10) << setfill(' ') << step << setw(10) << setfill(' ') << mod << "    " << answer << endl<<endl;

Read the problem caerfully.

[genti]

Thank you a lot, it worked.

[shihabrc]

Can somenone plz give explanation or proof why STEP and MOD are good choices if gcd(STEP,MOD) == 1.


-Shihab

[shahriar_manzoor]

if gcd(STEP,MOD)==5 then all the numbers generated will be multiple of five, so they will never cover all the numbers within range.