Shafaet's blog

[HackerRank] WorldCup starts 11September / Team Contest / Awesome Prizes
By Shafaet, history, 9 years ago, In English

Hello CodeForces Community!

I am glad to share that HackerRank's WorldCup (CodeSprint on Algorithmic Programming Challenges) starts 11-September-2015 at 16:00 UTC.

Go ahead and register now at www.hackerrank.com/worldcup to show off your coding chops, and win amazing prizes like Video chat with HackerRank founders or Ahmed Aly, DJI Phantom Vision Quadcopter, Phantom 2 Vision+ Quadcopter, Apple Sport Watch, HackerRank hoodies and t-shirts! All participants who completely solve one challenge (that’s just 1 out of 6 questions!) will get $100 of AWS credits. Prizes are restricted to University Students Only.

Also, you'll get an opportunity to connect for a career opportunity with WorldCup contest sponsors — Alarm, Asana, Capital One, Fidessa, Ooyala, Shift, Sightline Systems, Wipro Digital, Verizon, Zendesk, Zenefits.

Contest scoring is 25 — 40 — 50 — 75 — 100 — 120. Tiebreaker is person to reach the score.

I invite everyone from experts to beginners to participate and solve challenges. This is going to be a really awesome contest :)

This is a multi-stage team contest. Top 50%* of teams on the Leaderboard qualify to Semi Finals. *All teams whose final score is the same as the team in the 50% rank qualify (including teams ranked lower because of time penalty tiebreaker).

GL&HF

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

Comments Comments (101)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 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 +3 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 +3 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 0 Vote: I do not like it

1) Is contest rated?

2) Should team use only 1 PC?

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

    1) No.

    2) As it can't be enforced, there is no limit on number of PC.

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

I have a question, which round prizes will be given, semi-finals or qualifiers?

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

    Finals.

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

      but finals has fewer than 250 participants

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

      on the basis of which rounds will the T-shirts and hoodies be given?

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

      I really don't understand how the prize system works. The contest page does not contain any comprehensible information on that. Furthermore, the information it contains is contradictory.
      How can there be prizes for top 250 teams if only those qualified for finals are eligible for prizes? Please elaborate on that.

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

Can graduated participants receive top prizes?

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

    Sorry, prizes are only for university students.

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

      Can high school students get prize?

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

        cout << ( "University" == "High School" ? "YES" : "NO" );

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

when will it start .i mean is it a 2 day contest?

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

    Yes.

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

      So, a contestant has complete 48 hours to solve 6 tasks ?

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

        Yes, its the qualification round, so we decided to give long time.

        → 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 -8 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 +14 Vote: I do not like it

Constant optimization requirement in Ikbal's Arrays is too damn high.

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

Here's to hoping the next rounds' hard problem will not be "implement segment tree (or some other data structure) for the 597th time".

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

    The semifinal will contain better problems for sure :).

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

6th problem had too strict time limit , I had to do stupid optimizations like fast input , fast output , and some other shits to get AC.

Also hackerrank is strange , it didnt let me create an array of size 2 * 10 ^ 7 but it let me create 10 arrays of size 10 ^ 7

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

    It didn't let me create an array of size 1<<26 but allowed an array of size 107.

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

My submissions still haven't been processed (actually its just processing and processing). Is there a problem with the grader?

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

Problem with Inversions (2nd last problem, Semi-final):

