Hello CodeForces Community!

HackerRank is back with another World Codesprint! Join us on 21st May, exact time can be found here.

Its your chance to win upto $2000 Amazon gift cards/bitcoins and tshirts. [Note: Winners from US and India will receive Amazon Gift Cards. Winners from other countries will receive equivalent USD amount in bitcoins.].

Contest duration is 24 hours. The contest will be rated. If two person gets same score, the person who reached the score first will be ranked higher.

The challenges were prepared by osmanorhan, muratt, ma5termind, forthright48, cherrytree. I would like to thank wanbo and malcolm for helping to prepare this round.

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: The contest is in 2 hours.

Score Distribution: **15-25-40-50-60-70-80-100**

Edit: Rating updated!

Winners:

Are there any penalties for wrong submissions?

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

So, time of the last correct submissions and no penalties for wrong submissions.WAT? How is it possible that such civil countries as Serbia or Belarus ended up in this list? Is it a joke?

Its not that we hate these countries in the list, there are some legal restrictions to send prizes in these countries.

The world itself is a joke :(.

Its not you, but your partners from US hate these countries in the list.

It's not about how civilized it is.

It is wrriten Serbia ad Montenegro, and that country doesn't exist :P

Another great problem set, but this one felt too simple for such contest. Too bad I was so slow.

Glad to know that you liked the problem-set. This time we tried to make the problem-set a little easier than the last one. But may be another hard problem would be better.

Very nice problems. Though, I agree with Al.Cash that it was a bit too easy.

Do you consider breaking ties with an approximation problem? Something without known optimal solution. If not then are reasons technical? Yesterday, I've completely lost motivation after seeing 3 participants with full score. I would prefer an other system but the current one is fine.

Thanks for your feedback. I didn't expect so many top people in just after world finals. I agree that the problem-set was too easy for top people but at least it problems were nice :).

What about the part with breaking ties? Any chance to see tie-breaker challenge in the near future?

I personally don't really like the idea of tie-approximation problem (esp, for 24h contest (I mean not several days))

*I don't say that it's bad per se, but if we want competition in solving approx.problem, let's create competition that consists of approx.problem

Contest was interesting and good. For my opinion previous one was better, but also this is cool :) In last time, longer HR contests became my favourite in competetive programming.

I managed to solve first fourt tasks and sixth. I can not find bug in my seventh task. I tried several testcases and always everything is ok, but I got 0 points :(

My opinion about problems:

First task is easy, possible the easiest one which I solved in last 2 years :D

Second task is also good, nice idea, but for my opinion it is harder then third.

Third task, another constructive algorithm, for me it was interesting, but on previous round third task was much harder.

The fourth task, my favourite on the round. I spent a lot of time to solve it. Cool for that place !

I didn't read the fifth task, I saw big statement, I will do it later :)

Sixth task is good, I spent a lot of time to solve it. My solution in dp with Catalian numbers. I can not believe there is so many good submissions. I am interested whether some great coder can solve it in case when we have 200 square brackets and 10

^{5}parentheses ?Seventh task, for me was easier than fourth and sixth. But I had some implementation bug. I done it with dsu + priority_queue + set. Sort all edges and add one by one and check whether we get answer for some query now. If someone has free time, please look at my code and suggest me what can be wrong : solution

Last task were easier than it should be, but I think nobody expected so many top coders in ACM week :P

My advices:

You should have easier second task, one more on level as 8th problem and the last thing you should put clear subtask in each statement. It is not very big job, but for all contestants it will be much better :)

See you on Week of Code, I hope another great problemset !

Are there any ideas for "Travel in HackerLand"? It seems to be more difficult than the last problem.

You need to binary search the answer for each query. To speed it up, you need to do these binary searches simultaneously.

My Code

Complexity:

O(mlogm+logm(qlogq+nlog^{2}n+m+qlogn))You wrote loq instead of logq. It's

O(N*log^{3}(N)) bro, don't kill the latex :(Iterate over roads sorted by cost. Find&Union with adding smaller CC (connected component) to larger one, to amortize complexity. For each CC also store (in "set" from STL) set of queries where both

