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, bertho_coder and me. Thanks to wanbo, adamant, danilka.pro, 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?
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
WNow observe that if
w_1[a,b]is a subword ofsat some positionsp_1,p_2,..,p_xthen suffixes ofWwhich begins atp_1ins,p_2ins, ...,p_xinsandainw_1make 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 ofw_1and go to the right(left) as long as lcp is greater thanb-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 thati <= p <= jand all numbers inA[i,j]satisfiesA[i,j] >= M.To solve this problem we can use DSU-trick. Let me explain it briefly: Sort queries by decreasing
Mand remember for each position left and right end of its interval in DSU. WhenMdecreases we just have to do some UNIONs.If you want I can elaborate more on this trick.
Can there be a problem, if some w1[a, b] = w2[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:
Editorial is updated.
Thanks :)
When will you send prizes?
looking for prize too :)
I sent around ~5 emails to HackerRank almost a month ago regarding prizes for University CodeSprint 1 and received a response similar to "We are looking into this."
Pretty sure University CodeSprint 2 will have similar "response times"
well to update I got my price yesterday, which is quite nice
I got Rs. 5000 for some contest (I think its Univ 1), but it sucks for me because I now study in the US and would have preferred to get the money in dollars :c
I wish they will send $10 instead of T-shirt (I got several ones ^.^)
Send me one t-shirt, I would give you 20$ :P
I'd give you one for free, if you're serious.
Why do you love me so much :D
Generally I hope I can win it alone, but in several CodeSprints I had my task or I tested some tasks :) So I was unable to compete in last 5-6 rounds. Top 10 in other rounds is big success and I am not ready for it yet :)
I thought they said they'll give a "World Champion T-Shirt". I already have 2 of these :c
Did anyone receive gift cards yet?