| ENG RUS | Timus Online Judge |
Discussion of Problem 1523. K-inversions>>> what is 12 test // Problem 1523. K-inversions 8 Jul 2022 14:43 почему если сначала 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 👾_challenger128_[PermSU] How to decrease mod operations? // Problem 1523. K-inversions 16 Nov 2020 18:15 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? Megatron wa#7, some tests, plz [8] // Problem 1523. K-inversions 18 Feb 2009 18:00 Megatron Re: wa#7, some tests, plz [7] // Problem 1523. K-inversions 18 Feb 2009 18:41 I know where I am wrong. AC: 0.078 681 KB eclipse2008 Re: wa#7, some tests, plz [2] // Problem 1523. K-inversions 14 Mar 2011 12:44 remember to % Edited by author 14.03.2011 13:05 Vitalii Arbuzov Re: wa#7, some tests, plz [1] // Problem 1523. K-inversions 2 May 2011 21:46 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 ? Anton Re: wa#7, some tests, plz // Problem 1523. K-inversions 8 Mar 2012 13:46 yes solix Re: wa#7, some tests, plz [3] // Problem 1523. K-inversions 5 May 2013 19:36 Excuse me, can you tell me where you were wrong? ASK Re: wa#7, some tests, plz [2] // Problem 1523. K-inversions 26 Mar 2014 20:30 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 Adhambek Re: wa#7, some tests, plz // Problem 1523. K-inversions 25 Nov 2014 16:52 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 KostyaRychkov ASK, thanks you! // Problem 1523. K-inversions 10 Jul 2020 21:08 ajay jadhav DP+BIT // Problem 1523. K-inversions 9 May 2020 21:55 similar to strictly increasing subsequnce of length k just query and update BIT in reverse. Mahilewets It took pretty long time // Problem 1523. K-inversions 17 Jul 2017 16:52 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. sak3t Used DP+BIT // Problem 1523. K-inversions 22 Jun 2017 14:00 Used DP + BIT, AC in 0.078 O(n*k*logn) solution. Don't forget, % 10^9 every step. Mahilewets Give me proof why following approach is wrong [1] // Problem 1523. K-inversions 11 May 2017 13:17 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 sak3t Re: Give me proof why following approach is wrong // Problem 1523. K-inversions 22 Jun 2017 13:53 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 Takanashi Rikka WA #7 Hint // Problem 1523. K-inversions 25 Feb 2016 17:52 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. Adhambek Some Hint : // Problem 1523. K-inversions 25 Nov 2014 16:53 you can use Fenwick tree It's more useful. Edited by author 25.11.2014 17:00 pankaj kumar Can Anyone provide algorithm for this problem. I am not able to figure out!!! // Problem 1523. K-inversions 19 Sep 2013 16:20 Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) How to solve this task? n*n*k=4e+9 - too long... (-) [7] // Problem 1523. K-inversions 18 Feb 2007 17:04 Tolstobrov Anatoliy[Ivanovo SPU] Re: How to solve this task? n*n*k=4e+9 - too long... (-) [4] // Problem 1523. K-inversions 18 Feb 2007 17:08 my N*K*Log(N) hint: problem with stars(1028) P.S. i solve it with 38 attempts. Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) Re: How to solve this task? n*n*k=4e+9 - too long... (-) [1] // Problem 1523. K-inversions 18 Feb 2007 17:09 Thanks!!! P.S. I solved the "I" task with 15 attempts:) Edited by author 18.02.2007 17:10 Fokysnik[LNU] Re: How to solve this task? n*n*k=4e+9 - too long... (-) // Problem 1523. K-inversions 18 Feb 2007 18:10 Damn! ];-/ Realy, this problem is almost identical to (1028)Stars. Why didn't I recognize it? Maybe growing old :) Thanks for hint! Giorgi Saghinadze (Tbilisi SU) Re: How to solve this task? n*n*k=4e+9 - too long... (-) [1] // Problem 1523. K-inversions 9 Feb 2008 14:56 How to solve this problem when K is quite big? svr Re: How to solve this task? n*n*k=4e+9 - too long... (-) // Problem 1523. K-inversions 17 Dec 2008 20:41 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. MarioYC Re: How to solve this task? n*n*k=4e+9 - too long... (-) [1] // Problem 1523. K-inversions 5 Nov 2010 11:59 An array of BIT's works well here. vlyubin Re: How to solve this task? n*n*k=4e+9 - too long... (-) // Problem 1523. K-inversions 18 Apr 2012 05:49 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 stupidjohn pay attention to %10^7 every step, i was trapped here for twice // Problem 1523. K-inversions 30 Jun 2011 15:25 http://hi.baidu.com/stupidjohn/blog/item/eabd3bd2acfe6dca572c84ea.html Edited by author 30.06.2011 15:47 Energy Wa 10, pls help // Problem 1523. K-inversions 14 Aug 2009 20:48 Nevermind, AC :) Edited by author 15.08.2009 05:48 Roman WA4 [4] // Problem 1523. K-inversions 20 Feb 2007 19:14 What in this test? I use AVL trees and calculate result with binomial coefficient's. Where i mistaken? Anton [SUrSU] Re: WA4 [3] // Problem 1523. K-inversions 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 Lomir Re: WA4 [2] // Problem 1523. K-inversions 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? SerailHydra Re: WA4 // Problem 1523. K-inversions 2 Mar 2008 08:26 Try this test: Input: 6 3 6 2 3 1 5 4 Output: 3 elmariachi1414 (TNU) Re: WA4 // Problem 1523. K-inversions 7 Nov 2008 16:28 Also test 5 3 5 2 1 4 3 breaks this approach Igor Dex What's the answer for [2] // Problem 1523. K-inversions 15 Mar 2007 16:19 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 ------------------------------ ConanKudo Re: What's the answer for [1] // Problem 1523. K-inversions 25 Jun 2008 15:34 my answers are 59165 for test case 1 and 51963 for test case 2 Denis Koshman Re: What's the answer for // Problem 1523. K-inversions 17 Jul 2008 14:02 Same (AC) Anton [SUrSU] WA #9 [1] // Problem 1523. K-inversions 19 Feb 2007 00:00 What is that test? My algo is O(n * lgn). Tolstobrov Anatoliy[Ivanovo SPU] Re: WA #9 // Problem 1523. K-inversions 19 Feb 2007 23:22 4 3 4 1 2 3 Answer 0 My help it.
|