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:
- We ask that you don't discuss the statements or solutions (ideas or code) until after the practice round ends.
- If you choose to use an online compiler (such as IDEOne, or something else), it is your responsibility to make sure your code stays private. If your code becomes public, even by accident, you'll be DQ'd.
- If you're using Windows, don't use notepad because it sometimes may unexpectedly attempt to read some files as random Unicode characters.
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:
- Make sure your IDE is capable of allowing you to paste in huge (up to like ~70mb) inputs, or better yet
- Write your code to read from a file rather than stdin, or
- 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!
Would the questions in Round 1 be of more or less the same difficulty as the practice round, or would it be much harder?
About the same, but maybe with barely stronger validation data now that people have learned their lesson :)
Thanks
None of the easier problems cover any issue with stack sizes, which I think should be the primary concern for new comers.
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.
do we have to remove line from codes like this before submitting the source code
#ifndef ONLINE_JUDGE freopen("error.txt", "w", stderr); #endifNo, 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.
I'm curious--in what situations do you run code submitted by contestants?
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.
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.
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.
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
Thanks.
It is also possible to crash your system due to infinite loop for instance. Is there any workaround? Docker?
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
As others have pointed out, having non-unlimited stack is a good enough solution.
This helps when your program crashes due to a small stack size, not the system. I mentioned
ulimit -s unlimitedin 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 sizeHow many test cases are there for each problem? I want to setup something in case there's multiple test cases.
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.
is the solution validation really working or am I misunderstanding how it should work?
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?I think we are supposed to use .txt format ("out.txt" and not just "out").
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?
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". (╯‵□′)╯︵┻━┻
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.)
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.
very nice problem, thank you for keeping hacker cup alive
Seems like the zip file is not compressing the input at all. Is this intentional?
[Deleted]
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.
[Deleted]
because FB does not want to spend time building a testing system that is crash proof.
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?
For anyone struggling with problem A, here's a helpful visualization I found today.
(You'll have to imagine the missing buns)
5 years ago, my math teacher told me that he had actually eaten this before O_O.
I've just written a Python script to automate some tedious and repeated steps when running both validation and main tests.
Run
./script --helpfor help.Do the following to run the validation test:
~/Downloads, you can change it)./scriptRemoved step:
Do the following to run the main test:
./script --mainRemoved steps
Make some adjustments to match your own way of coding and structuring the files.
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?
What do you mean by 2-edge-connected components?
https://codeforces.net/blog/entry/83980 and https://en.wikipedia.org/wiki/K-edge-connected_graph
Thanks, I see this is the rest of the components which remain when we remove the bridges (except when it's single node). Now I feel it is provable what I submitted during the contest intuitively.
The pretests seemed kind of weak. Was this intentional? Regardless, the problems were very nice.
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%.
Are you going to have stonger pretests in the actual contests?
+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.)
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.
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.
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.
+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.
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.
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.
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.
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.
My solution failed due to binary searching up to ~1e16. I think the answer could be up to ~2e16. Nice problems!
Can we get some of the edge cases, sir?
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.
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.
Thank you. got 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.
you could as well remove inputs if the test cases are going to be this weak.
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.
Thanks for the contest and problems. I like a few things that are kind of unique in Hacker Cup:
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.
Yeah, you took a lucky ticket :)
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
Have you downloaded the result you submitted during the contest and verified the results are expected?
yes. for same input my contest submission result shows "NO" when practice submission shows "YES" :3
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.
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
"Road to Nutella" was a lovely problem — absolutely loved solving it!
Yeah, I would second that.
the funny thing is everyone red and above said the problem wasn't good while yellow and below thought it was...
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.
The sys-tests were also not very strong — my solution has a major bug but it passed
Really? It was like the hardest problem I solved during a contest — took 2/3 hours coding 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...
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 ;)
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".