x_{i}andy_{i}are already in this CC. Such set of queries should be sorted by the required number of types of buildings. After merging two CC's you need to check the first query from the set (the one with the least required number of types of buildings) and check if maybe there are enough types of buildings now.My code (there is some small bug and it didn't pass 2 small tests. I resolved it by submitting it again with brute force, run if the input is small)

I remember few informations when merging subtrees:

I answer query online:

More or less — I think answering query is O((log^n)^2).

So the total complexity:

time — O((n+q)(log^n)^2 + mlogm) memory — O(n lg n).

Is there something better, than:

Y^{3}log(X) +TY^{2}log(X) in 6th taskq*sqrt(nlogn) in 7th tash

in 8th task?

6th: Y^3 + T * Y

7th: NlogN

8th: NLogN. I think problem 8th can even be reduced to O(n)

I did the 8th task in O(n), using DP. Given the answer for v, we can calculate the answer for each of its children, using some values. If col[v] == col[par], ans[v] = ans[par]. Else ans[v] = ans[par] — A + B. A is the number of nodes in the subtree of v which can be reached from v without encountering any node of color col[par]. B is the number of nodes above v, which can be reached from par[v] without encountering any node of color col[v]. Hope this helps. :)

Well, actually the solution is how to count these A and B values? Which I didn't figure out.

Okay. So, you can calculate both using the same parameter arr[]. arr[i] denotes the number of nodes in subtree of i reachable from i without encountering any node of color col[par[i]]. Initially arr[i] = subtree_size[i]. Now do a DFS. Whenever you're at a node v, find its most recent ancestor having same color (let it be a) and subtract subtree_size[v] from its immediate child which is an ancestor of v. At the end of the DFS, arr[] will have the necessary values.

Now, regarding A and B. You can directly get A from arr[]. For B, find the most recent ancestor of node v which has same color, and then go to its immediate child which is ancestor of v. There you get the value of B. Also, the case when a node has no ancestor of same color has to be handled separately. I hope this makes it clear. :)

Thanks for the explanation :)

Thanks for the explanation. Wouldn't the solution be O(nlogn) due to finding ancestor of same color for every node.

I believe you can remember the position for each color on the stack.

So when you enter the vertex of color c, you add it to the stack S[c]. You also remove it from S[c] when you exit dfs.

Ah right. But that can again be reduced to O(1) using a method similar to how we found the nearest ancestor having the same color.

How to count the number of nodes in the subtree of v which can be reached from v without encountering any node of color col[par] in O(1)?

Please see my comment above. :)

There is an

O(X+Y+TlogMOD) solution for the 6th problem.Related paper

There is a formula for 6th task. My solution looks like this

Can you please explain a bit about how you derived this?

I started with counting sequences where parentheses and brackets are non-distinguishable.

Then I noticed that if we fix some correct brackets sequence then we can insert parentheses sequences into it in 2

x+ 1 positions. In each position we can insert sequence of lengthl_{i}(Σl_{i}=y), and there iscatalan[l_{i}] such sequences.These considerations lead me to the easy dp to count number of ways to split

yitems into 2x+ 1 groups, which could be computed inO(Y^{3}logX) using matrix exponentiation. But it was too slow.Then I printed answers for different inputs and noticed that output is very familiar sequence: it was a catalan's triangle with well known formula to compute ;)

I did the same, but I didn't recognize these values. Instead I noticed some pattern how to compute each cell in O(1) based on the 2 already computed cells.

My algo was O(X*Y^2), after pattern notice reduced to O(X*Y).

i did 6th in

O(sqrt(N) *M*M+M*T) . Basic idea wasdp(i,j) = number of ways to placeJpairs of brackets inIslots . Answer isdp(2 *n+ 1,m) *catalan[n] *factorial[n] *factorial[m]. This has complexityO(N*M*M). To optimize this i precalculate answer for alldp(N,m) whereN=i*sqrt(n) for integeriand alsodp(i,j) where 1 ≤i≤sqrt(n) . With this precalculation takesO(sqrt(N) *M*M) time and each testcase takesO(M) time.This trick is pretty amazing. There are so many unique solutions for each of the harder tasks of this contest :D

The 7th task (Travel in Hackerland) can be done in

