11176 - Winning Streak

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11176 - Winning Streak

Post by Rainer » Mon Feb 26, 2007 10:59 am

any hint?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Feb 26, 2007 9:09 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Feb 26, 2007 10:44 pm

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

Post by Monsoon » Mon Feb 26, 2007 11:08 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Feb 26, 2007 11:11 pm

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

Post by Monsoon » Mon Feb 26, 2007 11:17 pm

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Feb 27, 2007 9:54 am

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.
Ami ekhono shopno dekhi...
HomePage

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » Tue Feb 27, 2007 11:32 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Feb 28, 2007 3:03 am

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

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Wed Feb 28, 2007 7:33 am

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

Post by deepesh » Wed Feb 28, 2007 7:50 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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Feb 28, 2007 10:09 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri May 25, 2007 12:40 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

Post by Per » Fri Aug 17, 2007 9:21 am

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)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Aug 18, 2007 9:45 am

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.

Post Reply

Return to “Volume 111 (11100-11199)”