Show all threads Hide all threads Show all messages Hide all messages |

Hint to this question | guilty spark | 1032. Find a Multiple | 30 Aug 2020 14:09 | 1 |

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 |

random_shuffle | Nail[HSE] | 1032. Find a Multiple | 20 Oct 2017 14:55 | 1 |

random_shuffle and check prefix sums for division. |

if you got WA#1 | ile | 1032. Find a Multiple | 5 May 2015 13:04 | 6 |

The test has only one number: 1 2 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]. :) |

Find A Multiple Problem. Anyone got a better than O(N^2) algo.? | tau | 1032. Find a Multiple | 7 Oct 2014 16:54 | 14 |

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. 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? > > Thank you! **Sergey Baskakov, Raphail and Denis** 10 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. 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 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. 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:02*4s on p2-350 is enough for oj |

To admins: typo in statement | Smilodon_am [Obninsk INPE] | 1032. Find a Multiple | 27 Nov 2013 11:18 | 1 |

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". |

If you have WA #36 | Smilodon_am [Obninsk INPE] | 1032. Find a Multiple | 27 Nov 2013 11:08 | 1 |

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 |

Minimum cardinality set required? | Indivisible Atom | 1032. Find a Multiple | 28 Mar 2013 02:29 | 2 |

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? |

Time limit exceeded | Peca | 1032. Find a Multiple | 19 Oct 2011 02:57 | 2 |

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. |

WA #3 | cs_Diablo | 1032. Find a Multiple | 15 Sep 2011 15:24 | 1 |

WA #3 **cs_Diablo** 15 Sep 2011 15:24 |

---> Very Simple Way with O(N) and pigeonhole proving! <--- | Locomotive | 1032. Find a Multiple | 19 Aug 2011 07:37 | 8 |

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 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* |

AC; after little bit tweaking the code I got TL#4 | ile | 1032. Find a Multiple | 6 Feb 2011 00:20 | 5 |

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! 0,015s **dAFTc0d3r [Yaroslavl SU]** 26 Mar 2010 10:49 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. Re: 0,015s **dAFTc0d3r [Yaroslavl SU]** 27 Mar 2010 01:42 Yeah, there is a nice idea. =) 0.14 seconds on JAVA, O(nlogn + n) solution |

Is the question clear enough ? | Ake Tangkananond | 1032. Find a Multiple | 8 Feb 2010 19:55 | 2 |

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 |

1032. To Admins. | archi | 1032. Find a Multiple | 20 Aug 2009 13:28 | 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. |

Something wrong with checkers? | Java | 1032. Find a Multiple | 17 Aug 2009 15:31 | 1 |

Solution with DP (minimal summand count) gets WA3. Changing 1 line (eliminating miminizing) makes it AC. |

to admin WA #1 ???? | TESTER | 1032. Find a Multiple | 26 Jul 2009 10:49 | 3 |

My solution gives the minimal possible answer ? and yet it still gets WA#1. I tried many times but the result remained unchanged ? Why? |

Please help... | Soul Reaver | 1032. Find a Multiple | 21 Jul 2008 16:31 | 3 |

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??? |

explain the question | Emilbek | 1032. Find a Multiple | 27 May 2008 16:15 | 2 |

Print numbers from list such that the sum of those numbers is a multiple of n. |

gıve me solıtıon emılbek_4@netmail.kg | Emilbek | 1032. Find a Multiple | 25 May 2008 23:45 | 2 |

You can do it yourself! Here's a hint. Consider the sum of the first k integers for k = 1 to n. |

FT. | Phoenix | 1032. Find a Multiple | 12 Feb 2008 13:58 | 1 |

FT. **Phoenix** 12 Feb 2008 13:58 I got AC now. And I got WA twice only because I forgot a stupid santance "memset(o,0,sizeof(o));". |

Why didi I get 'Compilation error'? | 123789 | 1032. Find a Multiple | 26 Nov 2007 17:20 | 3 |

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[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[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[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
*Edited by author 23.11.2007 15:59* |