Yury_Bandarchuk's blog

101 Hack 41
By Yury_Bandarchuk, history, 8 years ago, In English

Hello CodeForces Community,

I would like to invite you to participate in 101 Hack 41 will be held on Tuesday, 20 of September. The problems were set by me (Yury Bandarchuk) and josdas (Stanislav Naumov), tested by wanbo.

101 Hack is back with its 41st edition! Passionate programmers will enjoy solving algorithmic challenges. It's all about speed, accuracy and efficiency: 5 challenges in 120 minutes. Every second counts!

Top 10 winners on the leaderboard will receive a HackerRank T-Shirt.

Hope, you will participate and enjoy the problems.

Good luck && have fun!

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

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

I guess/hope one or two programmers will get full score. :) The last two problems is a little harder compared to the previous contests. Hope everyone enjoys the contest.

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

Can you explain 4th problem not like in an editorial? I can't understand how the editorial connected to the given problem.

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

Once again I find myself disagreeing with Hackerrank's philosophy in problemsetting. In Washing Plates, why do we have to print 0 if the income is negative? It adds nothing to the difficulty of the problem, you just put in one if. If you forget about it and then find out what's wrong, you don't think "ahh, I forgot about this edge case, of course, that makes sense", but rather "why is this this sentence in the statement?" I get it, it's a paycheck, so it shouldn't be negative. But the story shouldn't be more important than the algorithm. The same goes for k>n, another pointless "haha, got you" condition. Both of these are akin to allowing cases like n=0, which we almost never see on Codeforces, for example.

The 4th problem was interesting, but WTF is that editorial? Where is the proof or logic?

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

    Let's look at the vertices, which causes maximum damage. Adoption: we remove the vertex immediately after the remove of her father. If we know two unequivocal order of vertices, then try to get them to merge and reduce the number of vertices to 1. We can do this because we know that we will remove these vertices in that order. Another statement, if we started to remove some component with dependencies, then we will remove it all, without having to switch to other components.

    Now we calculate how much damage we obtain from the removal of the components size bed and the total damage sum. size * sum for this size moves. We compare the two components and understand in what order better to remove them.

    In the first case size1 * sum1 + (size1 + size2) * sum2. Second size2 * sum2 + (size1 + size2) * sum1. Let's compare them. We find that quite compare: sum / size.

    Now, we will support the entire structure in the set, for a maximum. And dsu for mergers

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

      I still don't completely understand your explanation.

      I got 45/80 by running a dfs, storing the optimal sequence of removals at each node, and using DP to merge the sequences of its children. Is this what you mean by "If we know two unequivocal order of vertices, then try to get them to merge and reduce the number of vertices to 1"? How do you do the merge step faster?

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

    @-Wave-, I agree with you, next time, I will try to discard the tedious part which is not highly related to the algorithm. Because I got AC the first time very easily, so I haven't noticed that there is any problem.

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

Can you please explain editorial of Tree Color in more detail.

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

Can someone please explain how to solve the 3rd problem, Aria's Loops? I did not understand the editorial.

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

    Let's transform the given problem to the next one:

    for i1 = 1 .. n
  for i2 = i1 .. n
    ....
     for ik = i(k - 1) .. n

    This problem can be solved with k-combination with repetitions
    (I strongly belive, you can understand why this is the answer).

    In order to transform initial problem to the problem above,
    you have to extract from initial N the values from 1 to k - 1 which is .

    Now, you can get the formula from editorial.

    I read the editorial after the contest and i bounded the logic chain today in the morning.

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

    There is an easy way to understand the formula.

    We'll map each sequence (i1, i2, ..., ik) with a new sequence (a1, a2, ..., ak, ak + 1, such that a1 = i1, a2 = i2 - i1, a3 = i3 - i2 - 1, ..., ak = ik - ik - 1 - (k - 2), ak + 1 = n - (i1 + i2 + ... + ik) + 1. Now, and note that ai are positive integers. Conversely, every positive integer solution to this equation is equivalent to a sequence (i1, i2, ..., ik) that can be attained in the code. So, we just need to count the number of new sequences, which is easy, since by balls in urns formula this is just . This gives the formula.

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

      I think ak + 1 should be given by:

      ak + 1 = n - ik + 1
      → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

For the 3rd problem, Aria's Loop someone may find this useful

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

I know the post is really old, but I have to ask one more time: How to solve 4th problem? It is very interesting and I've struggled for a couple of months to solve it and no results are to be seen. I'd be grateful if someone could provide me with a complete explanation.

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

    I found another blog regarding this problem .

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

    The problem seems to be the same as this problem (just stated in a different manner).

    This should help you solve the problem.

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

    Thanks both of you. I will read the explanations you gave, but I'm optimist that I will understand at least one of them as they seem to be written very well.

    → Reply