Shafaet's blog

HackerRank World Codesprint
By Shafaet, history, 9 years ago, In English

Hello CodeForces Community!

I am glad to share that HackerRank's World Codesprint is scheduled on 29-January-2016 at 17:00 UTC. Contest duration is 24 hours.

Go ahead and register now to show off your coding abilities, and win upto $2000 Amazon gift cards/bitcoins, medals and tshirts. [Note: Winners from US and India will receive Amazon Gift Cards. Winners from other countries will receive equivalent USD amount in bitcoins.]

The contest is sponsored by Distil-networks, Pampared-chef and Philips. Contest site will be continually updated to reflect upcoming sponsors.

The problems were prepared by malcolm,Errichto,svanidz1, forthright48, and Shafaet. Thanks to wanbo for testing the problems.

The contest will be rated. If two person gets same score, the person who reached the score first will be ranked higher.

Editorials will be live soon after the contest ends, I invite everyone from experts to beginners to participate and solve challenges. I hope everyone will enjoy the contest.

Update: Scoring: 15-25-40-60-80-80-100-100. All the problems will have partial scoring unless explicitly mentioned in problem statement.

Update:

Contest is over. Congrats to the winners.

anta

cgy4ever

Eryx

zeulb

shangjingbo

Hackerrank will contact the winners for prizes very soon! Please share your opinion on the contest in comments, it will help us to improve. The next contest is Hourrank, see you there!

Code the future

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

»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

What an intersection!
Both contests on cf and this one start at the same time!

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

Winners from US and India will receive Amazon Gift Cards. Winners from other countries will receive equivalent USD amount in bitcoins.

Just mentioning this for the others because it's in the rules but not in the announcement. For me personally an Amazon Gift Card would be better, but I guess tough luck =)

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

    You are right, I should've mentioned it. Added it in the post now, thanks.

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

      Also, there is bad news for tourist.

      Residences of the following countries and territories are not eligible to win prizes due to legal restrictions: Antarctica, Afghanistan, Cote D'ivoire, Cuba, Belarus, Bouvet Island, British Indian Ocean Territory, Cameroon, Central African Republic, Christmas Island, Equatorial Guinea, Haiti, Heard Island and Mcdonald Islands, Iran, Islamic Republic of Iraq, Democratic People's Republic of Korea (North Korea), Lao People's Democratic Republic (Laos), Lebanon, Liberia, Libyan Arab Jamahiriya, Myanmar, Nigeria, Pakistan, Papua New Guinea, Serbia and Montenegro, Sudan, Syrian Arab Republic, Zimbabwe.

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

      Hi! Could you please explain the reasons of non-eligibility of Belarus residents?

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

        Probably because you're an evul dictaytorship to some countries.

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

Has anybody received T-Shirts from the university world cup?

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

    If you (or anyone else) haven't received it yet, please inbox me your hackerrank username and make sure your profile contains your address.

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

    NOPE. I've sent multiple emails, no reply. The DHL website shows the same status since last few months.

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

    Yes, i have received it dude :)

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

    Yes, I have also recieved it, just before 2-3 days

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

Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).

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

It's not a good idea to announce about HackerRank contest on CodeForces's website that conflict in start time with CodeForces round.

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

    Well unlike codeforces they don't care about community.

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

      Its not true that we don't care. We exist only because the community exist, not the opposite.

      We re-scheduled our contest time because of conflicts several times and we will do so in future too. This time we couldn't do it due to many reasons.

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

