### Shafaet's blog

By Shafaet, history, 15 months ago, ,

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.

•
• +64
•

 » 15 months ago, # | ← Rev. 2 →   +15 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.
•  » » 15 months ago, # ^ |   0 Updated post, thanks.
 » 15 months ago, # |   0 Alumni have no eligibility to win prizes but are rated?
•  » » 15 months ago, # ^ |   -16 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 :DMy 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.
•  » » 15 months ago, # ^ |   0 Rated for everyone.
 » 15 months ago, # |   +39 Anyone else who hasn't received the prize for the First University Codesprint? xD
•  » » 15 months ago, # ^ |   0 Contact support@hackerrank.com if you didn't recieve prizes.
 » 15 months ago, # |   +3 Are the prizes only for top 100 university students? Can high school students win a prize?
•  » » 15 months ago, # ^ |   +113 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
 » 15 months ago, # |   +61 No prize for tourist, only coders from Earth can get it :P
 » 15 months ago, # | ← Rev. 2 →   +20 awesome editorial for querying sums on strings -_-
•  » » 15 months ago, # ^ |   +13 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.
•  » » » 15 months ago, # ^ |   +13 It was sarcastic :P
•  » » » » 15 months ago, # ^ |   +5 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?
 » 15 months ago, # |   0 I couldn't get the problem with my solution for story-of-a-tree.Help required..solution
 » 15 months ago, # |   +3 Can anyone please explain how to solve Querying Sums on Strings !!! The editorial is impossible to understand :(
•  » » 15 months ago, # ^ |   +3 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
•  » » » 15 months ago, # ^ |   0 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. :)
•  » » 15 months ago, # ^ |   +6 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.
•  » » » 15 months ago, # ^ |   0 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.
•  » » » » 15 months ago, # ^ |   0 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)
•  » » » » » 15 months ago, # ^ |   0 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: dsu_size[ x ] = 1 , if x — is S'suffix dsu_size[ x ] = 0 , otherwise
•  » » 15 months ago, # ^ |   0 Editorial is updated.
•  » » » 15 months ago, # ^ |   0 Thanks :)
 » 15 months ago, # |   +18 When will you send prizes?
•  » » 15 months ago, # ^ |   +15 looking for prize too :)
•  » » » 15 months ago, # ^ |   +8 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"
•  » » » » 14 months ago, # ^ |   +1 well to update I got my price yesterday, which is quite nice
•  » » » » » 14 months ago, # ^ |   0 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
•  » » 14 months ago, # ^ |   0 I wish they will send $10 instead of T-shirt (I got several ones ^.^) •  » » » 14 months ago, # ^ | ← Rev. 2 → +3 Send me one t-shirt, I would give you 20$ :P
•  » » » » 14 months ago, # ^ |   +15 I'd give you one for free, if you're serious.
•  » » » » » 14 months ago, # ^ |   0 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 :)
 » 14 months ago, # |   +5 I thought they said they'll give a "World Champion T-Shirt". I already have 2 of these :c
 » 13 months ago, # |   0 Did anyone receive gift cards yet?