Shafaet's blog

By Shafaet, history, 4 years ago, In English

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:

TooDifficuIt

fataleagle

izban

I_love_Tanya_Romanova

Al.Cash

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

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Are there any penalties for wrong submissions?

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

    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.

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it
Residents of the following countries and territories are not eligible to win prizes due to legal restrictions: Antarctica, Afghanistan, Belarus, Bouvet Island, British Indian Ocean Territory,Burundi, Cameroon, Central African Republic, Christmas Island, Cote D'ivoire, Cuba, Equatorial Guinea, Haiti, Heard Island and Mcdonald Islands, Islamic Republic of Iran, 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,Somalia, Sudan, Syrian Arab Republic, Yemen, Zimbabwe.

WAT? How is it possible that such civil countries as Serbia or Belarus ended up in this list? Is it a joke?

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

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    It's not about how civilized it is.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +63 Vote: I do not like it

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

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

    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.

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

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.

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

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

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it -16 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 6   Vote: I like it +79 Vote: I do not like it

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

    • there are already such contests (codechef, hackerearth)
    • it makes you spent much more time for the contest (instead of solving everything and go away)
    • competition transforms from [solve algorithmic problems better(faster)] to [solve algorithmic problems somehow and really-compete in approximate problem] *
    • I personally can't into these problems:)

    *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

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 105 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 !

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 7   Vote: I like it 0 Vote: I do not like it

    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 + nlog2n + m + qlogn))

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

      You wrote loq instead of logq. It's O(N * log3(N)) bro, don't kill the latex :(

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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 xi and yi 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)

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

    I remember few informations when merging subtrees:

    • remember history of parents for each node and the minimum cost of edge which caused that merge — cM
    • for each merge resulting in increased number of types, in the root add the new number of types and cost of edge which caused that merge — cP

    I answer query online:

    • find first common parent of (x,y) — check the cost of that merge = cM
    • check each common parent and find first which got desired number of different types, compare the cost of that edge cP, with cM and print max

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

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is there something better, than:

Y3log(X) + TY2log(X) in 6th task

q*sqrt(nlogn) in 7th tash

in 8th task?

  • »
    »
    4 years ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    6th: Y^3 + T * Y

    7th: NlogN

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

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +28 Vote: I do not like it

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

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

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

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 5   Vote: I like it +23 Vote: I do not like it

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

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

          Thanks for the explanation :)

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

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

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            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.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

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

      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)?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    There is an O(X + Y + TlogMOD) solution for the 6th problem.

    Related paper

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

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

    int solve(int x, int y) {
        int n = 2 * x + y;
        int val = Comb(n + y, n) * (n - y + 1) % MOD * pmod(n + 1, MOD - 2) % MOD;
        return catalan[x] * val % MOD * factorial[x] % MOD * factorial[y] % MOD;
    }
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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 2x + 1 positions. In each position we can insert sequence of length li (Σ li = y), and there is catalan[li] such sequences.

        These considerations lead me to the easy dp to count number of ways to split y items into 2x + 1 groups, which could be computed in O(Y3logX) 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 ;)

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

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

  • »
    »
    4 years ago, # ^ |
    Rev. 10   Vote: I like it +15 Vote: I do not like it

    i did 6th in O(sqrt(N) * M * M + M * T) . Basic idea was dp(i, j) = number of ways to place J pairs of brackets in I slots . Answer is dp(2 * n + 1, m) * catalan[n] * factorial[n] * factorial[m]. This has complexity O(N * M * M). To optimize this i precalculate answer for all dp(N, m) where N = i * sqrt(n) for integer i and also dp(i, j) where 1 ≤ i ≤ sqrt(n) . With this precalculation takes O(sqrt(N) * M * M) time and each testcase takes O(M) time.

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

      This trick is pretty amazing. There are so many unique solutions for each of the harder tasks of this contest :D

»
4 years ago, # |
Rev. 5   Vote: I like it +30 Vote: I do not like it

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 of u and v that has  ≥ k distinct values in it's subtree. We can precompute number of distinct values for every subtree in the reachability tree in O(NlogN). Answering each query can then be done in O(logN) using binary jumping.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    editorial for all problem is live, please check.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I can try:

    • We should notice that if you have X [] pairs, then you have 2*X+1 positions where you can insert () pairs:

    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.

»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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.

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

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

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

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

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

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

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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)?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

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

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

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

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

»
4 years ago, # |
Rev. 2   Vote: I like it +73 Vote: I do not like it

Yes yes I am TooDifficuIt.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Interesting,

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

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

    I also got a message that I won the contest.

    Also in the April contest I got a wrong message.

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

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

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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

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

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