ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1523. K-inversions

How to solve this task? n*n*k=4e+9 - too long... (-)
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... (-)
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