|
|
почему если сначала for k.. for (i=n-1; i >= 0; i--) inc() то ва12 а если for(i = n-1; i >=0; i--) for k... inc() то АС? надеюсь кто-нибудь понял.. Edited by author 08.07.2022 14:59 Anybody know how to decrease mod operations to get more faster solution? I've implemented segment tree, where any node used mod operation to be calculated. I got 0.75s on G++, 0.41s on Clang and 0.25s Visual C++. Maybe I should check if value is overflowed (than mod), but will it be faster? I know where I am wrong. AC: 0.078 681 KB remember to % Edited by author 14.03.2011 13:05 This test is going to kill me. I know that I should do % but it doesn't help anyway. I'm not strong in module algebra is (a + b + c) % 10^9 ?== (((a % 10^9 + b) % 10^9 + c) % 10^9 ? Excuse me, can you tell me where you were wrong? 40 20 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 ans: 846528820 your ans is correct , but k <= 10... try this test case : 40 10 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 ans : 847660528 similar to strictly increasing subsequnce of length k just query and update BIT in reverse. It was hard to understand how to calculate the answer. It is relatively easy to invent a correct solution when you know the expected time complexity. Solve the task online, read elements one by one. So, you have dp[i][j] = count of different j-inversions ending at element number j. dp[i] [j] =sum (dp[p] [j-1]) for all p>i. The answer is sum(dp[i] [k]) for all i=0...n-1. As mentioned below, an array of Fenwick trees is your friend. Used DP + BIT, AC in 0.078 O(n*k*logn) solution. Don't forget, % 10^9 every step. My approach wrong approach is such. Read cur number X. Find CNT count of numbers Y (Y>X) already read. Find number of ways to pick K-1 items from set of CNT distinctive items. Add that number to ANSWER. Find modulo. Edited by author 11.05.2017 13:28 Your solution is wrong. See for example 6 3 3 4 5 6 2 1 when you read 2, all the numbers before it are > 2 and hence you'll add to your sum, all the possible pairs in previous 4 numbers. But 3 4 5 6 can't make any pair such that a_i > a_{i+1}. Hence your solution doesn't work. Edited by author 22.06.2017 13:55 If you use fenwick tree and got WA #7, don't write Get(r) - Get(l - 1). Write (Get(r) - Get(l - 1) + mod) % mod. you can use Fenwick tree It's more useful. Edited by author 25.11.2014 17:00 my N*K*Log(N) hint: problem with stars(1028) P.S. i solve it with 38 attempts. Thanks!!! P.S. I solved the "I" task with 15 attempts:) Edited by author 18.02.2007 17:10 Damn! ];-/ Realy, this problem is almost identical to (1028)Stars. Why didn't I recognize it? Maybe growing old :) Thanks for hint! How to solve this problem when K is quite big? Red_Black trees. Dynamic statistics with renewing after adding each -a[i] going backward from the end. We store int d[10] for each node balanced tree and for each subtree T(x). Here d[i]- number of sequences beggining from x with length i. An array of BIT's works well here. RSQ works as well and the solution is really quick and simple.O(k*n*log(n)) gives 0.046s(That's with vectors, probably without them it would be even faster). Edited by author 18.04.2012 08:47 Nevermind, AC :) Edited by author 15.08.2009 05:48 What 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 What's the answer for ------------------------------ 30 8 15 16 19 17 18 20 21 27 30 29 28 26 25 24 23 22 14 13 12 11 10 5 4 3 2 1 6 7 8 9 ------------------------------ 30 10 15 16 19 17 18 20 21 27 30 29 28 26 25 24 23 22 14 13 12 11 10 5 4 3 2 1 6 7 8 9 ------------------------------ my answers are 59165 for test case 1 and 51963 for test case 2 What is that test? My algo is O(n * lgn). 4 3 4 1 2 3 Answer 0 My help it. |
|
|