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... (-)

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... (-)

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... (-)

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... (-)

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*