SecondThread's blog

Meta Hacker Cup Round 3
By SecondThread, history, 2 years ago, In English

Meta Hacker Cup Round 3

Good morning! Meta Hacker Cup Round 3 starts on Saturday, October 8th in under 48 hours! You're automatically registered for Round 3 if you placed in the top 500 of Round 2.

Important info:

  • You'll qualify for the Hacker Cup Finals if you place in the top 25 in this round.
  • If you place in the top 200 of this round, your Hacker Cup shirt will have a badge on the sleeve indicating you did so.
  • The round will be 3 hours long.

Less important advice:

  • Though we attempt to sort the problems in ascending order of difficulty and assign point values appropriately, we particularly encourage reading all the problems in this round.

A separate post about t-shirt distribution will be coming in the next few days. Good luck, have fun, and we'll see you on the scoreboard!

Days until contest: 4, 3, 2, 1, 0

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

»
2 years ago, # |
  Vote: I like it +41 Vote: I do not like it

SecondThread, could you please read your DMs? I have sent you one a few days ago regarding tax issue with last year's Hacker Cup T-Shirt, and it is still unread.

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

    Hi, sorry, I've been focused on preparing round 3 and dealing with t-shirts this week. I've read and replied to all of them. There's also a message cap on CF, so I had to go somewhat slowly responding as well.

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

Will Meta considering holding contests in future years a couple of hours earlier (around the time slot that Google Code Jam or Codeforces hold their rounds)? The Code Jam timing seems to allow West Coast US all the way till East Asia to take part. On the contrary, Meta Hacker Cup timing requires East Asia participants to take part at 1-4am.

I know some people say sleep is for the weak or coders know no sleep etc, but when you are in your thirties, 3am is a pain...

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

    +1. Majority (?) of contestants are in Asia timezones, so I can't understand why the contest time is like this. If you hold the contest for just 2 hours earlier (which will be 8am for Facebook engineers in California), thousands of contestants' live would be much better.

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

Will finals be an onsite contest?

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

I can't download the input to problem A.

I get:

Sorry, something went wrong. We're working on getting this fixed as soon as we can.

