Meta Hacker Cup Round 2 Editorial

Good morning!

As usual, written editorials are available in the solution section of all problems on the Hacker Cup site. Feel free to give problem feedback and discuss solutions here.

A1/A2: Perfectly Balanced

B: Balance Sheet

C: Balance Scale

D1/D2: Work-Life Balance

• Problem Statement, with written editorial
• Solution video coming soon.

Feel free to leave your thoughts on the problems below. I hope you found the round, and the scoring distribution, almost perfectly balanced. :)

• 2 hours ago, # ^ | ← Rev. 2 →   +7 Anything with an equal weight to the chocolate chips has the same chance as being left as the chocolate chips. So if you have 3 chocolate chips, and 7 raisins of equal weight, just pretend you have 10 chocolate chips, and then multiply your answer by 30% at the end.

  • 2 hours ago, # ^ | "Note that it's irrelevant how ties are broken by choosing the left cookie, because for any random subset lined up in a random order to be placed on the scale, it's equally likely for any two cookies of the same weight to be placed on either side" How are raisins and chocolate chips of the same weight to be equally likely?

    • 117 minutes ago, # ^ | ← Rev. 2 →   0 Symmetry. Raisins and chocolate chips of same weight are basically identical, so we can just divide up the probability equally among them.

• 2 hours ago, # ^ | As for me, I wrote AC solution, but because of my small stack size, I got RE on the second validating test, so after 7 minutes I had no chance to send it. In fact this task is pretty nice, but the system... After the contest I asked my friend to send it using his laptop and he got AC....

  • 98 minutes ago, # ^ | I don't see how this is an issue specific to this problem--everyone has had two rounds to set up their system to run code with a sufficiently large stack size; at this point, competitors who haven't done so are willingly making the choice to MLE any problem with a sufficiently large input.

    • 57 minutes ago, # ^ | During that two rounds every submission got accepted, so I have no problems with stack size. But in this particular problem I had some problems. I mean the task was great, but I didn't like the system. Anyway it is my fault. I can't get the point why the authors created such a weird system. There is a really nice system that is used on Codeforces, so you do not need any local resources to successfully submit your code.

  • 81 minute(s) ago, # ^ | But there's no recursion in the solution for A... Are you sure you didn't just have UB?

    • 56 minutes ago, # ^ | I have segment tree that uses recursion. And as I say earlier, my friend submitted the same code and got accepted

      • 50 minutes ago, # ^ | So about log n depth... so your stack is smaller than 10 kb? I don't think so. Default stack is 10 mb. 99% chance you have UB.

• 113 minutes ago, # ^ | idea obvious, just implementation heavy.

• 108 minutes ago, # ^ | The strongest reason I have for disliking the problem is that ideologically, I feel that it is not appropriate to propose problems where the intended solution is not deterministically guaranteed to solve the problem when you only have one submission available to you. In Code Jam, usually these problems are set as Visible data sets so you can take a relatively informed risk in implementing something simpler with a lower probability of success, versus taking more time to implement something more complicated that has a higher probability of success. However, here, you have no recourse if you got unlucky but had the spirit of the intended solution.

  • 96 minutes ago, # ^ | So you don't like any probabilistic problems at all? Even ones like this where you can write solutions where you are more likely to get hit by an asteroid during the contest than get it incorrect by being "unlucky"?

    • 88 minutes ago, # ^ | I think my comment makes it clear that my position exists in the context of the one-submission contest format.

      • 77 minutes ago, # ^ | But the same thing happens anywhere with system tests too

• 97 minutes ago, # ^ | In A1 I disliked the special case where Li == Ri (the substring length is 1). Nothing is left after removing this single letter and both first/second halves are empty strings. Is the resulting empty string a palindrome? Searching on the Internet reveals that some people think that it is (because reversing an empty string results in an empty string), but the others think that it isn't (because an empty string is not considered to be a word). Fortunately the A2 problem statement mentioned that [1] is an example of an almost perfectly balanced array and this resolved the ambiguity for me. Still a bit of time was wasted wondering whether I need to ask for a clarification or not.

• 86 minutes ago, # ^ | I wouldn't say I disliked it personally but I didn't find it very interesting. To me it feels like just a knowledge check (do you know how to hash a multiset) followed by trying to implement it cleanly, which can be fun for some people but I personally don't find that super exciting.

• 67 minutes ago, # ^ | I was going to leave a similar comment. Here is my explanation: Spoiler However, I think that this solution is easier than the one from the editorial, if one is familiar with the "find K longest in a DAG" idea