Shafaet's blog

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

Hello Codeforces Community, I am glad to share HackerRank World Codesprint 8 starting on 17th December 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.

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 7 normal algorithmic challenges and 1 approximate challenge in this contest. I highly recommend you to read all the problems. Most of the problems contain cool figures :).

The problems are prepared by svanidz1, malcolm, darkshadows, kevinsogo, robinyu, torquecode and me.

I would like to give special thanks to Wild_Hamster who worked really hard to finalize the problems and testing the data. Also thanks to wanbo as always for testing.

Update: Score of the problems are 10-20-30-50-60-75-85-100. The last problem will have binary scoring.

Update: The contest has ended, editorials are now available. Congrats to the winners!

Ratings will be updated soon. Don't forget to give your feedback!

Happy Coding!

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

»
8 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Just curious, did you guys hire Wild_Hamster for testing after reading his blog (http://codeforces.me/blog/entry/48380) on how to pass inadequate solutions in hr?

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

    Smart move, isn't it? ;)

    I wouldn't use the word 'hire', but he is a nice guy who is willing to help us to improve. I hope no one will be able to hack solutions this time.

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

      One more thing, why don't you guys change the design of the tshirt? i'm bored of getting the same tshirt with "world champion" written in front of it again and again. i hope the tshirt i will get for this codesprint will be different and unique.

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

        Well, you always can send them to mee_)

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

Is the "approximate challenge" for the purpose of tie-break? It seems that "approximate challenge" of HackerRank is usually too weak to tie-break.

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

    Yes.

    Usually hackerRank contests don't have approximate challenges, we had an approximate challenge in the last university codesprint after a really long time and yes that challenge wasn't quite strong enough to break tie. I believe this time the approximate challenge is harder and better and will be good enough to break tie.

    We will know after the contest ends :).

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

I can't connect to hackerrank with Chrome, it gives the following error: NET::ERR_CERTIFICATE_TRANSPARENCY_REQUIRED.

It says that hackerrank uses HSTS (whatever that is).

It works fine on Firefox though.

Is it just me or others are having the same problem?

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

Are codesprints going to contain an approximate challenge from now on?

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

There's easier to code but much harder to prove and understand O((n + m)logn) solution for Tree Coordinates problem.

Let's root the tree at some vertex and compute the depth of each vertex. We will be interested in the deepest point, i.e. with maximal value of sumi = depthxi + depthyi. Suppose its index is h.

Distance between two vertices (not points) xi and xj equals to depthxi + depthxj - 2 * depthlca(xi, xj). I proved that if points i and j are the furthest, then lca(xi, xj) lies on the path from xh to the root (similarly for y's). Let's denote xlcai = lca(xi, xh), ylcai = lca(yi, yh). Then, there are two cases:

  1. One of i and j is equal to h.
  2. xlcai is an ancestor of xlcaj and ylcaj is an ancestor of ylcai (remember they all lie on a path from xh or yh to the root).

This leads to the following solution.

  1. Find index h of the deepest point.
  2. For each point, compute xlcai and ylcai.
  3. Create a segment tree for maximum corresponding to the path from yh to the root.
  4. Sort the points in decreasing value of depthxlcai and, in case of a tie, in increasing value of depthylcai.

Basically, I process points as the xlcai goes up the path from xh to the root, and I proved that I only need to check those points processed before that have ylca above ylcai. Point processing consists of just 3 operations:

  • Update the answer with sumh + sumi - 2 * (depthxlcai + depthylcai), to account for the first case.
  • Update the answer with sumi - 2 * depthxlcai + SegmentTree.maximum(0, depthylcai) (right border included).
  • Update segment tree at position depthylcai with sumi - 2 * depthylcai.

My code (not the cleanest): https://www.hackerrank.com/contests/world-codesprint-8/challenges/tree-coordinates/submissions/code/8180255

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

    From article, this problem becomes to "exercise 2.3". Embed tree metric into l∞O(logN).

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

      And the solution to this exercise is discussed in this paper (see Theorem 3.3, page 5 of the pdf).

      P.S.: Al.Cash's code seems to be inaccessible, even for people who have solved the problem (at least I can't see it).

      Edit: Thanks, Shafaet =)

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

    My solution :

    1. Find index p with max(depth[xp] + depth[yp]).
    2. Find index q with max(dist(xq, yq));
    3. Either p or q will be one of the necessary points.

    I could not prove or disprove this solution. My code.

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

      I tried to cut off many random solutions, such as: taking 200-1000 points with max(depthx+depthy), min(depthx+depthy), max(depthx), max(depthy), min(depthx), min(depthy), trying to reroot tree 200-1000 times, doing O(1) LCA. And still a couple of random solutions passed.

      Can somebody prove his random solution?

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

    There was also a slower, simpler (at least for me) solution with sqrt-decomposition in .

    Root the tree and for each subtree S calculate the answer using only points i with xi in S.

    When merging two subtrees, for each point with an x-value in the smaller (fewer points with x-values in it, not fewer vertices) subtree we compare it all the points having an x-value in the larger subtree S2.

    If there are more than such points, we first precalculate for each vertex v the distance of the furthest point with to (root(S2), v). This can be done in O(N) by some dfs. For each point i with the distance to the furthest point j with is the precalculated value for yj + dist(root(S2), xj).

    At each merge there are at most points and maybe a single precalculated value to check each point with. Each points gets merged at most times. There are at most precalculations, each taking O(M + N) time. From this the above time bound follows.

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

Can somebody describe his 90+% solution on approx problem? I wasted pretty much time on 84%(71.4 points)

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

How do we approach approximation problems? I always find it more difficult to get to these. I tried using A-star search, greedy, etc. I know with practice I will improve, but are there some resources I should be looking at the start.

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

It seems to me the model solution for Tree Coordinates presented in the editorial is wrong.

Here is a simple case where it gives the result 0 instead of the correct answer 4:

7 2
1 2
2 3
3 4
4 5
5 6
6 7
1 5
3 7

The idea is that after having divided in the x-direction, we cannot just go ahead and start dividing the current subtree B in the y-direction, because the y-coordinates may all lie outside of B. Note that dividing first by y and then by x doesn't work in this case either.

The closest "correct" solution to the presented one would be to start from the whole tree T again for the second divide-and-conquer, but this should lead to a runtime of at least Ω(n2).

It might be possible to fix this by alternating between dividing in x- and y-direction and pruning when there are no points left in the current region (which feels quite similar to working with a quadtree), but I couldn't quite get that to work during the contest.

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

    I guess, it's just bug in tester's solution. Main author's solution is here

    Honestly I don't understand editorial solution, so I can't judge it.

    Edit: wanbo's code also gives 4 for your testcase.

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

      Yeah, I didn't entirely understand the explanation either, so my comment above mostly refers to my understanding of that explanation based on the provided code.

      I'm gonna have a look at the author's solution then, perhaps that will clear things up for me.

      Given that you're part of the organizers, do you think it is possible to post the other solution in the editorial so as to not confuse other readers?

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

        I have removed the buggy code for now and added author's code. That code was written by editorialist, not tester or author.

        → Reply