Meta Hacker Cup Round 3

Unfortunately, it clashes with the ICPC regional. Couldn't get a top-200 badge this time :(

lol my facebook account got banned

Can anyone register https://www.facebook.com/profile.php?id=61551793797917 please? my account was banned (i did not use it...)?

Pretty please send out some kind of announcement about the starting time next time, I (and some other people) got screwed due to daylight saving time changes :/

Thanks for the contest! Some thoughts (written before the end of the round):

Overall, while I think most of the problems were reasonably nice in isolation, the round as a whole was far too easy to meaningfully distinguish the top 25 competitors from the rest of the pack. We're about 2h10m into the contest and already the cutoff for top 25 is 100 points, with relatively minute differences in time penalty distinguishing the potential finalists. This means that the finalists will be distinguished either by FSTs, which feels unsatisfying (and not especially correlated with problem-solving ability), or by relatively minute differences in time penalty. I think this is a much worse scenario than e.g. MHC 2021 R3, where finalists were determined by the ability to solve at least two out of the three harder problems in the round.

Problem-specific feedback:

A: Pretty good problem. As a matter of personal preference I don't love problems where the time complexity can't be evaluated nicely by hand, but in this case it's easy enough to intuit that the solution will run fast enough.

B: Good problem; not ridiculously challenging, but appropriate enough for its position. It took a bit of thought to reduce from O(N^3) to O(N^2), and the process of doing so was reasonably nice.

C: The idea behind this problem was nice, but the implementation was very unpleasant (obviously, this might be my fault for not implementing in the cleanest possible way). Even after spending a fair amount of time thinking about how to implement in the least edge case-heavy way, my code ended up running nearly 200 lines (again, possibly a skill issue), not counting my template. Heavy implementation is especially frustrating in an R3 where the finalists will largely be determined by penalty time. Because of the difficulty of implementation, I thought this was by far the hardest problem of the round.

D: Fairly standard rerooting problem. Not too bad and easy to dispatch if you've seen the idea before, but nothing particularly exciting either.

E: This problem is pretty neat in isolation, and would be a great problem in a hypothetical contest in which formal proofs must be submitted with your code. Having said that, I think it's highly ill-suited for position E on Round 3. This is partly a matter of taste--the problem feels too straightforward in a sense to be the last problem identifying the finalists--but also because in a round where the key to advancing is maintaining a good penalty time and where using validation tests is costless, contestants are encouraged even more strongly than usual to attempt proof by AC, and those who spent the least time attempting to prove the solution before implementing, running validation tests, and downloading the full input were rewarded with shorter penalty times.

Is problem B similar to 1870E - Another MEX Problem?
I messed up during copy-pasting soln from this codeforces problem.

I’ve never felt this dumb, helpless, hopeful, sad, nervous, happy and confused within a 3hr span before :)

Wow, Japan did phenomenally, especially considering that it's currently 5 AM there. It looks like 7 of the top 25 finalists will be from Japan this year.

Thank you for the contests :)

I found the problems of round 2 and 3 cool!

Unfortunate that I got systest on A and missed top 200 by a few places because of that :x

Hopefully, see you next year with an online judge and feedback after submissions

Also one fun fact about the problem E. I participated in the contest [Codeforces Round 897 (Div. 2)] virtually, and during the contest, I understood the problem https://codeforces.com/contest/1867/problem/F as today's E (and solved it), then I got that I read problem incorrectly :) and today I have already solved the correct problem :)

In B, I can't believe there weren't any case in pretests (validation input or whatever) where hash 0 comes only from 0 orders. I even contemplated it once while writing, but thought I read it had to be positive number of orders and indeed passed pretests. Such a needless constraint. Glad to get the top-200 badge, but ending the night on a sour note.

Missed Top-200 T-shirt because I thought that with auto it = s.rbegin(), we need to use it-- instead of it++ to iterate in the set. Anyways, learnt some more unknown secrets of C++.

I might have the dumbest reason to miss 200-tshirt.

In a codeforces round I changed

typedef long long ll;

To

typedef int ll;

Since I used ll everywhere but I needed to speedup my program, and didn't wanna replace.

And today I accidentally used this bad typedef instead of the good one, and my D overflowed on 1 test :(.

I think the common solution to D assumes $$$C = \sum_{(u, v) \in E} \min(deg(u), deg(v))$$$ are small and uses that much computation. Apparently, this is not assumed by the editorial, which relies on an extra property that can make implementation a little more boring.

Actually, it's quite well-known that for all graphs with $$$|E| = |V| = O(n)$$$, $$$C = O(n^{1.5})$$$ (Cf. IOI 2009 Regions). I was pretty much sure $$$C = O(n)$$$, but I didn't find an immediate proof and I also thought $$$n^{1.5}$$$ would be fast enough anyway.

Now I see that $$$C = O(n)$$$. Root the tree arbitrarily. WLOG assume $$$u$$$ is the parent of $$$v$$$: $$$C = \sum_{(u, v) \in E} \min(deg(u), deg(v)) \le \sum_{(u, v) \in E} deg(v)$$$. But each $$$v$$$ occurs at most once, so this is just at most $$$2n-2$$$.

This same reasoning works for planar graphs and basically any graph with bounded degeneracy.

Could someone help me debug my code for problem C? It fails on only one test out of the 118 tests in the full input, and I can't find the bug for the life of me.

I don't know if it has something to do with how Meta generates test data, but my code for D which has an extremely obvious bug managed to slip through and got AC

    for(int i = 2; i <= n; i++) {
        int x; cin >> x;
        conn[x].push_back(i);
    }

I only pushed one edge into the tree when the question stated the tree is undirected. Initially did this due to most Codeforces problems with similar input formats also guarantee $$$P_i < i$$$, but not for Hackercup. Eventually managed to realise this when testing samples and changed other parts of my code but somehow forgot the input processing part, somehow still passed.

Edit: As some replies have pointed out, the fact that $$$P_i < i$$$ is irrelevant, which definitely explains the whole situation. But still funny how this feels so wrong to do while being completely correct

I wanted to say that I really liked the problems. Based on several previous years I was expecting a contest full of data structure bashing, but the problems were interesting, particularly C and E.

The difficulty was too low, and I feel like it is connected: if you don't have top-tier problemsetters it is easier to achieve high difficulty by asking for harder data structures and overall just a lot of code. But I appreciate the attempt at making more interesting problems.