10407 - Simple division

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

Moderator: Board moderators

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

10407 - Simple division

Post by yahoo »

I can't understand why my this code got runtime error. Can anyobody explain where i am doing wrong.Here is my code:
#include<stdio.h>
#define N 3000
main()
{
int tmp,a[N],i,j,r,hi,lo,n,m,b[N];
while(1)
{
n=0;
while(1)
{
scanf("%d",&a[n]);
if(a[n]==0) break;
n++;
}
if(!n) break;
for(i=0;i<n-1;i++)
{
m=i;
for(j=i+1;j<n;j++)
if(a[m]>a[j])
m=j;
tmp=a[m];
a[m]=a[i];
a[i]=tmp;
}
for(i=0;i<n-1;i++)
b[i]=a[i+1]-a[i];
lo=b[0];
for(i=1;i<n-1;i++)
if(b[i]<lo)
lo=b[i];
hi=b[0];
for(i=1;i<n-1;i++)
if(b[i]>hi)
hi=b[i];
int gcd=b[0];
for(i=1;i<n-1;i++)
{
if(b[i]>gcd) { hi=b[i];lo=gcd;}
else{hi=gcd;lo=b[i];}
while (1)
{
r = hi%lo;
if (r!=0)
{
hi = lo;
lo = r;
}
else {gcd=lo;break;}
}
}
printf("%d\n",lo);
}
return 0;
}
:oops:

abc
New poster
Posts: 15
Joined: Sun Dec 15, 2002 2:51 pm

Post by abc »

How do you solve this? I don't get it

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo »

Thanks for your reply. I got it accepted after recoding it. My algorithm was wrong here. Thanks again.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

actually yahoo,
your method donot work for repeated input. try it.
--anupam
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

again,
there may be problem about the array size.
check it.
--thanks.
"Everything should be made simple, but not always simpler"

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

10407-Simple Division

Post by b3yours3lf »

I always get TLE.
Can I use long int for this problem or I must use string?

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal »

i used int for this problem.

-sohel

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

10407

Post by .. »

I solved it by 0.082s, but I see there are many solutions of 0.002s.
Now I solve it by finding some possible values of d, and then test each value for d.....Is there some way to solve it in O(nlgn) or even O(n)?
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post by makbet »

It's very easy, once you know it :wink: :
if a mod d = b mod d <=> d divides (a-b). Now the problem gets simple :wink:

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Yes, I know that,
so what I do is, find the minimum (but positive) pairwise difference (diff), then test each factor of diff to check if all the input values get the same remainder r.
But it is slower than others, what do I miss??
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse »

why do you consider the minimum one only?
the most important point here is that d divides ALL pairwise-differences.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

cytse wrote: the most important point here is that d divides ALL pairwise-differences.
As you say, d divideds ALL pairwise-difference, so d is a factor of any pairwise-difference. Then d is also a factor of the min. pairwise-difference, so d <= min. pairwise-difference. It is safe to only consider the factors of min. pairwise difference.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post by makbet »

I don't know what you guys are talking about: you calculate differences of consecutive numbers and then calculate gcd of those. For examle:
17 5 9 3 99 55
differences:
12 4 6 96 44
nwd of those: 2, which is the correct anwser.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Oh~~~
I get it, thanks a lot!
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

10407,WA why ?????????????????

Post by Riyad »

Hi,
My Algorithm is very simple for this problem . i calculated the differences between all the successive numbers and stored them in an array of integer . than calculated the GCD of all the number . which should be the answer.

lets take an example , the sequence of number be

a b c d e f g h i j
i calculated abs(a-b),abs(b-c),abs(c-d),abs(d-e),........... and stored them in an array .
than i calculated the GCD s of them like this ..

a= it is the int array where i stored the diffences

x=GCD(a[0],a[1])

for(i=2;i<index;i++){
x=GCD(x,a);

}

x is the ans .
What is wrong with my algorithm and code .
plizzzzzzzzzz help.
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Post Reply

Return to “Volume 104 (10400-10499)”