SecondThread's blog

Meta Hacker Cup 2023 Practice Round
By SecondThread, history, 15 months ago, In English

Meta Hacker Cup Practice Round

Good morning! The Meta Hacker Cup Practice Round starts in under 24 hours!

If you haven't yet, now's a great time to register for the round here. This round will be 72 hours long, starting tomorrow, September 21st at 10AM Pacific. Though it's optional, we strongly recommend participating. If you've never competed before, you'll see that Hacker Cup has a slightly unconventional submission system (you run your own code locally, and upload the output), so it's good to practice that. Be sure you have a sufficiently large stack size, for example, if you plan to use recursion in any of your solutions, and that you're familiar with compiling your code if you don't usually do that in other contests.

A couple other reminders before the contest starts:

If you're using an IDE, you may need to paste in larger inputs than you're used to. I recommend you do at least one of the following:

  1. Make sure your IDE is capable of allowing you to paste in huge (up to like ~70mb) inputs, or better yet
  2. Write your code to read from a file rather than stdin, or
  3. Redirect stdin to a file when executing your code.

You can also view some of our FAQs here. Good luck, have fun, and see you on the scoreboard!

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

Comments Comments (75)
| Write comment?
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Would the questions in Round 1 be of more or less the same difficulty as the practice round, or would it be much harder?

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

    About the same, but maybe with barely stronger validation data now that people have learned their lesson :)

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

      Thanks

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

      None of the easier problems cover any issue with stack sizes, which I think should be the primary concern for new comers.

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

        The tricky part about stack size issues is that recursion is hard to force on people without mandatory DFS's. DPs can be solved iteratively. Many graph theory problems and tree problems can be solved with BFSes. To force people to get caught by stack size, we do have to make the problem a bit harder. We also wanted to keep it original, which is why D may have been even harder than that too.

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

do we have to remove line from codes like this before submitting the source code

this
→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No, if we need to run your code, we'll look at how it works and make reasonable allowances or adjustments. The only requirement is that you submitted the code you used to generate your answer (and that you're not submitting something like a compiled executable or intentionally obfuscated source code to avoid cheating detection). If it requires some set up or for files to be named a particular thing, that's okay.

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      I'm curious--in what situations do you run code submitted by contestants?

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        In last year's Hackercup the submit system failed for me. When I tried to upload the output file I got some weird error message telling me that the upload had failed. In the end, what I did was that I sent just my Python code in a message to the judges, and then they ran my code on their system and gave me AC.

        → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i think it would be better if there is no time limit for submitting, for one of the questions in practice round as we are giving this contest after a long time, we can clearly explore and have a good idea on submitting the output and code.

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

    After the contest ends, you'll be able to resubmit and test things on your own without a timer, in the same way you currently can for previous contests. We wanted to make sure the practice round had the exact same format as future rounds will in a few weeks.

    → Reply
»
15 months ago, # |
  Vote: I like it +99 Vote: I do not like it

I made a video for the newcomers where I show how to read input and what the small-stack-segfault looks like, how to fix it on my machine and where to read about fixing it on other os

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Thanks.

    It is also possible to crash your system due to infinite loop for instance. Is there any workaround? Docker?

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Afaik you cannot crash your system just with infinite loop. It happens when you allocate more and more memory with each iteration of this loop, for example, by pushing something to a vector.

      Basically any memory limitation would probably solve this problem, maybe docker is a reasonable solution, I didn't try it. Usually, when I have a suspicion that my program may have entered an infinite loop, I first rerun it with debug output to see the progress (basically print "test #i is done" to stderr). If my program takes too much time to run on one particular test, I move my mouse to see if the cursor is moving smoothly. Once it starts lagging, I cancel the execution as fast as I can. If I miss the moment, my PC freezes and I have to reboot it

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

        As others have pointed out, having non-unlimited stack is a good enough solution.

        ulimit -s 268435456
        → Reply
        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          This helps when your program crashes due to a small stack size, not the system. I mentioned ulimit -s unlimited in my video. When you asked about "crash your system due to infinite loop", I thought more about turning your PC into a brick rather than seeing your program terminate incorrectly, which is a completely different matter and which is not fixed by increasing your stack size

          → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How many test cases are there for each problem? I want to setup something in case there's multiple test cases.

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

    Each problem includes a set of validation tests (used to check your solution before you submit) and a full test file (used for grading). The full tests usually (not necessarily always) include the maximum number of tests allowed by the constraints of the problem, but they are always contained in a single file.

    → Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