O(NlogN) and we can process the queries online as well.I built the reachability tree for each connected component of the graph.

Now a query (

u,v,k) reduces to finding the lowest common ancestor ofuandvthat has ≥kdistinct values in it's subtree. We can precompute number of distinct values for every subtree in the reachability tree inO(NlogN). Answering each query can then be done inO(logN) using binary jumping.Mine was nlog^3n and offline. Your solution is really amazing.

Thank you :)

Can you share your code?

Solution — Travel in Hackerland

Yeah I did the same except I found the number of distinct elements online using Pesistant Seg Trees.

Editorials are available for all problems except the 4th question, please make it available. Thanks.

editorial for all problem is live, please check.

Could someone explain the merging part of the 6th question in a bit more detail than in editorial?

I can try:

1 [ 2 [ 3 ] 4 [ 5 [ 6 ] 7 ] 8 ] 9 -> I showed 9 positions for the sequence [ [] [ [] ] ], which has 4 [] pairs.

The number of such ways equals Cat[X], so now let's pick one and think in how many ways we can insert Y () pairs.

We have Y () pairs and 2*X+1 positions to insert them. In each position you can insert between 0..Y pairs of () and the sum over all positions must be equal Y. Moreover if you decide to insert k pairs of () on one position, you can also do that in Cat[k] ways.

So for example, you have 3 positions and 3 () pairs, you can insert them in the following ways:

Cat[0], Cat[0], Cat[3]

Cat[0], Cat[1], Cat[2]

Cat[0], Cat[2], Cat[1]

Cat[0], Cat[3], Cat[0]

Cat[1], Cat[0], Cat[2]

Cat[1], Cat[1], Cat[1]

Cat[1], Cat[2], Cat[0]

Cat[2], Cat[0], Cat[1]

Cat[2], Cat[1], Cat[0]

Cat[3], Cat[0], Cat[0]

So now you have the following question: given Y pairs of () and 2*X+1 positions, compute the number of ways in which you can insert pairs into positions. And a lot of papers and formulas in this thread were devoted to explain how to compute this efficiently.

Does anyone know how to get a T-shirt in Hackerrank? A month ago I won a T-shirt in another contest. However, it seems that the organizers have not informed me about the T-shirt.

I also didn't get the T-shirt from January Codesprint. And still no information about prizes from April Codesprint.

I got the T-shirt from January Codesprint and an equivalent of 75 USD in BTC as well.

But still no prizes from April Codesprint, maybe we have to wait...

For last april codesprint, the tshirts are being sent now. Are you talking about any other contest? You can inbox me.

And what about 75 USD in BTC for the April contest? I didn't received any email where I could specify my BTC wallet

Do you know when the T-Shirts from booking.com contest ( https://www.hackerrank.com/contests/booking-hack-a-holiday/challenges ) will be sent out?

I will use this subject to voice my opinion.

The problem I am seeing during Hackerrank contests is discussing different ideas/approaches of the problems during contest. It looks like nobody is actively monitoring that forum — people are asking about complexity, programming techniques used to solve the problem, etc. Even though during Week of code it is theoretically forbidden to post even test cases.

I also pointed that problem out to one of the task author during contest but there was no reaction. Would it be possible to actively monitor the discussions or disable them at all (not the best solution though)?

This is one problem I am aware of. I agree that its very bad when someone posts a spoiler, corner case etc. I try to monitor the contests I manage but I can't monitor 24 hours. We will try our best to figure out a solution for this before the next contest.

Moderated comments maybe? So, comments are hidden by default and only a moderator can reveal them.

Maybe you can at least try to do something with this during current contest? People are describing the solutions in the discussions...

Yes yes I am TooDifficuIt.

Interesting,

I "won" the $750 dollar prize, which means I am izban = P

I also got a message that I won the contest.

Also in the April contest I got a wrong message.

I got two messages with prizes. I actually won neither. Seems legit :^)

I got all three messages, apparently i am 1,2 and 3 altogether lol xD

But still no prizes for nothing.

Is there anyone who hasn't got their BTC? Mine in April and May Codesprint one hasn't come.

Yep, still waiting for the May prize. And their support ignores messages.