| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| what is 12 test | >>> | 1523. K-инверсии | 8 июл 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-инверсии | 16 ноя 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-инверсии | 10 июл 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-инверсии | 9 май 2020 21:55 | 1 |
DP+BIT ajay jadhav 9 май 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-инверсии | 17 июл 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-инверсии | 22 июн 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-инверсии | 22 июн 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-инверсии | 25 фев 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-инверсии | 25 ноя 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-инверсии | 19 сен 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-инверсии | 18 апр 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-инверсии | 30 июн 2011 15:25 | 1 |
|
| Wa 10, pls help | Energy | 1523. K-инверсии | 14 авг 2009 20:48 | 1 |
Nevermind, AC :)
Edited by author 15.08.2009 05:48 |
| WA4 | Roman | 1523. K-инверсии | 7 ноя 2008 16:28 | 5 |
WA4 Roman 20 фев 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 фев 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 мар 2008 08:26 Try this test:
Input:
6 3
6 2 3 1 5 4
Output:
3 Re: WA4 elmariachi1414 (TNU) 7 ноя 2008 16:28 Also test
5 3
5 2 1 4 3
breaks this approach |
| What's the answer for | Igor Dex | 1523. K-инверсии | 17 июл 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-инверсии | 19 фев 2007 23:22 | 2 |
WA #9 Anton [SUrSU] 19 фев 2007 00:00 What is that test?
My algo is O(n * lgn). Re: WA #9 Tolstobrov Anatoliy[Ivanovo SPU] 19 фев 2007 23:22
4 3
4 1 2 3
Answer 0
My help it. |