is the solution validation really working or am I misunderstanding how it should work?

Case #1:3
Case #2:1
Case #3:0
Case #4:199
Case #5:100
Case #6:1999999999999
Case #7:3
Case #8:1728395059
Case #9:1999999999999
Case #10:1000000000000
Case #11:1
Case #12:1

note the missing space, but it seems the validator just did not catch this and allowed me to submit my solution after anyway. Is this intended?

I do see

We're unable to verify whether your selected file is a valid text file. You may still submit it, but please double-check that you've uploaded the correct file. If so, what's the point of the validation?

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

    I think we are supposed to use .txt format ("out.txt" and not just "out").

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

      sure, I realised that, but changing to txt only avoid the error that, and still doesn't catch the validation. unless the output above is an acceptable output?

      → Reply
»
15 months ago, # |
  Vote: I like it -18 Vote: I do not like it

I don't know if this has been discussed but I think the Meta format makes the penalty on errors like RTE too harsh.

Usually, for RTE, you get some points deducted or some minutes added to your penalty. But in this format, it's "fix this in 5 minutes or you are out". (╯‵□′)╯︵┻━┻

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Not sure why this is unique to RTE? The same reasoning applies to every other type of error.

    (If you're concerned that validation tests won't catch bugs in your solution, you have the option to write a stress tester if you're worried about WA or to generate and run your code on a large test case if you're worried about TLE/RTE on large inputs.)

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      You worry about WA and TLE before testing, but not about RTE — and that's unique about it.

      You don't have a way to know if your program has a WA in the actual input. And you can guess the time complexity of your program, which avoids TLE. So you don't really worry about these after the validation tests pass.

      Nonetheless, I know you should stress-test your code before trying to run the actual input. I was just saying that I think the penalty being restricting you to submit is a bit unconventional.

      → Reply
»
15 months ago, # |
  Vote: I like it +18 Vote: I do not like it

very nice problem, thank you for keeping hacker cup alive

→ Reply
»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Seems like the zip file is not compressing the input at all. Is this intentional?

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 8   Vote: I like it -25 Vote: I do not like it

    [Deleted]

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    The point isn't to compress the input, but to let you download the input (potentially on a slow network connection) before the timer starts.

    → Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

[Deleted]

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

    because FB does not want to spend time building a testing system that is crash proof.

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

Several times I've attempted to participate in Hacker Cup and was unable to log into my otherwise unused FB account. Not because I lost access to it, but because I was asked to verify my identity or something and that didn't work.

Last year I somehow managed to create a new FB account and register for HC. Now FB wants to verify my identity again, but says "We currently can't verify your identity. Please try again later." before prompting me to supply any information. Creating a new account doesn't help either. This is really frustrating. Is there anything you can do, as a Meta employee promoting Hacker Cup?

→ Reply
»
15 months ago, # |
  Vote: I like it +55 Vote: I do not like it

For anyone struggling with problem A, here's a helpful visualization I found today.

