Discussion @ 1032. Find a Multiple @ Timus Online Judge

tau Find A Multiple Problem. Anyone got a better than O(N^2) algo.? [13] // Problem 1032. Find a Multiple 26 Jun 2001 21:04

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.

Jivko Ganev Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.? [6] // Problem 1032. Find a Multiple 26 Jun 2001 22:51

In this problem you need to note 2 things:
1) There is always solution.
2) The solution is always a continuous sequence.

tau Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.? [5] // Problem 1032. Find a Multiple 28 Jun 2001 15:07

> In this problem you need to note 2 things:
> 1) There is always solution.
> 2) The solution is always a continuous sequence.

Thanks you.

Sun-ho, Cho Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.? [3] // Problem 1032. Find a Multiple 28 Dec 2001 11:19

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

meoden It's the choice 2 [2] // Problem 1032. Find a Multiple 28 Feb 2002 11:47

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

Big Guava Re: It's the choice 2 // Problem 1032. Find a Multiple 9 Mar 2002 10:49

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

Sergey Baskakov, Raphail and Denis Thank you! // Problem 1032. Find a Multiple 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.

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

why it's always a continuous sequence?

Edited by author 07.10.2014 17:00

Dinh Hong Minh Yes, O(N) . // Problem 1032. Find a Multiple 27 Jun 2001 19:04

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

Macarie Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.? [3] // Problem 1032. Find a Multiple 11 Apr 2005 15:04

O(N) -> compute partial sums then find two with same remainder modulo N and subtract them

TURAL**(SEKI OZEL TURK LISEYI) Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.? [2] // Problem 1032. Find a Multiple 7 Mar 2006 20:26

i think you're proffessor becasuse you find algorithm that every one know..

Ayhan Aliyev [BOTL] Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.? [1] // Problem 1032. Find a Multiple 8 Mar 2006 00:35

TURAL**(SEKI OZEL TURK LISEYI) wrote 7 March 2006 20:26

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

AOTL_EKREM Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.? // Problem 1032. Find a Multiple 30 Mar 2007 22:15

what do you say

tiancaihb Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.? // Problem 1032. Find a Multiple 9 Aug 2009 06:52

4s on p2-350 is enough for oj

Discussion of Problem 1032. Find a Multiple