Discussion @ 1523. K-inversions @ Timus Online Judge

How to solve this task? n*n*k=4e+9 - too long... (-)

Posted by Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) 18 Feb 2007 17:04

Re: How to solve this task? n*n*k=4e+9 - too long... (-)

Posted by Tolstobrov Anatoliy[Ivanovo SPU] 18 Feb 2007 17:08

my
N*K*Log(N)

hint: problem with stars(1028)

P.S. i solve it with 38 attempts.

Re: How to solve this task? n*n*k=4e+9 - too long... (-)

Posted by Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) 18 Feb 2007 17:09

Thanks!!!
P.S. I solved the "I" task with 15 attempts:)

Edited by author 18.02.2007 17:10

Re: How to solve this task? n*n*k=4e+9 - too long... (-)

Posted by Fokysnik[LNU] 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!

Re: How to solve this task? n*n*k=4e+9 - too long... (-)

Posted by Giorgi Saghinadze (Tbilisi SU) 9 Feb 2008 14:56

How to solve this problem when K is quite big?

Re: How to solve this task? n*n*k=4e+9 - too long... (-)

Posted by svr 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.

Re: How to solve this task? n*n*k=4e+9 - too long... (-)

Posted by MarioYC 5 Nov 2010 11:59

An array of BIT's works well here.

Re: How to solve this task? n*n*k=4e+9 - too long... (-)

Posted by vlyubin 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

Discussion of Problem 1523. K-inversions