Show all threads Hide all threads Show all messages Hide all messages |
what is 12 test | >>> | 1523. K-inversions | 8 Jul 2022 14:43 | 1 |
почему если сначала 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 |
How to decrease mod operations? | 👾_challenger128_[PermSU] | 1523. K-inversions | 16 Nov 2020 18:15 | 1 |
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? |
wa#7, some tests, plz | Megatron | 1523. K-inversions | 10 Jul 2020 21:08 | 9 |
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 |
DP+BIT | ajay jadhav | 1523. K-inversions | 9 May 2020 21:55 | 1 |
DP+BIT ajay jadhav 9 May 2020 21:55 similar to strictly increasing subsequnce of length k just query and update BIT in reverse. |
It took pretty long time | Mahilewets | 1523. K-inversions | 17 Jul 2017 16:52 | 1 |
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 | sak3t | 1523. K-inversions | 22 Jun 2017 14:00 | 1 |
Used DP + BIT, AC in 0.078 O(n*k*logn) solution. Don't forget, % 10^9 every step. |
Give me proof why following approach is wrong | Mahilewets | 1523. K-inversions | 22 Jun 2017 13:53 | 2 |
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 |
WA #7 Hint | Takanashi Rikka | 1523. K-inversions | 25 Feb 2016 17:52 | 1 |
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. |
Some Hint : | Adhambek | 1523. K-inversions | 25 Nov 2014 16:53 | 1 |
you can use Fenwick tree It's more useful. Edited by author 25.11.2014 17:00 |
Can Anyone provide algorithm for this problem. I am not able to figure out!!! | pankaj kumar | 1523. K-inversions | 19 Sep 2013 16:20 | 1 |
|
How to solve this task? n*n*k=4e+9 - too long... (-) | Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) | 1523. K-inversions | 18 Apr 2012 05:49 | 8 |
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 |
pay attention to %10^7 every step, i was trapped here for twice | stupidjohn | 1523. K-inversions | 30 Jun 2011 15:25 | 1 |
|
Wa 10, pls help | Energy | 1523. K-inversions | 14 Aug 2009 20:48 | 1 |
Nevermind, AC :) Edited by author 15.08.2009 05:48 |
WA4 | Roman | 1523. K-inversions | 7 Nov 2008 16:28 | 5 |
WA4 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 Anton [SUrSU] 20 Feb 2007 21:12 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? Re: WA4 SerailHydra 2 Mar 2008 08:26 Try this test: Input: 6 3 6 2 3 1 5 4 Output: 3 Re: WA4 elmariachi1414 (TNU) 7 Nov 2008 16:28 Also test 5 3 5 2 1 4 3 breaks this approach |
What's the answer for | Igor Dex | 1523. K-inversions | 17 Jul 2008 14:02 | 3 |
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 |
WA #9 | Anton [SUrSU] | 1523. K-inversions | 19 Feb 2007 23:22 | 2 |
WA #9 Anton [SUrSU] 19 Feb 2007 00:00 What is that test? My algo is O(n * lgn). Re: WA #9 Tolstobrov Anatoliy[Ivanovo SPU] 19 Feb 2007 23:22 4 3 4 1 2 3 Answer 0 My help it. |