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.

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

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.

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

Talking like you know everything

Edited by author 28.05.2006 01:02

what do you say

4s on p2-350 is enough for oj

why it's always a continuous sequence?

Edited by author 07.10.2014 17:00