| ENG RUS | Timus Online Judge |
Обсуждение задачи 1523. K-инверсииhakka_no_togame what is 12 test // Задача 1523. K-инверсии 8 июл 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 🐒🍌[PermSU] How to decrease mod operations? // Задача 1523. K-инверсии 16 ноя 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] // Задача 1523. K-инверсии 18 фев 2009 18:00 Megatron Re: wa#7, some tests, plz [7] // Задача 1523. K-инверсии 18 фев 2009 18:41 I know where I am wrong. AC: 0.078 681 KB eclipse2008 Re: wa#7, some tests, plz [2] // Задача 1523. K-инверсии 14 мар 2011 12:44 remember to % Edited by author 14.03.2011 13:05 Vitalii Arbuzov Re: wa#7, some tests, plz [1] // Задача 1523. K-инверсии 2 май 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 // Задача 1523. K-инверсии 8 мар 2012 13:46 yes solix Re: wa#7, some tests, plz [3] // Задача 1523. K-инверсии 5 май 2013 19:36 Excuse me, can you tell me where you were wrong? ASK Re: wa#7, some tests, plz [2] // Задача 1523. K-инверсии 26 мар 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 // Задача 1523. K-инверсии 25 ноя 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! // Задача 1523. K-инверсии 10 июл 2020 21:08 ajay jadhav DP+BIT // Задача 1523. K-инверсии 9 май 2020 21:55 similar to strictly increasing subsequnce of length k just query and update BIT in reverse. Nikita Mogilevets It took pretty long time // Задача 1523. K-инверсии 17 июл 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 // Задача 1523. K-инверсии 22 июн 2017 14:00 Used DP + BIT, AC in 0.078 O(n*k*logn) solution. Don't forget, % 10^9 every step. Nikita Mogilevets Give me proof why following approach is wrong [1] // Задача 1523. K-инверсии 11 май 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 // Задача 1523. K-инверсии 22 июн 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 index WA #7 Hint // Задача 1523. K-инверсии 25 фев 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 : // Задача 1523. K-инверсии 25 ноя 2014 16:53 you can use Fenwick tree It's more useful. Edited by author 25.11.2014 17:00 mirzman How to solve this task? n*n*k=4e+9 - too long... (-) [7] // Задача 1523. K-инверсии 18 фев 2007 17:04 Tolstobrov Anatoliy[Ivanovo SPU] Re: How to solve this task? n*n*k=4e+9 - too long... (-) [4] // Задача 1523. K-инверсии 18 фев 2007 17:08 my N*K*Log(N) hint: problem with stars(1028) P.S. i solve it with 38 attempts. mirzman Re: How to solve this task? n*n*k=4e+9 - too long... (-) [1] // Задача 1523. K-инверсии 18 фев 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... (-) // Задача 1523. K-инверсии 18 фев 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! Freeuni: GioSag Re: How to solve this task? n*n*k=4e+9 - too long... (-) [1] // Задача 1523. K-инверсии 9 фев 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... (-) // Задача 1523. K-инверсии 17 дек 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] // Задача 1523. K-инверсии 5 ноя 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... (-) // Задача 1523. K-инверсии 18 апр 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 Roman Nefyodov [Ufa SATU] WA4 [4] // Задача 1523. K-инверсии 20 фев 2007 19:14 What in this test? I use AVL trees and calculate result with binomial coefficient's. Where i mistaken? Anton juver++ Postnikov Re: WA4 [3] // Задача 1523. K-инверсии 20 фев 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] // Задача 1523. K-инверсии 13 окт 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 // Задача 1523. K-инверсии 2 мар 2008 08:26 Try this test: Input: 6 3 6 2 3 1 5 4 Output: 3 elmariachi1414 (TNU) Re: WA4 // Задача 1523. K-инверсии 7 ноя 2008 16:28 Also test 5 3 5 2 1 4 3 breaks this approach Igor Dex What's the answer for [2] // Задача 1523. K-инверсии 15 мар 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] // Задача 1523. K-инверсии 25 июн 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 // Задача 1523. K-инверсии 17 июл 2008 14:02 Same (AC) Anton juver++ Postnikov WA #9 [1] // Задача 1523. K-инверсии 19 фев 2007 00:00 What is that test? My algo is O(n * lgn). Tolstobrov Anatoliy[Ivanovo SPU] Re: WA #9 // Задача 1523. K-инверсии 19 фев 2007 23:22 4 3 4 1 2 3 Answer 0 My help it.
|