## 11176 - Winning Streak

Moderator: Board moderators

Rainer
New poster
Posts: 1
Joined: Mon Feb 26, 2007 10:45 am

### 11176 - Winning Streak

any hint?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I did dp, but for some reason, my time is quite a bit slower than the others.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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 .
Ami ekhono shopno dekhi...
HomePage

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
Jan wrote: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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I m getting the same output but getting WA. Is there any trick?
Ami ekhono shopno dekhi...
HomePage

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
in my code i haven't got any special 'if'

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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?

Ami ekhono shopno dekhi...
HomePage

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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

Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
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
New poster
Posts: 13
Joined: Sat Dec 23, 2006 5:57 am
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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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
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:

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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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:

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
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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.