|
|
back to boardWhat in this test?
I use AVL trees and calculate result with binomial coefficient's. Where i mistaken? 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 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? Try this test:
Input:
6 3
6 2 3 1 5 4
Output:
3 Also test
5 3
5 2 1 4 3
breaks this approach |
|
|
