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 (ab)%x is always 0 So the segment between those two prefix sums will give 0 as modulo which is (3,4) = 7 random_shuffle and check prefix sums for division. The test has only one number: 1 2 Ohhhhhhh,thank youuuuuu! Try also this test: 5 3 1 3 3 3 Answer is, of course: 4 1 3 3 3 The test has only one number: 1 2 This test isn't coorectly because numbers is [1, N] correct testcase is: 1 1 And my program print coorect answer: 1 1 But I still have WA1.. someone can help? P.S. my program pass your testcase too =) No, numbers are in [1, 15000], not [1, N]. :) 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 PII350. 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. In this problem you need to note 2 things: 1) There is always solution. 2) The solution is always a continuous sequence. > In this problem you need to note 2 things: > 1) There is always solution. > 2) The solution is always a continuous sequence. Thanks you. > > In this problem you need to note 2 things: > > 1) There is always solution. > > 2) The solution is always a continuous sequence. > > Thanks you. I can't understand 2) The solution is always a continuous sequence. What means continuous sequence? ex) 1. 4 5 6 7 8 9 or 2. Input[4], Input[5], Input[6], Input[7], Input[8], Input[9]? I don't know.. Give me more hints... > ex) 1. 4 5 6 7 8 9 > or > 2. Input[4], Input[5], Input[6], Input[7], Input[8], > Input[9]? It's the second one. S[i]= (input[1]+input[2]+..+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?
Why the answer is such a sequence of input? Is it impossible that : input[1],input[7],input[9]....... Thanks. > It's the second one. > S[i]= (input[1]+input[2]+..+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? > > I got AC. Your explanation is perfect! I think, I would have never invented anything better than O(n^2) myself. Thanks once again! rafailka. why it's always a continuous sequence? Edited by author 07.10.2014 17:00 > 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 PII350. > > 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. O(N) > compute partial sums then find two with same remainder modulo N and subtract them i think you're proffessor becasuse you find algorithm that every one know.. i think you're proffessor becasuse you find algorithm that every one know.. Talking like you know everything Edited by author 28.05.2006 01:024s on p2350 is enough for oj There is a typo in statement in the first part of it. The sentence: "This numbers are not necessarily different" should be written as: "These numbers are not necessarily different". Try this test (it helped me, but real test #36 has N = 10000): 7 4 4 4 5 5 5 5 Answer, of course, is for example 3 5 4 5 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? Thanks. Does it say it requires a minimum cardinality? For test 34 I have time limit exceeded answer. I have done the problem in Java. May I see the test 34? Thanks. I solved by using int[] instead of ArrayList. As you know i can prove that there is 1<=i<j<=n that: ( a[i]+a[i+1]+...+a[j1]+a[j] ) mod n =0 because as boxprinciple(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..n1] 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 p1p2 we see: P3=a[j]+a[j1]+a[j2]+..a[i+2]+a[i+1]= (lk)*n+b[j]b[i] and we knew b[i]=b[j] so P3=(lk)*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 Cool It's great idea. But i think b[i]=(a[1]+...+a[i])%n; Edited by author 19.04.2005 14:19 Cool It's great idea. But i think b[i]=(a[1]+...+a[i])%n; right!!! Edited by author 24.02.2007 18:30 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! And I'm interesting how to solve this in 0,015s. 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. Yeah, there is a nice idea. =) 0.14 seconds on JAVA, O(nlogn + n) solution What is the answer to 3 1 2 3 According to the question, the answer should be 1 3 isn't it? But why the correct answer is 2 1 2 What is exactly the sentence below mean? "Your task is to choose a few of given numbers (1 ≤ few ≤ N) so that the sum of chosen numbers is multiple for N" Is it already correct that the answer to the above question is {1, 2} where as the minimum set which its sum divisible by 3 is {3}. (I'm not English native) Edited by author 07.02.2010 23:20 you should print any set of numbers/ so, both answers are possible. even 3 1 2 3 Check please test 33. It's very strange that dp ( subset with given sum ) don't work. Maybe there is a bad checker. Both test 33 and checker are correct. Look for a bug in your solution. Good luck! Thank's. Stupid error in my algo. Solution with DP (minimal summand count) gets WA3. Changing 1 line (eliminating miminizing) makes it AC. My solution gives the minimal possible answer ? and yet it still gets WA#1. I tried many times but the result remained unchanged ? Why? Can the sample output be 4 1 2 3 4 ??? Edited by author 17.03.2007 00:19 (1+2+3+4)%5=10%5=0 So it can be. Why do I have WA12??? Print numbers from list such that the sum of those numbers is a multiple of n. You can do it yourself! Here's a hint. Consider the sum of the first k integers for k = 1 to n. I got AC now. And I got WA twice only because I forgot a stupid santance "memset(o,0,sizeof(o));". 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[0]:=true;f[0,0]:=true; for i:=1 to n do for j:=n downto a[i] do if c[ja[i]] then begin c[j]:=true; for l:=0 to i1 do if f[ja[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[0]:=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[ja[i]] then begin c[j]:=true; for l:=0 to i1 do if f[ja[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 Edited by author 23.11.2007 15:59 