The validation worked fine though.

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

    Same here...

    And don't repeat my mistake — I clicked the next button hoping to download the plaintext file, it doesn't work either :(

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

5 problems, 3 rolling hash.

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

    Which 3? You can use it for Second Mistake and Zero Crossings, but what else?

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

      Can use it for third trie too (I did and AC)

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

      We don't actually need it, but I also used the hash in Third Trie.

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

        What was the approach? The runtime wasn't O(100^6 * 10^4) per testcase, was it? We had specific cases breaking that naive with C++ -O3 TLEs to make sure it worked.

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

          Can count the number of occurrence for each string over all tries and then add nC3- (n-count)C3 for each string (since each string will only occur once per trie)

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

            Oh I didn't even consider that. Yeah the intended is to combine the tries into a single trie and then just do a DFS on that. Hashing is just ridiculously strong when checking big things for equality.

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

      -

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

Missed E1 by 6 minutes :( needs more templates...

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

I feel like d1 was much easier than d2, but it was worth more points.

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

    I had a small bug in D1, but my D2 passed :( annoying that D2 is worth little

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

    It is assumed that if you solve D2, you solve D1 as well, so the points for D2 represent the extra difficulty of D2 compared to D1, not the total difficulty.

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

What's the solution for A? I bricked there so hard :/

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

    We look at the highest card to lowest, and determine which ones will win rounds. A card will win if there is no available higher card from the opposite team that plays later. So, you can do a greedy approach with the following code

            // person[i] is index of person that holds card i, available is an array that starts as all 0s.
        int rounds_left = r;
        for (int i = n - 1; rounds_left > 0 && i >= 0; i--) {
            if (available[person[i] + 1] > 0) { // next player can cover my card
                available[person[i] + 1]--;
                available[person[i]]++;
            } else if (available[person[i] + 3] > 0) { // only relevant for b2 covering a1
                available[person[i] + 3]--;
                available[person[i]]++;
            } else { // this card will win
                rounds_left--;
                win[person[i]]++;
                available[person[i]]++;
            }
        }
    → Reply
»
2 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Sudden death when I noticed I failed D1 when I was received WA at validation of D2

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

    I was smart and validated both D1 and D2 before submitting either.

    Spoiler
    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is E2 persistent treap?

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

I failed D because I wrote an N for M. :)

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

    Nice clutch making it to the finals with E2 though. We were worried when it looked like you were going to not qualify despite solving E1 because of WAs on D

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

When can we expect editorials to be up by? fun problems btw

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

I failed E1 because of an invalid sample test. It was actually updated on the site, but I noticed it too late (there was no announcement). As a result, I spend the last 10 minutes of the contest debugging a solution which was in fact correct. SecondThread Can you make an announcement when sample tests are updated? Some people download them once, not copy&paste it from the page each time.

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

This is the first time I do Meta Hacker Cup and it turned out that I was pretty lucky. Here is what I have experienced during the contest.

I never thought before that the local stack size might be an issue for CP but this happened after I downloaded the full input of problem B (since I used a dfs function). Fortunately, I managed to change my dfs function into a bfs function and submit the output & solution in the last two seconds. (Or maybe even the last one second?)

Besides, when I started coding D2, I realized that my code for D1 would output wrong answer when $$$k = 1$$$. Fortunately, I checked the full input data of D1 and found that there was no test case with $$$k = 1$$$, XD.

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

It seems that everybody got errors when submitting A. The organizers should have announced the issue instead of letting us waste time (before eventually using clarifications).

(It didn't affect my score. I'm just saying that an announcement would improve the contest.)

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

    Most people had no issues with A. We received fewer than 25 clars for A in total, which includes statement-related clars. It seems the slowness came in waves (either of high stress or of random maintenance on servers), we're not sure why yet.

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

      ok, them my suggestion is invalid

      I asked two friends and they also had issues with submitting. Too small of a sample, I guess.

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

Some feedback on the contest:

A: Great problem, interesting to think about and not too difficult to implement. On a personal level, it's a bit disappointing that validation didn't catch all the bugs (in my solution, when player three cannot cover any remaining card played by player two, they cover the highest possible card played by player one rather than the lowest; this passes validation tests), but obviously it's unreasonable to expect these tests to catch every little error, and my mistake was both sufficiently subtle and sufficiently silly/one-off (i.e., I doubt many other contestants wrote the same error) that I can't be too frustrated by the lack of pretests covering the case (i.e., I don't think this is evidence that the authors failed to prepare good validation tests).

B: Good problem; reasonably interesting solution and straightforward implementation. I think this was probably easier than A, but it's close.

C: Decent problem--ad-hocs involving hashing are always a bit more implementation-heavy than I'd like, but this one wasn't too bad and the idea was a nice special case of meet-in-the-middle.

D: I enjoyed this problem overall. D1 felt a bit standard as a use case of small-to-large merging, but it wasn't too painful to write. When I read D1, I suspected that D2 wouldn't be too much harder; I think I was right, but even so, the extra step to finish the problem was fairly interesting.

E: I wasn't a fan of this problem. It felt like three disjoint problems, each of which I've seen before (ICPC NAC 2020 C, some problem on Codeforces I can't remember involving hashing trees to check isomorphism of subtrees, and this problem from this year's NA ICPC regionals, concatenated on each other. As such, coming up with the solution was very easy (as little/no thought was required to reduce the problem to these tasks, and I remembered the solution to each subproblem immediately), but the task still took three problems worth of implementation/debugging time. I'm also not a huge fan of geometry in the Hacker Cup format because geometry problems tend to be rife with edge cases and MHC penalizes subtle implementation bugs far more heavily than ICPC or (to some degree) Codeforces, but obviously the bug I wrote in this particular case is my own skill issue more than anything else.

Overall, I enjoyed the contest--my one overall point of criticism is that the round felt a bit like speedforces (i.e., exactly four problems must be solved to make finals, there is a clear set of four easiest problems, and finals are decided largely by penalty time on these four problems, with the finalists solving them very quickly). One of the things I think GCJ usually does very well is making sure that there are always multiple paths to the finals. Last year's scoreboard is a great example of this--after picking off the "free points" (A and B small), there were a number of options for how to move forward (fast B large/C small, B/C full, or D full were all strategies that made the finals). This meant that mid-contest, observing the scoreboard and making guesses about FST rates could enable competitors to make better choices about which problem to attempt next. (For example, in the aforementioned GCJ round, I solved A slowly and then decided that because many others had accumulated more points already, my best chance to make finals was to fully solve D; this would have worked if I had a bit more time to finish the small subtask of B afterwards.)

As another example, last year's R3 made B, C, and D all sufficiently challenging that solving two out of three was enough for the finals, meaning that there was some strategy involved in problem selection (and in particular, guessing early on that two of these problems were necessary for the finals, while one could be safely skipped, could have led to better strategic decisions throughout the contest).

In this year's R3, the set of "must-solve" problems for finals was ABCD, without much opportunity for variation. I suppose that someone at ~52 points with around an hour left might be incentivized to attempt E instead of their last problem from A-D, but E was hard enough that this strategy was unlikely to work. If I were writing this contest and could choose problem difficulties arbitrarily, I'd replace two of ABCD with problems harder than D and easier than E (the hope being that contestants will need at least one of these problems, but not both, in order to make finals). More generally, I think future rounds should have fewer than four easy-medium problems and more medium-hard problems, so that finals are decided by more challenging problems and so that there are multiple sets of problems that can be solved in order to make finals.

Thanks for the contest! Hoping to write fewer one-line bugs next year :)

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

    By the way, did anyone get constant factor TLEs on C? My solution isn't optimized that well, but it took 2-3m to run on my (reasonably strong, i5-8400) PC, which makes me suspect that it may have TLE'd if run on a weaker PC.

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

      I did! Took me ~8 minutes to run on my laptop (submitted as practice after round ended and it was AC)

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

I passed C with naive iteration for each dictionary word over trie built over all query strings. Was this intended? Can anything be proven due to dictionary words being distinct?

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

    Intended was: build one trie that's the union of all tries. Then iterate over that mega-trie and do combinatorics on it.

    It turns out that it's actually very hard to get the solution for every query. We were able to disguise it well by hiding the fact that you return the sum of query answers in other problems too, thinking perhaps people wouldn't think too much about that approach at first. (The fact it was solved early gave that away a bit, which lead to it being easier to spot I think)

    Judges' solutions wouldn't be able to solve this problem if you needed to print the xor of answers for instance.

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

      I was talking about "Second Mistake". I indeed solved "Third Trie" with the mega-trie.

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

        That ought to TLE on perfect data. Just because the words are distinct doesn't mean they won't share a large prefix, forcing you to go down the same long path on the trie multiple times.

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

Interestingly enough, my solution for D1 does not generalize (at least by me) to the solution for D2 (in D1 I maintain the remaining number of connections that need to be made, while in D2 I maintain the GCD of the bars between different-colored stakes)

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

Wrote tons of hashes in the previous rounds, luckily don't have to write any more, got rank 26 in round 3 finally. (ＴДＴ)

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

Whoops, after some discussion, I realized I passed both D1 and D2 with a completely incorrect solution. In all my tests, it was enough to assume all cells of each color will be consecutive on a good board. So I only cared about the leftmost cell of each color and of all cells being consecutive.

D1 fails on something like:

6 4 2
4 3
5 1
6 1
2 1

123456 -> 123356 -> 123316 -> 123311 -> 113311
ah, eto... bleh
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The tests are weak in terms of catching slow solutions too. Merging "first to second" instead of "smaller to larger" takes less than 1s. That's $$$O(N^2)$$$.

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

I solve the problem C faster than all other contestants. Why the first blood list in the hacker cup homepage is Yuhao Du (apiad), but not me. :(

My rank is 264th. Please SecondThread check it.

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

    Sorry about that, and thanks for the correction! We've updated the summary.

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

Will solutions to the problems be presented as they have been for previous rounds? In C my solution (which sounds broadly like what people mentioned in the blog — hashing meet-in-the-middle sort of thing) ran ~8 minutes on the large input. So I am interested whether I just have a bad constant or there is something more that I missed :)

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

    Did you compile your program with at least -O2?

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

      yes. I did use meh hardware and didn't take much care of the constant (didn't realize I'd run into problems with it, which is my fault anyway), it would still be a bit disappointing if I would've passed simply by working from my desktop instead of my laptop

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

I failed miserably, but it was fun anyway.

Waiting for the editorial, as I still need to learn how to correct my D1 "solution" :)

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

I still can't download A's full input(status code 500). If it's just me, could anyone help me out and upload it somewhere? Every other problem's fine.

Also no K=1 tests in D1 -- kinda evil.

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

Since there is apparently no editorial, I can write my solutions (briefly) so that nobody needs to wait.

A: Fourth player
B: Third something
C: Second mistake
D1: First something
D2: First something
E: Zero crossings
→ Reply
»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

no post regarding the t-shirt. it has been now a week SecondThread

→ Reply