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!

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

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.

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.

Well, you always can send them to mee_)

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

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

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?

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

We will try to.

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

deepestpoint, i.e. with maximal value ofsum_{i}=depth_{xi}+depth_{yi}. Suppose its index ish.Distance between two vertices (not points)

x_{i}andx_{j}equals todepth_{xi}+depth_{xj}- 2 *depth_{lca(xi, xj)}. I proved that if pointsiandjare the furthest, thenlca(x_{i},x_{j}) lies on the path fromx_{h}to the root (similarly fory's). Let's denotexlca_{i}=lca(x_{i},x_{h}),ylca_{i}=lca(y_{i},y_{h}). Then, there are two cases:iandjis equal toh.xlca_{i}is an ancestor ofxlca_{j}andylca_{j}is an ancestor ofylca_{i}(remember they all lie on a path fromx_{h}ory_{h}to the root).This leads to the following solution.

hof thedeepestpoint.xlca_{i}andylca_{i}.y_{h}to the root.depth_{xlcai}and, in case of a tie, in increasing value ofdepth_{ylcai}.Basically, I process points as the

xlca_{i}goesupthe path fromx_{h}to the root, and I proved that I only need to check those points processed before that haveylcaaboveylca_{i}. Point processing consists of just 3 operations:sum_{h}+sum_{i}- 2 * (depth_{xlcai}+depth_{ylcai}), to account for the first case.sum_{i}- 2 *depth_{xlcai}+SegmentTree.maximum(0,depth_{ylcai}) (right border included).depth_{ylcai}withsum_{i}- 2 *depth_{ylcai}.My code (not the cleanest): https://www.hackerrank.com/contests/world-codesprint-8/challenges/tree-coordinates/submissions/code/8180255

From article, this problem becomes to "exercise 2.3". Embed tree metric into

l_{∞}^{O(logN)}.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 =)

Try again, you can access now.

My solution :

pwithmax(depth[x_{p}] +depth[y_{p}]).qwithmax(dist(x_{q},y_{q}));porqwill be one of the necessary points.I could not prove or disprove this solution. My code.

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?

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

Root the tree and for each subtree

Scalculate the answer using only pointsiwithx_{i}inS.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

S_{2}.If there are more than such points, we first precalculate for each vertex

vthe distance of the furthest point with to (root(S_{2}),v). This can be done inO(N) by some dfs. For each pointiwith the distance to the furthest pointjwith is the precalculated value fory_{j}+dist(root(S_{2}),x_{j}).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.Can somebody describe his 90+% solution on approx problem? I wasted pretty much time on 84%(71.4 points)

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.

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`

: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 Ω(

n^{2}).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.

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.

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?

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