Shafaet's blog

HackerRank University Codesprint 2
By Shafaet, history, 8 years ago, In English

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.

  • Vote: I like it
  • +64
  • Vote: I do not like it

Comments Comments (34)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Alumni have no eligibility to win prizes but are rated?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Rated for everyone.

    → Reply
»
8 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +113 Vote: I do not like it

    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

    → Reply
»
8 years ago, # |
  Vote: I like it +61 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

awesome editorial for querying sums on strings -_-

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      It was sarcastic :P

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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?

        → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    To compute f fast we can:

    1. create word W = s#w_1#w_2#...#w_q#

    2. 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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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
          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Editorial is updated.

    → Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

When will you send prizes?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    looking for prize too :)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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"

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        well to update I got my price yesterday, which is quite nice

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wish they will send $10 instead of T-shirt (I got several ones ^.^)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Send me one t-shirt, I would give you 20$ :P

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        I'd give you one for free, if you're serious.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :)

          → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I thought they said they'll give a "World Champion T-Shirt". I already have 2 of these :c

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone receive gift cards yet?

→ Reply