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 » Sun Nov 24, 2002 8:00 pm

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 » Sun Dec 15, 2002 2:51 pm

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 » Sun Dec 15, 2002 3:10 pm

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 » Mon Dec 16, 2002 6:42 am

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 » Mon Dec 16, 2002 6:43 am

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 » Sat Apr 12, 2003 7:15 am

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 » Sat Apr 12, 2003 3:59 pm

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 .. » Wed May 21, 2003 5:50 pm

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 » Wed May 21, 2003 8:36 pm

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 .. » Thu May 22, 2003 6:57 am

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 » Thu May 22, 2003 4:56 pm

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 .. » Thu May 22, 2003 6:04 pm

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 » Thu May 22, 2003 6:35 pm

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 .. » Thu May 22, 2003 6:50 pm

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 » Fri Nov 21, 2003 8:20 am

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)”