Our team managed to score 109 points out of 120, with correct answer on all except 2 testcases. Can someone who used segment tree / fenwick tree in their solution please explain their algorithm briefly?

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

    Which problem? The one with the inversions?

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

      Yes, that one — Lauren and Inversions.

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

        Well, we didn't solve it using fenwick tree.

        We did the following while there was time left (for 1950 ms or so): Look at the i for which i - a[i] is largest (and i hasn't been chosen before). Take this as the right index to swap. We can find the best left index to swap it with in . If this is better than the current best, save it.

        We didn't expect this to pass, but apparently it did :) Also, we have no argument why this would work guaranteed; but the heuristic makes sense.

        Code: https://github.com/TimonKnigge/Competitive-Programming/blob/master/HackerRank/lauren-and-inversions.cpp

        [My teammate solved it, so what I posted before was not what we actually did.]

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

          For fixing the right index to swap, we found out the largest number which had minimum inversions on its left side, and found the best left index to swap with in n*logn . Turns out that ours wasn't that good a heuristic :) Thanks!

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

    Our solution passes all test cases and works 0,39sec (and what is more important, we can prove it).

    First, lets look at this chain (we will call it "left chain"): a sequence, which starts with a[1] and every next term is the closest to the right that has larger value (than the previous term). For example, for permutation 2, 1, 4, 5, 3, 6; their "left chain" is [2], 1, [4], [5], 3, [6].

    Second, lets look at the "right chain". It's like the "left chain", but starts at a[n] and goes left (every next term is closest to the left, that has smaller value). So, for permutation 2, 1, 4, 5, 3, 6; it is 2, [1], 4, 5, [3], [6].

    Nice! Now, lets notice, that the best swap pair should have its left number in the "left chain" (otherwise, we can improve that swap pair). Similarly, the best swap pair should contain its right number in the "right chain".

    Good! Now we can move on. Lets look at some number, which is not term of the left nor the right chain. This number has some range of terms in the left chain, which are "to the left and bigger" and some range of terms in the right chain, which are "to the right and smaller". So, this number makes "+1" for some rectangle on the plane (indexes of the left chain, indexes of the right chain).

    So now, our problem is this: we have some rectangles, find how many rectangles has non-zero intersection. This is a classic problem, which can be easily solved with a segment tree.

    The complexity of the solution is O(n log n).

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

      "this number makes "+1" for some rectangle on the plane"

      Can you please explain how is a rectangle defined here exactly?

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

        Imagine a plane, where there are terms of the left chain as one axis, and terms of the right chain as the other axis. On the intersection you have number of inversions, which will be produced by this pair, if we swap them.

        Then for a fixed number which is nor a term of the left chain nor a term of the right chain, there is a fixed range in OK-terms in the left chain and a range in the right chain. range x range = rectangle =)

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

How to solve problem World Cup City?

We've writed this solution: if K is less than sqrt(N), then just interate over all possible pairs of indexes and calculate LCA in O(1). So, this case complexity is O(K2). Otherwise, if K is bigger than O(sqrt(N)), than just run standart dynamic programming solution in O(n).

I believe, that the complexity of this algo is O(Nsqrt(N)). But, our solution works 1.95sec (with TL 2sec) and barely passes TL (even after some optimizations). Is there some faster solution?

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

    We did centroid decomposition with O(Nlg(N) + Mlg(N)2)) complexity and same TL problems.

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

      What kind of centroid dec. did you write? My centroid dec. O((n+k)logn) solution works with max 0.6 sec. K is sum of set sizes.

      Here is the code : Link

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

    We had the same solution in O(Nsqrt(N)) but didn't manage to pass TL on 5 test cases, with all optimisations :/

    Then we wrote solution with central decomposition — you can fix one central node, count all pairs of residents which should go through the fixed node (you can do that in O(Rlog(R)) where R is the total number of residents), and then delete fixed node and do recursivly the same thing for it's subtrees. So the total complexity is O(log(N) * (Rlog(R) + N)) and it works in 1.5s.

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

    We had O((sumk + n) log (n)) solution.

    For each query we sort all cities by tin, find all lca of neigbours and then create "mini-tree" of this lca's and vertices. it has <= 2k vertices maximum.

    Now what you need is to solve in O(TreeSzie). it may be done by calculating for each vertex number of elements in its subtree.

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

    We did a method similar to finding LCA via HLD.

    Initially, when a query comes we put all nodes in a priority_queue. Now at each step whichever node has the deepest chain head is shifted up to correct position and corresponding number is added to the answer.

    By correct position I mean the node is shifted up to the first node above it in its chain, if it exists, or to the parent of the chain head. If another node exists above it in its chain then after moving the node up I just merge them and treat the entire thing as a single node in the future.

    And by corresponding number I mean if a bunch of x nodes were shifted up by distance y, then I add x.(k - x).y to my answer, where k is the number of total nodes.

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

    In case anyone is interested, here is our code, using the same approach as Alex Dmitriev. In retrospect, we overcomplicated the actual calculation, since we first calculate , and then subtracted the paths from the LCAs to the root.

    link to code It runs in about 1 second.

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

    What is the "standard dynamic programming solution" that you used for K > O(sqrt(N)) ? Can you provide some link/explanation for that approach?

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

      for each edge calculate how many times we pass from this edge. if edge goes from u to v, it will be cnt[v] * (m — cnt[v]) where m — count of residents. cnt[v] — count of residents in subtree

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

