Show all threads Hide all threads Show all messages Hide all messages 
How to decrease mod operations?  👾_challenger128_[PermSU]  1523. Kinversions  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. Kinversions  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. Kinversions  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. Kinversions  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 jinversions ending at element number j. dp[i] [j] =sum (dp[p] [j1]) for all p>i. The answer is sum(dp[i] [k]) for all i=0...n1. As mentioned below, an array of Fenwick trees is your friend. 
Used DP+BIT  sak3t  1523. Kinversions  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. Kinversions  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 K1 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. Kinversions  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. Kinversions  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. Kinversions  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. Kinversions  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. Kinversions  30 Jun 2011 15:25  1 

Wa 10, pls help  Energy  1523. Kinversions  14 Aug 2009 20:48  1 
Nevermind, AC :) Edited by author 15.08.2009 05:48 
WA4  Roman  1523. Kinversions  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. Kinversions  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. Kinversions  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. 