408 - Uniform Generator

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

Moderator: Board moderators

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: 408 very odd infinte loop

Post by CDiMa »

lotu wrote: 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.
lotu wrote: 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...
lotu wrote: 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.
lotu wrote: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
New poster
Posts: 11
Joined: Sun Jul 18, 2004 1:39 am

408 - why wrong answer?

Post by 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
New poster
Posts: 17
Joined: Thu Jul 15, 2004 10:55 am
Location: Poland, Rzeszow University of Technology

Post by 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
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

408 how to fix PE??

Post by 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!
keep it real!

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

I think the "choice" should be left justified.

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by 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:>
keep it real!

xish
New poster
Posts: 5
Joined: Mon Feb 13, 2006 9:45 am

408 any effective method to solve the problem

Post by 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
New poster
Posts: 44
Joined: Sun Feb 13, 2005 1:13 am
Location: India
Contact:

Post by 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)
google

genti
New poster
Posts: 5
Joined: Sat Oct 28, 2006 2:24 pm

WA and RE

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


Last edited by genti on Sun Nov 12, 2006 7:46 pm, edited 1 time in total.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by 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
New poster
Posts: 5
Joined: Sat Oct 28, 2006 2:24 pm

Post by 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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by 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
New poster
Posts: 5
Joined: Sat Oct 28, 2006 2:24 pm

Post by genti »

Thank you a lot, it worked.

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

Post by shihabrc »

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


-Shihab
Shihab
CSE,BUET

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

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

Post Reply

Return to “Volume 4 (400-499)”