Can you double check the test case of the last problem? It looks like lots of us are getting 46.67pts including tourist.

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

    There was an issue with the tests. We fixed and rejudged it. We are extremely sorry for this.

    (You now got full points.)

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

      All right, I gave up on the contest after not being able to get the very first problem accepted. Now that's a bit disappointing.

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

        I totally understand the disappointment :(. Still only 5 people got full score till now, I hope you will start again and end up in top 10.

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

        Now I know how to stop you to solve the hardest task in 7 minutes :P

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

      The test cases still seem weak. My first submission passes while it should not (test case "288 18").

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

    I am very sorry for issues with the last problem. My program wasn't correct. Unfortunately, tester made the same mistake (without seeing my code).

    I will write a few more words later today (there is the FHC in half an hour), to explain what I did wrong and how it could be avoided in the future. In short, I should have written a checker and consider the possibility that my outputs aren't optimal — then the checker should crash or something.

    tourist, I apologize you as much as I apologize other contestants. Sometimes organizers make a mistake. I know I fucked up but it was your choice not to do other problems. It was reasonable (because likely one must solve all problems to get prizes) but it has a disadvantage that organizers' mistakes affect you terribly.

    I'm sorry.

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

Where are the time limits, memory limits for the problems given ?

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

Bear and Cryptography: precompute solutions for odd K (only powers of 2); for even K, keep decreasing N and factorising till it gives K factors. A very optimised factorisation gives full score.

Build a String: O(N3) DP, various optimisations and bucketing of suffixes by the first two characters: 72/80 points.

Self-Driving Bus: adding vertices + union-find, O(N2) checking which intervals give valid answers. Once again, optimisations. If there's no chance of it running in time, try a stupid (but fast) guesstimate (4 tests passed this way, lol). 80+/100 points.

ヽ༼ຈل͜ຈ༽ﾉ

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I got rank 270. Cool, congrats to everyone who won :D

I was wondering, how do you guys plan to send the gift cards? I mean, I don't have an Amazon Account associated to the email I use for HackerRank, is it possible to transfer the card to some other account/shifting it to bitcoin?

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

    I don't have answer at this moment. You will get email. If I get the answer, I will let you know.

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

    Last time I won an Amazon Gift Card from Hackerearth they mailed me a Claim Code. Could use it on any Amazon Account.

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

why "Current Rank" is not the same as the rank in the Leaderboard?

UP: ok, it takes some time to be updated

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

Rank 11 again. Whyyyyyyyyyyy?

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

Problem "Build a String" can be solved in O(N) using suffix automaton, and I think this approach is easier than author's.

Problem "Self-Driving Bus" has O(NlogN) solution with centroid decomposition, which is also easier than author's HLD.

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

    Could you elaborate on these solutions? I thought about applying both techniques but discarded them because I couldn't figure out how to make them work.

    As a side note, I had a slightly different solution for "Self-Driving Bus". My solution relied on the fact than a connected segment of size x has x - 1 edges between its vertices. Checking this property for different left ends of the segment reduces to maintaining the number of zeros in an array subject to range sum updates. Code here: https://ideone.com/hVosff

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

      Problem 1. We need to maintain the longest suffix which appears in the string somewhere before. We store it's starting index and respective state in the suffix automaton.

      When we add a letter:
      1) Extend SA with this letter.
      2) We need to extend our suffix with this letter. So we follow suffix links from the current state until there's an edge by this letter.
      3) Now we need to make sure our suffix doesn't intersect with its previous occurrence. To do that, in every SA state we need to know the first index where corresponding string ends (it's computed in constant time). While this index is greater than our suffix's starting index — we decrease suffix length by 1, or delete it's first letter. What this means in SA: if the length became not greater than length of state reached by link from current — we follow the link, otherwise we remain at the same state.

      All checks are done in O(1) and in total we move some pointers not more that O(N) times.

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

        While this index is greater than our suffix's starting index — we decrease suffix length by 1, or delete it's first letter.

        Please elaborate why is it O(n) in total. I wrote same thing but the proof is not obvious for me.

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

          Suffix length increases by at most one for each letter added and it can't go below 0, so in total it will decrease not more than N times.

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

            So we follow suffix links from the current state until there's an edge by this letter.

            What is the current state? Do you iterate every time from the longest state?

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

              Of course not. We maintain the state corresponding to longest suffix that can be copied.

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

                Well, I do iterate from the longest state :)

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

      Problem 2. We have tree center and we need to know how many good intervals contain it. If it has index v, we'd try to add for example v - 1 to the interval. This means we also need to add all the numbers on the path from the center to node v - 1, but we're only interested in minimum and maximum. We're building continuous interval, so we need to add all nodes between those minimum and maximum, and it's like a transitive closure.

      Now the solution:
      1. Find the center and run dfs to find min and max for all reachable nodes.
      2. Find transitive closure (update those min and max to final values after we add all nodes between min and max). Surprisingly, this is done with a couple of simple loops in O(N).
      3. Run 3 pointers: decrease left interval border, and maintain minimum and maximum possible right interval border and count of possible right borders between them. We just need to sum up those counts for all left borders.
      4. Remember that we split the graph in the center, so current part may not contain all the nodes, and once we get a gap in the interval that has nodes from another part — we stop.

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

    For "Self-Driving Bus", I also thought about centroid decomposition at first. But then I realized, we can also use the center of an interval instead of the center of the tree. So my solution only have a quick-sort like algorithm with BFS.

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

    I solved self driving bus with a segment tree with lazy propagation only. Here is the code: http://paste.ubuntu.com/14799263/ . It is way easier that hld or centroid decomposition.

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

      Can you elaborate a little on it?

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

        Basically we have to find the number of pairs [l,r], such that the number of edges (a,b) such that l<=a,b<=r equals r-l. This implies r = l + number of such edge. Say initially each nodes value is their number. So lets run a loop from 1 to n. each time pick all the edges that start with a previous node and ends at current node and increase the value of each nod from 1 to this edge's other end. Then count the the number of previous nodes with value equal to current node.

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

    Can you prove that your solution for "Build a string" using suffix automaton works in O(N)?

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

How to do build string using suffix array by using binary search. I am unable to understand the tutorial. can someone explain?

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

    dp[p] = min cost to build string s[0 .. p]

    note: dp[p] >= dp[p — 1]

    In order to compute dp[p] we have two cases: - p-th character is appended, cost = A + dp[p-1] - p-th character is pasted, this means there is point k splitting the string in two, s[0 .. k] and s[k+1 .. p], k can be found using binary search

    How to check if s[k+1 .. p] is in s[0 .. k]? Using suffix array and longest common prefix table we can find two values L and R, L <= SA[k+1] <= R, these values represents all the occurrences of s[k+1, p] in s, this can be done using binary search, now we are interested in the leftmost suffix containing s[k+1, p], this can be done with segment tree.

    The overall complexity is O(N * log^3(N)).

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

      What array a[] contains in tutorial code. And how the author calculated suffix array? by using hashing or something

      → Reply