Pigeonhole principle: It will always be possible and the answer will always be a continuous sequence. How to solve: Consider N = 7: 1 2 50 3 4 0 0 The sum of the segment 1, 2, 50 is 53 and that of 1,2,50,3,4 is 60 53 % 7 = 4 60 % 7 = 4 if a % x = 1 and b % x =1 then (a-b)%x is always 0 So the segment between those two prefix sums will give 0 as modulo which is (3,4) = 7
Why the answer is such a sequence of input? Is it impossible that : input,input,input....... Thanks. > It's the second one. > S[i]= (input+input+..+input[i]) mod n; > If you can find i such as s[i]=0; it's ok. > If not, you always find i, j: s[i]=s[j]; > The sol is input[i+1]...input[j]. OK? > >
Thank you!Sergey Baskakov, Raphail and Denis10 Apr 2005 15:18
I got AC.
Your explanation is perfect!
I think, I would have never invented anything better than O(n^2) myself.
> Could someone help me. I've tried to solve the problem > using a classical Lee approach and for the worst case > when the numbers are very small (eg. 1 or 2), the program > takes about 4 secs on my PII-350. > > The Dirichlet method of solving isn't a better solution > because it has the same complexity. > > Could someone give me a hint on optimizing my algorithm or > if you got a better solution could you please forward it. > > Thankz.
Hi, Does the solution require the set having the minimum cardinality having numbers that sums to k*n? I am getting a WA, but the solution appears pretty right to me. If so, the question makes it appear that you can get by with any set. @Mods can this be updated in that case?
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;
we see b[x] es should be in range [0..n-1] but they are n+1 b(b 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+a+a+..a[j]=l*n+b[j] and P2=a+a+a+..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; k:=0; repeat inc(a); readln(a[a]); k:=(k+a[a]) mod n; if m[k]=-1 then m[k]:=a else begin writeln(a-m[k]); for i:=m[k]+1 to a 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
This is ridiculous!! My AC solution (ACed twice) works in 0.950 seconds. Which is actually O(n^2). The code is long and nasty... After some "improvements" - ie changing ArrayList to LinkedList/getting rid off BitSet/etc - the running time should decrease drastically!! but it gives me TL... WTF? I was sure, that my "better" code works FASTER, since there is much less operations to perform... Can anyone help me with it? I can send the code to get feedback. Thanks!
well... There's good idea in neighbor thread, which proves that solution always exist. It can help you solve it in O(n). Or... you can think up your own ideas based on remainders... There's up to N remainders only... so I used BFS without considering duplicates... it works fast enough in Java.
Re: 0,015sdAFTc0d3r [Yaroslavl SU]27 Mar 2010 01:42
I can run it in FP,but if I put it on,it will showed'Compilation error'. Who can tell me why?
var n,i,j,t,l:longint; a:array[0..1000] of longint; c:array[0..1000] of boolean; f:array[0..50000,0..1000] of boolean; begin readln(n); for i:=1 to n do readln(a[i]); c:=true;f[0,0]:=true; for i:=1 to n do for j:=n downto a[i] do if c[j-a[i]] then begin c[j]:=true;
for l:=0 to i-1 do
if f[j-a[i],l] then f[j,l]:=true; f[j,i]:=true; if j=n then begin for i:=1 to i do if f[n,i] then inc(t); writeln(t); for i:=1 to i do if f[n,i] then writeln(a[i]);halt; end; end; writeln(0); end.
var n,i,j,t,l:longint; a:array[0..1000] of longint; c:array[0..1000] of boolean; f:array[0..50000,0..1000] of boolean; begin readln(n); for i:=1 to n do readln(a[i]); c:=true;f[0,0]:=true; for i:=1 to n do //If you use var i here for j:=n downto a[i] do if c[j-a[i]] then begin c[j]:=true;
for l:=0 to i-1 do
if f[j-a[i],l] then f[j,l]:=true; f[j,i]:=true; if j=n then begin for i:=1 to i do // then you can not use it inside cycle if f[n,i] then inc(t); writeln(t); for i:=1 to i do if f[n,i] then writeln(a[i]);halt; end; end; writeln(0); end.
You can choose "send reply on my email" for explanations