Meta Hacker Cup Round 2 Editorial
source link: http://codeforces.com/blog/entry/107275
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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: WorkLife 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, #  Can anyone explain how to handle the equal weights in problem C, the Balance Scale? I couldn't grasp the editorial clearly. Thanks in advance. 

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.

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

2 hours ago, #  More people than I expected apparently disliked A1/A2. If you're one of them, what didn't you like about it? 

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

I don't see how this is an issue specific to this problemeveryone 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.

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.


But there's no recursion in the solution for A... Are you sure you didn't just have UB?


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.

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


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.

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.
84 minutes ago, #  Editorial of B sais, that it's too long to solve it as general "find K longest paths in DAG" problem, but it isn't. We can construct a graph with N vertices and 2N edges, not N^2 edges. We don't need to add an edge to all possible buyers. Only to the smallest cost. But to compensate for it, we need to add an additional edge "resell immediately to next cost buyer". Solution Code is kinda messy and definitely not easier than the intended solution. 
59 minutes ago, #  Also, the editorial of D2 seems to solve the subtask of type "find the smallest index in a nondecreasing Fenwick tree so that the th prefix sum is at least " in , while it is possible to do so in , restoring the answer bit by bit 
47 minutes ago, #  For A2 I used the classic 1e9 + 7 as big prime for hashing and got FST for 1 test case... 
40 minutes ago, #  saddest person on earth right now Spoiler 
33 minutes ago, #  any good cf blogs to understand stuff going with problem A2.? 
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK