Shafaet's blog

By Shafaet, history, 4 months 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, 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.

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

»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Alumni have no eligibility to win prizes but are rated?

  • »
    »
    4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Rated for everyone.

»
4 months 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

»
4 months 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?

  • »
    »
    4 months 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

»
4 months ago, # |
  Vote: I like it +61 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

awesome editorial for querying sums on strings -_-

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      It was sarcastic :P

      • »
        »
        »
        »
        4 months 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?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Help required..

solution

»
4 months 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 :(

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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. :)

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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)

        • »
          »
          »
          »
          »
          4 months 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
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Editorial is updated.

»
4 months ago, # |
  Vote: I like it +18 Vote: I do not like it

When will you send prizes?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    looking for prize too :)

    • »
      »
      »
      4 months 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"

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 months 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

  • »
    »
    4 months 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 ^.^)

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 months 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 :)

»
4 months 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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone receive gift cards yet?