WA4

Posted by

Roman 20 Feb 2007 19:14

What in this test?

I use AVL trees and calculate result with binomial coefficient's. Where i mistaken?

Re: WA4

Interval tree is enough.

I wrote solution based on binomial coefficient's, but it's almost wrong(WA 9).

My new program, DP O(n * k * logn ) gets AC.

*Edited by author 20.02.2007 21:23*

*Edited by author 20.02.2007 21:23*

Re: WA4

Posted by

Lomir 13 Oct 2007 04:01

I used direct calculation of bin cofficents from factorials.

Answer := SUM[ C(k - 1)(n) ] for each ai

where n is the number elements greater tha ai in subsequance from 0 till ai.

However also WA4... Why?

Re: WA4

Try this test:

Input:

6 3

6 2 3 1 5 4

Output:

3

Re: WA4

Also test

5 3

5 2 1 4 3

breaks this approach