I decided to solve "World Cup City" after contest, but when I try to submit, it shows this message,
"Individual submissions are not allowed in this contest. Please create a team for this contest in order to participate."
But we have a team, and I can't submit my solution. Is it a bug or you decide to don't accept the practice?

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

    Once Finals will be over contest will be open for individual submissions.

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

      Are you sure about it?

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

        Yup I have the practice contest ready and waiting for approval, once done It'll be launched in 2 days.

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

So, regarding finals:

Initially you don't say anything(by saying I mean notif.) about partial scoring or additional test cases. But you are actually being shown partial scoring in prelim. tests, so you think obviously there is partial scoring. Halfway into contest you release a notif. about no partial scoring after additional testing. Then you release a notif. in last 45 minutes about partial scoring being present. Certainly not the best way to go about it. It only makes sense to decide things before contest and not the halfway around or not after the contest(based on how many people have solved what).

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

    Yes this bugged me as well. Whether or not partial scoring is available has a huge influence on your strategy. The decision afterwards to only do binary scoring for the third problem was very arbitrary as well (I hated it especially because I was two testcases away from a full score), it says "after considering very few AC only challenge bear and safe is binary.", even though at the time of writing it hadd less full-score submissions than the second problem, and more than the fourth..

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

    It's very difficult to understand the decision of the organizers. The problems were great, but they decided to spoil the whole round by changing the scoring system two times in the middle of the round. Now the final round was more like a joke.

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

How to solve Alice and Bob (and string)? We've got AC, but our solution is ~500 lines of code, with suffix tree, suffix array and some additional magic. Is there simplier solution?

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

    Our solution is suffix automaton + suffix array + binsearch on answer.

    adamant has said that our solution is overkill :)

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

    Build suffix automaton on reversed string and calculate winning states. On the next step you have to deal with lexicographical order. There is a fact that suffix link tree in suffix automaton is a suffix tree to the reversed string. Given this, you can calculate winning states and find k-th winning string using suffix link tree. Also, this solution is described in editorial.

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

Regarding finals :P

img

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

In qualifications there wasn't a single problem with with binary scoring.

In semifinals there wasn't a single problem with with binary scoring.

5 hours into the contest, not single sing of binary scoring. No notifications, nothing.

You were showing partial scoring during the contest.

And then "... Binary scoring is only for challenge bear and safe."

Thanks a lot.

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

When are we suppose to receive the email regarding the prizes ?

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

Alright, I got an email, but when I clicked the "Claim your prize" (I am eligible for a hoodie) button I was redirected to my profile settings. Was that a silent hint that I'm supposed to make sure my address is filled in, or am I missing something?

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

    As I remember we will get another email which is not from Hackerrank.

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

    Our team hasn't received an email.

    Is there someone else who hasn't received ?

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

      You can expect an email in next few days, if you don't you can inbox me your user-name.

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

    I asked for support and they told me this:

    "I hope you have the access to click the “Claim Prizes” button that will take you to your profile page where you have to complete your shipping address within your profile and we will get your prizes delivered within 2 weeks."

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

hi guys did anyone receive the t-shirt ?

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

    I am still waiting for the T shirt! :(

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

    Still no T-shirts here. Has anyone received one ?

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

    Please wait a bit longer. Given high volume participation, your prize will be delivered to you a few weeks after you completed your address on HackerRank.com. Please make sure your address is 100% complete including Country and area code

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

      It's been 4 months, I still haven't got the sweatshirt. Also, no mails have been replied to. PS- Both my teammates received theirs' a month ago and mine hasn't been dispatched and shows the same status since more than a month.

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

I think T-shirts are "made in mars". Not reached yet :(. Sorry hackerrank.

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

did anyone receive the t-shirt ?

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

    Nope

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

    no.

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

      xD

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

        Did you received email? Did anybody received email about hoodies?

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

          People have started to receive the prizes though a bit slowly because of high volume. Please wait patiently for a little longer, all eligible people will surely get the prizes.

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

    I received mine about 10 days ago.

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

Still no t-shirt :( Has anyone else got their t-shirt?

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

    I received mine a week ago. Make sure all your address details including country are filled properly. You should receive a mail from DHL once you're done. They require a photo of your identity proof before they dispatch.

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

No tshirts yet !!

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

It's been 4 months, I still haven't got the sweatshirt. Also, no mails have been replied to. PS- Both my teammates received theirs' a month ago and mine hasn't been dispatched and shows the same status since more than a month.

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

I kind of feel sad: My brother got his T-shirt but I didn't :D

→ Reply