## 11176 - Winning Streak

**Moderator:** Board moderators

What is the correct output for the following input set...

I m getting WA .

**Input:**Code: Select all

```
3 0.4
10 0.75
1 .77
100 .5
500 .5
500 .4
500 1
500 0
3 1
10 1
0 0.5
```

Ami ekhono shopno dekhi...

HomePage

HomePage

Jan wrote:What is the correct output for the following input set...

Input:I m getting WA .Code: Select all

`3 0.4 10 0.75 1 .77 100 .5 500 .5 500 .4 500 1 500 0 3 1 10 1 0 0.5`

Code: Select all

```
1.104000
5.068090
0.770000
5.991780
8.301581
6.357200
500.000000
0.000000
3.000000
10.000000
```

I have found my problem. But now I m getting TLE. My solution is O(n^3). Can anyone give me a hint for a better solution?

Thanks in advance.

Thanks in advance.

Ami ekhono shopno dekhi...

HomePage

HomePage

Finally got accepted with O(n^3) (with some modifications). Ivan, my idea is similar, except that I am calculating F

*[j] in O(n^3). Can you PM me the O(n^2) idea? Thanks.*Ami ekhono shopno dekhi...

HomePage

HomePage

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

Apart from solving this problem case by case by substituting the value of p in an early stage, we can also solve the general cases: the answer for a certain length l, A(l), can be expressed as a polynomial in p. If my hand calculations are right, the first four polynomials are:
Did anyone walk this route? I think the key to solving the problem this way, is finding an easy way to calculate the factors in the polynomials, but I haven't found one to date. You could use the applied formulas on polynomial objects in stead of substituting the value of p, of course, but this leads to an increased time complexity.

Would be interested to hear results.

Code: Select all

```
A(1) = p
A(2) = 2p
A(3) = 3p - p^2 +2p^3 - p^4
A(4) = 4p -3p^2 +7p^3 -6p^4 +3p^5 - p^6
```

Would be interested to hear results.

The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

I would be quite surprised if it was possible to get this approach faster than n^3 (which is what you get by just doing the calculations on the polynomials rather than the numbers): to do that, you would need better than linear time per coefficient, which I don't think is likely. But then, I have no hard facts to back this up, it's just my general feeling about it.little joey wrote:Apart from solving this problem case by case by substituting the value of p in an early stage, we can also solve the general cases: the answer for a certain length l, A(l), can be expressed as a polynomial in p. If my hand calculations are right, the first four polynomials are:Did anyone walk this route? I think the key to solving the problem this way, is finding an easy way to calculate the factors in the polynomials, but I haven't found one to date. You could use the applied formulas on polynomial objects in stead of substituting the value of p, of course, but this leads to an increased time complexity.Code: Select all

`A(1) = p A(2) = 2p A(3) = 3p - p^2 +2p^3 - p^4 A(4) = 4p -3p^2 +7p^3 -6p^4 +3p^5 - p^6`

Would be interested to hear results.

(And of course, if #testcases > n, this still gives a better complexity)

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

Yes, I think you are right in that it's unlikely that there is a better way then O(n^3) to calculate the coefficients, and it's not worthwhile to do so for so few queries.

Precalculation and hardcoding is no option because there's not enough room in a 32k program (and would be considered cheating by some).

Still there are some very fast times in the ranking for this problem, which gives me the feeling that there must be something better than the 'obvious' DP.

Precalculation and hardcoding is no option because there's not enough room in a 32k program (and would be considered cheating by some).

Still there are some very fast times in the ranking for this problem, which gives me the feeling that there must be something better than the 'obvious' DP.

The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.