11176 - Winning Streak

[Rainer]

any hint?

[sclo]

I did dp, but for some reason, my time is quite a bit slower than the others.

[Jan]

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

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

I m getting WA .

[Monsoon]

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

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

I m getting WA .

Code: Select all

1.104000
5.068090
0.770000
5.991780
8.301581
6.357200
500.000000
0.000000
3.000000
10.000000

[Jan]

I m getting the same output but getting WA. Is there any trick?

[Monsoon]

in my code i haven't got any special 'if'

[Jan]

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.

[Ivan]

I solve the problem by using the function F[j] - the
probability that from i consecutive games you get no more than j
consecutive wins. This can be calculated with a complexity of n^2.
Having this computed it is not hard to see how to use it to solve
the actual problem.

[Jan]

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.

[Hadi]

The O(n^2) method is fundamentally the same as O(n^3) one. the difference is that it uses an extra array to avoid unnecessary calculations. (Just think about what your function does and how can you store it in an array)

[deepesh]

I have got accepted on this problem by considering three separate cases:

F[j] -> case 1, i<=j ; case 2;i==j+1; case 3 i>j+1.

Is there any elegant method which does all this in a single formula?

[sclo]

I've solved it both ways.
My earlier solution was O(n^3) and involves an convolution making it O(n^3)
My later solution was O(n^2) has 4 cases, there's also a case for i==0.

I wonder how the code can have no "if" statements.

[little joey]

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:

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

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.

[Per]

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:

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

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.

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.

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

[little joey]

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.