---> Very Simple Way with O(N) and pigeonhole proving! <---

As you know i can prove that there is 1<=i<j<=n that:

( a[i]+a[i+1]+...+a[j-1]+a[j] ) mod n =0

because as box-principle(or pigeonhole) if we define

b[i]:=a[i] mod n

and b[0]:=0;

we see b[x] es should be in range [0..n-1] but they are n+1 b(b[0] to

b[n])

and it means there is two b (like (b[i],b[j]) that hey are equal

b[i]=b[j]

so

we see:

P1=a[1]+a[2]+a[3]+..a[j]=l*n+b[j]

and

P2=a[1]+a[2]+a[3]+..a[i]=k*n+b[i]

so if we calculate p1-p2 we see:

P3=a[j]+a[j-1]+a[j-2]+..a[i+2]+a[i+1]=

(l-k)*n+b[j]-b[i]

and we knew b[i]=b[j] so

P3=(l-k)*n ----> p3 mod n =0!!!!

so we should calcualte all b(s) and find I and J

so:

(with this algorithm we dont need to read all numbers!)

here is my code:

Var

n,i,k :integer;

a :array[0..10000] of integer;

m :array[0.. 9999] of integer;

begin

readln(n);

fillchar(m,sizeof(m),-1);

m[0]:=0; k:=0;

repeat

inc(a[0]);

readln(a[a[0]]);

k:=(k+a[a[0]]) mod n;

if m[k]=-1 then

m[k]:=a[0]

else

begin

writeln(a[0]-m[k]);

for i:=m[k]+1 to a[0] do

writeln(a[i]);

break;

end;

until false;

end.

~~~~~~~~~~~~~~~~~~~~~~

Please tell me if you dont understand it at all.

and your notice about it

Sincerely

Aidin_n7@hotmail.com

Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---

Posted by

Sid 18 Apr 2005 22:53

Cool It's great idea. But i think b[i]=(a[1]+...+a[i])%n;

*Edited by author 19.04.2005 14:19*

Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---

Posted by

Machvi 24 Feb 2007 18:28

Cool It's great idea. But i think b[i]=(a[1]+...+a[i])%n;

right!!!

Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---

Posted by

Machvi 24 Feb 2007 18:29

*Edited by author 24.02.2007 18:30*

Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---

that's it

Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---

Thank you so so much ))

Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---

Respect!

Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---

amazing, really amazing.