(You'll have to imagine the missing buns)

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    5 years ago, my math teacher told me that he had actually eaten this before O_O.

    → Reply
»
15 months ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

I've just written a Python script to automate some tedious and repeated steps when running both validation and main tests.

Run ./script --help for help.

Do the following to run the validation test:

  1. Download the input file to your downloads directory (usually ~/Downloads, you can change it)
  2. Run the script ./script
  3. Submit the output file

Removed step:

  • No need to redirect input and output
  • No need to choose the problem directory, just one fixed place for downloads

Do the following to run the main test:

  1. Download the input 7z archive to your downloads directory
  2. Copy the password
  3. Run the script ./script --main
  4. Submit the output file (in the directory where you run the script)

Removed steps

  • No need to redirect input and output
  • No need to extract the archive
  • No need to choose the problem directory, just one fixed place for downloads

Make some adjustments to match your own way of coding and structuring the files.

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

What is the FST case on A2? (edit: i found it, if you have enough to have another single burger but not a double burger)

I didn't know about 2-edge-connected components in D, so I found them by finding 2-vertex-connected components, ignoring size 2 components, and union-finding all components belonging to the same vertex. Can it be proven that this will yield 2-edge-connected components?

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

The pretests seemed kind of weak. Was this intentional? Regardless, the problems were very nice.

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

    Yeah, there were some cases we intentionally removed from validation data so that people were aware that it was possible/likely to fail full data. We didn't expect so many people to fail though. A2 had a 24% AC rate among contestants who submitted. I expected 80%.

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

      Are you going to have stonger pretests in the actual contests?

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

        +1. As is probably well-known by now, I'd prefer stronger validation tests, but in any case it would be good to know in advance whether we should expect certain edge cases to intentionally be omitted from validation so that we know whether e.g. it's worth stress testing before submitting in Round 1. (It seemed like in previous years validation tests usually tried to catch all the obvious errors, which is why I was surprised that they were so weak in this contest.)

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

          The only good answer that comes to my mind is "never trust the validation tests". I hope SecondThread doesn't mind if I share a small insight. We were aware of missing edge cases in A2 validation and we gave a hint by assigning a lot of points to A2. But at the same time I thought that validation test in C is too generous and checks more than it should. All of a sudden C also has very low success rate.

          However I am sure that the success rate for both problems would have been higher if it was a non-practice round, where contestants test their solutions more thoroughly.

          → Reply
          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
              Vote: I like it +17 Vote: I do not like it

            I don't think there would have been much difference in a non-practice round. Most people expect the validation tests to be strong enough.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              15 months ago, # ^ |
                Vote: I like it +11 Vote: I do not like it

              My point was exactly about it: "Please don't expect things like these". Even without being planned, validation tests may miss tests that contain a certain type of bugs which no one expected during problems preparation process.

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

              +1, this seems like a substantial change from past seasons and because I assumed validation tests were meant to be strong based on my past experience, I would have behaved exactly the same way if this round was official (though I might not now that I know y'all are intentionally withholding cases from validation...).

              I also never would have interpreted a problem having a high score as a hint that validation tests are weak, especially because A2 was obviously harder than B and arguably harder than C even ignoring the strength of the data.

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

                Ok, I revoke my assumption about contestants changing their behavior based on the round type. Eventually, all of us found some wrong assumptions they've made.

                → Reply
          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
            ← Rev. 2   Vote: I like it -10 Vote: I do not like it

            I understand your point of view and I would find it valid for a round that lasts 72 hours or 24 hours like the old format of the first round, but for rounds that last only 3 hours I think dealing with solving the problems is enough for that time frame (for most of the participants, I am not talking about IGMs and higher) and you should not have to worry about weak validation tests as testing takes a lot of the time from that assigned to solve problems (as you need to write a strong generator, a brute solution and maybe other stuff). I see the point of testing in general software development but I think that for competitive programming contests that last 2-3 hours like codeforces or hacker cup it should not worry as much as it worried at this practice round and validation data should at least include those edge cases.

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

              Yeah, agreed. Because of my FST now I'm going into round 1 worried that I'll FST enough points to lose my qualification to round 2.

              I'd like to propose an alternative format. I understand the difficulties in building a fully functional testing system, but it is still possible to allow people to submit multiple times. My national OI uses the following format in its first round: you can download the full input and submit within 5mins. If you pass then you get the points, but if you don't, you can download another input and submit within 5mins. Maybe input generation is a bit of a concern but ig because the contest lasts 3h, no more than 36 submissions can be made per task so one can just generate 36 inputs before the contest begins and give them to contestants in a certain order. So it's full-feedback without the need to build a testing system.

              → Reply
        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it +33 Vote: I do not like it

          There's no hidden information though in this format. You can just look at the validation testdata and check if it is strong or not. If you see the validation data contains no max case, better write a max case yourself. If it seems to be really few tests that check on small cases for correctness, make a bruteforce and random test generator yourself. Although in the practice round I just yolo submitted everything, with blind trust on the validation, testing is pretty easy.

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

      My solution failed due to binary searching up to ~1e16. I think the answer could be up to ~2e16. Nice problems!

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

      Can we get some of the edge cases, sir?

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

        For me the problem was long long overflow. So I don't really think it was "edge cases" but rather not accounting for the fact that 1e16*1e16 can be larger than long long.

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

        The other easy to miss case depending on how you attempted to implement it was that you might actually need to buy two singles, which is a bit unintuitive at first. Further explanation is in the problem solution.

        → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      Controversial opinion: A2 is a type of problem where the pretest should intentionally be weak.

      Having a strong pretest just encourages people to submit their code without proving their correctness. There will be some people who just add more checks when their code failed the pretest without knowing/proving whether those additional checks are actually necessary and/or sufficient.

      Of course, some people will argue that programming contest is about intuition and not about rigorous proof.

      → Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

you could as well remove inputs if the test cases are going to be this weak.

→ Reply
»
15 months ago, # |
← Rev. 6   Vote: I like it +17 Vote: I do not like it

My suggestion is to make stronger pretest or validation test cases in the future round. They do no need to be in the examples, but act as "pretest 2" in the codeforces. So many people failed problem A2 and C, which will make them very upset.

Nearly all of the contests is full-feedback, which means people adjust there answer according to the feedback. However, hacker cup is a nearly one-shot round, the validation test can only block a few fraction of all the false code that pass the example.

My initial python code passed all validation test for all the problems, then for C and D, I realized I make a mistake when I was trying to get the password, and withdrew the submitting procedure to modify my code. For problem A2, I get wrong answer in the end. Then I surprisingly find by rank raise from 77 to 62 despite my failure of A2, which means a lot people get more wrong answer than me.

Another suggestion is to include at least one full size example in the validation test, to let people to be aware that their laptop may crush when running large test case.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contest and problems. I like a few things that are kind of unique in Hacker Cup:

  1. I like the relaxed 72/24 hours time limit of the qualification round and original round 1. It allows me to solve all the problems thoroughly without tight time constraint, which is usually the case of problem solving in real projects. One example is problem D, I was able to solve it after thinking about it on and off for 2 days, after two in-correct/slow versions. I really enjoy the journey.
  2. Thorough testing is necessary and feasible given the relaxed time constraints, which again mimics real software development.
  3. Submitting results requires people to avoid deep recursion code that may lead to stack overflow in local run, which is a good practice to encourage.
→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I somehow messed up my executable file which led to me submitting the correct source code but incorrect output for A2. I would have never thought of this dumb mistake but at least it happened to me in the practice round.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for A1 problem, I got wrong answer don't know why.

but now when I submitted the same code again it gives me AC. I have taken input from file and I named correctly file name it code as well.

why this happened? please explain SecondThread

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

    Have you downloaded the result you submitted during the contest and verified the results are expected?

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

      yes. for same input my contest submission result shows "NO" when practice submission shows "YES" :3

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

        If the expected answer is YES but your contest submission was NO, then it is wrong answer. If you wonder why it was NO in the contest submission, check the submitted source code as well, to tell whether you have modified the code afterward to get the expected YES answer now.

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

Me Thinking I have secured easy 60 points then getting a big shock after result reveal ; with due respect I must say that validation tests were very weak

→ Reply
»
15 months ago, # |
  Vote: I like it +28 Vote: I do not like it

"Road to Nutella" was a lovely problem — absolutely loved solving it!

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

    Yeah, I would second that.

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    the funny thing is everyone red and above said the problem wasn't good while yellow and below thought it was...

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +43 Vote: I do not like it

      I really liked nutella. However, I FSTed so I no longer like nutella. I'm somewhat annoyed, because I fail over 3/4 of the sys-tests, so I don't know how I passed validation, but if weak pretests are clearly communicated, I don't have a huge issue with them.

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

        The sys-tests were also not very strong — my solution has a major bug but it passed

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

      Really? It was like the hardest problem I solved during a contest — took 2/3 hours coding it...

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Yes, I asked a few reds and pinks and they said things like the idea is "obvious", "standard", "3 concepts thrown together" and implementation is annoying. I thought the idea was a bit nice at least...

        → Reply
»
15 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Thank you to authors and organizers for the nice round with final plot twist. All very interesting problems, and D that took me a whole night was great, really satisfactory. "Never trust the validation tests (especially if the score looks too high)" is the take out for next rounds ;)

→ Reply
»
15 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I like that the title of problem D is a nod to SecondThread's ongoing video series on his youtube channel by similar title, "Road to LGM".

→ Reply