Hello Codeforces Community, I am glad to share HackerRank University Codesprint 2 starting on 17th February 2016. The contest duration is 24 * 2 = 48 hours.

The winners of the contest will win up to 2000USD cash prizes. Also, there are opportunities to win T-shirts and Amazon Gift cards. (Winners will be required to give proof that they are currently enrolled in the university they represented during University CodeSprint.)

The contest will be rated. If two person gets the same score, the person who reached the score first will be ranked higher. There will be a separate ranklists for schools.

There will be 8 algorithmic challenges in this contest. Many of the problems will have smaller subtasks, so I highly recommend you to read all the problems.

The problems are prepared by tunyash, allllekssssa, osmanorhan, DmitriyH, darkshadows, tube_light and me. Thanks to wanbo, adamant, dans, svanidz1, zemen for helping them with testing. Special thanks goes to wild_hamster for helping to finalize everything and to allllekssssa for finding mistakes in the statements.

Update: Contest is starting in less than two hours!

Update: The contest has ended, the editorials are now available. Congrats to tourist for solving everything in just 143 mins!

Editorials will be live soon after the contest ends.

72 hours? But clist said that duration is only 48 hours. And official site said that contest starts 17th at 20:00 MSK and ends 19th (I think also at 20:00MSK). So that's only 48 hours.

Updated post, thanks.

Alumni have no eligibility to win prizes but are rated?

You need to solve all tasks in 210 minutes, than you will get prize from me :P Shafaet, Wild_Hamster and me bet about winning time :D

I found six small mistakes in statements, I got new best result :D

My estimation this Codesprint will be easier than last two-three rounds, but I believe everyone will find something interesting and spend great hours in solving.

Rated for everyone.

Anyone else who hasn't received the prize for the First University Codesprint? xD

Contact support@hackerrank.com if you didn't recieve prizes.

Are the prizes only for top 100 university students? Can high school students win a prize?

By the time you get an email regarding the prizes, you will have completed university studies. Then they'll deem you ineligible for the prize. #proStrategy

No prize for tourist, only coders from Earth can get it :P

awesome editorial for querying sums on strings -_-

I hope this comment is sarcastic. I personally have no idea what the editorial means. Kinda frustrated since the question itself is interesting and I really want to learn from a well-written editorial.

It was sarcastic :P

Alright so I'm not the only who is frustrated with the editorial writer :) Btw do you have any idea how to solve that question?

I couldn't get the problem with my solution for story-of-a-tree.

Help required..

solution

Can anyone please explain how to solve Querying Sums on Strings !!! The editorial is impossible to understand :(

This is how I did it. Consider 2 cases.Also remember q*k=10^5.

Case 1: k>sqrt(10^5).Simply iterate over pairs in each query and calculate the function f.The complexity would be q*m.Since k>sqrt(10^5) and q*k=10^5 q<sqrt(10^5).

Case 2: k<sqrt(10^5).In this case the string in the query would have O(k^2) substrings.Calculate the function f for all of them.Since there are O(k^2) substrings we would have to answer O(k^2) distinct queries.So somehow group repetitive queries.Complexity would be q*k^2.q*k^2=(q*k)*k.since q*k<10^5 and k<sqrt(10^5) this is good enough.

I wasn't calculating the function f efficiently which lead to a complexity of q*min(k^2,m)*log(n) and thus my solution was giving TLE.

Hope this helps.

Thanks. I came up with that square root thing during contest too. But I couldn't think of a good way to calculate f. If you understand how to find f efficiently, please let me know. I'd be grateful. :)

To compute f fast we can:

create word

`W = s#w_1#w_2#...#w_q#`

compute suffix array and lcp for

`W`

Now observe that if

`w_1[a,b]`

is a subword of`s`

at some positions`p_1,p_2,..,p_x`

then suffixes of`W`

which begins at`p_1`

in`s`

,`p_2`

in`s`

, ...,`p_x`

in`s`

and`a`

in`w_1`

make up a block (are consecutive) in suffix array.Moreover using lcp we can easily find the ends of this block: start at suffix which begins at

`a`

-th letter of`w_1`

and go to the right(left) as long as lcp is greater than`b-a`

.Now the problem is: we have an array

`A`

(lcp) and some queries of the form: for a pair`(p, M) = (position, number)`

find the longest interval`(i,j)`

such that`i <= p <= j`

and all numbers in`A[i,j]`

satisfies`A[i,j] >= M`

.To solve this problem we can use DSU-trick. Let me explain it briefly: Sort queries by decreasing

`M`

and remember for each position left and right end of its interval in DSU. When`M`

decreases we just have to do some UNIONs.If you want I can elaborate more on this trick.

Can there be a problem, if some

w_{1}[a,b] =w_{2}[c,d] for example? Than for both segments there will be 1 extra point in answer.Yes. I didn't mention that. But we can fix it easly. We can mark suffixes which has begin in

`s`

. And having interval in lcp-array for a query, we can compute number of marked points in the interval. We can use sparse table to preprocess in O(NlgN) and answer in O(1)We don't need sparse table to compute number of marked points in the interval.

We could get DSU components/interval(as you call it) size.

With initialization: