ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1032. Find a Multiple

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...
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.
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.
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..
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
4s on p2-350 is enough for oj