ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1032. Find a Multiple

Find A Multiple Problem. Anyone got a better than O(N^2) algo.?
Posted by tau 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.
Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?
Posted by Jivko Ganev 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.
Yes, O(N) .
Posted by Dinh Hong Minh 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.
Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?
Posted by tau 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.
Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?
Posted by Sun-ho, Cho 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, Input, Input, Input, Input,
Input?

I don't know..

Give me more hints...
It's the choice 2
Posted by meoden 28 Feb 2002 11:47
>     ex) 1.      4 5 6 7 8 9
>                 or
>         2.      Input, Input, Input, Input, Input,
> Input?

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?
Re: It's the choice 2
Posted by Big Guava 9 Mar 2002 10:49
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!
Posted by Sergey Baskakov, Raphail and Denis 10 Apr 2005 15:18
I got AC.

I think, I would have never invented anything better than O(n^2) myself.

Thanks once again!

rafailka.
Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?
Posted by Macarie 11 Apr 2005 15:04
O(N) -> compute partial sums then find two with same remainder  modulo N and subtract them
Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?
Posted by TURAL**(SEKI OZEL TURK LISEYI) 7 Mar 2006 20:26
i think you're proffessor becasuse you find algorithm that every one know..
Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?
Posted by Ayhan Aliyev [BOTL] 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
Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?
Posted by AOTL_EKREM 30 Mar 2007 22:15
what do you say
Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?
Posted by tiancaihb 9 Aug 2009 06:52
4s on p2-350 is enough for oj
Re: Find A Multiple Problem. Anyone got a better than O(N^2) algo.?
Posted by zylm 7 Oct 2014 16:54
why it's always a continuous sequence?

Edited by author 07.10.2014 17:00