|
|
back to boardCould 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? > > 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:024s on p2-350 is enough for oj |
|
|