Meta Hacker Cup Round 1 Editorial
Good morning!
As usual, written editorials are available in the solution section of all problems on the Hacker Cup site. I thought this post might also be useful to see what people thought of the problems. After all, feedback is a gift, right?
A1/A2: Consecutive Cuts
Feedback
B1/B2: Watering Well
Feedback
C: Lemonade Life
Feedback
Feel free to leave your thoughts on the problems below :)
Question: is this for the qualification round or round 1? saying this because the links, title, problems are all mixed up (title is mixed, "Hacker Cup" link goes to the qualification round, problems are for round 1)
edit: noticed the fix. thank you!
Ah, thanks, fixed the link
C for me personally didn't run in time (took 6 min to run), and seeing the scoreboard, that seemed to happen to many other people as well. Not sure what could be done here since ideally the slower solutions on faster computers shouldn't pass as well. Hopefully, future iterations have judging servers, so this won't be an issue, but maybe you guys should try testing with worse computers as well, since I doubt everyone has a top-tier computer to run on.
I appreciate all of the team's effort on creating and testing the round. I had a good time overall :).
FWIW a lot of people tried a version with quadratic memory and 35k^2*log memory, which we wanted to fail, yeah.
.
That's not how the contest format works. Besides, what does it matter? The number of advancers is not bounded.
It does matter!!!
I encourage you to read the contest rules. The number of points distributed is the "sum of the point values for all of the input sets he or she correctly solves in that Round", and an "input set" is defined as the downloaded input file (as can be seen by the part which says you should upload the source code and the "output file generated when the competitor's source code is run on the relevant input set"). If you upload an output file with correct answers corresponding to the input you downloaded, as well as a source file which generates the given output provided the downloaded input, then the solution receives the corresponding points. Even if the source does not match the output exactly, that might not matter (see Section 8). Therefore, for the purposes of scoring, it does not matter that the solution fails on test cases outside the downloaded input file.
Can you please quote the exact section where it says
"If you upload an output file with correct answers corresponding to the input you downloaded, as well as a source file which generates the given output provided the downloaded input, then the solution receives the corresponding points. Even if the source does not match the output exactly, that might not matter"
"If, after the close of any Round, an alleged discrepancy is discovered between the source code and the output file for any of a competitor's Submissions that were judged correct at the conclusion of the round, a panel of two or more judges consisting of employees of Meta and/or its subsidiaries shall examine the source code for all Submissions of the competitor for that round. The judges shall determine, in their sole discretion whether a discrepancy exists, and if so whether the discrepancy is trivial or non-trivial. In the event of a trivial discrepancy, the competitor shall be assessed an additional 6-minute penalty for that input set. In the event of a non-trivial discrepancy, the competitor shall forfeit the points for that input set"
The part you quote deals with the scenario in which the uploaded source code does not produce the uploaded output file. It says that a trivial discrepancy does not remove the contestant's points, but only adds a 6-minute penalty. This is what I was referring to when I said a discrepancy might not matter.
More importantly, though, the part you quoted does not refer to the case in which the answers are correct for the downloaded input file and the uploaded source file produces the uploaded output file. In that case, the solution receives full points and that's it.
Please be specific: Are you saying that some solution was marked as correct while failing a test case contained in the corresponding user's downloaded file? I doubt that's the case because grading is automatic. Of course, if that's the case then it should be fixed. As far as I can tell, however, the OP asked for regrading because the solution failed on a test case outside the downloaded input set. Given that the competitor's score is "sum of the point values for all of the input sets he or she correctly solves in that Round" (second sentence, Section 8), that does not matter for scoring.
(It should go without saying that my previous message is not contained verbatim in the rules. Only the portions inside quotes are.)
Yeah I do know the quoted text doesn't refer to the case, but I was referring to a general case, that they should make the Testcases stronger in place of bigger. As you can see the code failed on a very small case! So surely it is not the entirely correct solution. And maybe uphacking might be included or anything to counter these solutions!
Wow, how the hell this code passed?!
Ah, maybe he just accidentally submitted A1 code along with A2 output, because it looks like the correct solution to A1.
Were A2 tests weak?
Looks like there isn't any test with
K = 1where the deck is "mirrored". Example:You can see that we can actually split it into the middle and achieve the answer. I think my code gives the wrong answer for cases like these, but it still passed the official test.
I don't think the test cases are same for everyone.
I'm just trying to understand if my code is fully correct. Looks like there could have been some tests capable of breaking my solution.
If I understand correctly, you can download a file containing all of the testcases by clicking on the "Submit for Practice" button. That way you can check if you were lucky with your randomly-generated input file :)
Edit: I just checked against my own input file and it seems that there is more randomness involved. Never mind.
I submitted the output for B2 3 times in practice mode. The input for contest was different but the input for practice is same I think. Atleast it's the same for the 3 times I downloaded and submitted in practice. I got WA during contest even with correct solution. The output file they have attached doesn't match the output my attached code produces. Acc. to them, it differs for 1 test case. I ran my code for the single test case and found it gives correct answer. Seems like there were lots of false positives (due to weak test cases) and false negatives also (like in my case).
False negatives seem really unlikely. Maybe your code uses undefined behavior, or maybe you don't reset some variables between test cases. Compiling with
-fsanitize=address,undefined -gwill catch some problems at runtime.In particular: Are you sure the output file you uploaded during the competition is well-formed? Or could some line of the file be truncated? You can download it from the website. The reason I ask is because you use
sync_with_stdio(false), but you also use a stdio function (freopen). I am not sure this is guaranteed to work. If you want to read/write from/to a file while using C++ streams, you can useifstreamandofstream. Or just run your program like./b < in.txt > out.txtso you don't have to usefreopen.If so — that's a shame. Most of the time on this problem I spent figuring out how to handle this particular case (my solution initially is very different from the ones given in the official editorial, where it's done quite simply).
BTW, better wording here is "periodical", not a "mirrored". Mirrored string is a palindrome :)
My A2 "solution", which sorts the difference arrays and compares if they are equivalent, fails with the countertest
with any $$$k>1$$$. It still managed to pass pretests.
Edit: nvm, it is $$$O(n^2)$$$.
I did $$$O(n\sqrt{n})$$$ approach for A2: Fix an integer $$$B[j]$$$ in $$$B$$$ so that for each $$$i$$$ in $$$A$$$ with $$$A[i] = B[j]$$$ we can start a basic comparison of the arrays from their respective indices in $$$O(n)$$$. We check if the arrays are the same from the fixed indices and do some casework with $$$k$$$ and $$$n$$$ to determine the answer. We should always choose $$$B[j]$$$ to be the number with the least occurrences in $$$A$$$ since this guarantees we do at most $$$\sqrt{n}$$$ array equality checks.
what is with a testcase like this:
$$$(1~2)^{n-1}~2~1$$$ i.e $$$1~2~1~2...1~2~2~1$$$
$$$(1~2)^{n}$$$ i.e $$$1~2~1~2...1~2~2~1$$$
If you choose the first $$$1$$$ in $$$B$$$ and match it with all $$$n$$$ ones in $$$B$$$ you get a runtime in $$$O(n^2)$$$. Since you need to go $$$O(n)$$$ steps on average before you get a missmatch
Oh right, it is indeed $$$O(n^2)$$$. I guess I am just one of those who got lucky with A2.
In A2 editorial:
I used python's
str in sbut that didn't finish in 6 minutes. Googling it, it seems like it's implemented as Boyer-Moore which has a worst case of O(M * N) (unless you upgrade to python 3.10, but I was using pypy). So it seems like the test cases were constructed to be mean to python and you should probably remove the mention of Boyer-Moore in the editorial.yes, in fact while Boyer-Moore does have a lower "best case" time complexity, it does not guarantee an $$$O(n+m)$$$ time complexity at worst. what you could have used though, is the
strstrfunction in C, which uses Perrin and Crochemore's Two way algorithm (assuming GCC). this method does guarantee an $$$O(n+m)$$$ time complexity (even though some extra constant would be on the $$$n$$$ side). maybe you could mention this in the editorial?on an additional note, Python before 3.10 used a heuristic selection between multiple algorithms, namely Boyer-Moore-Horspool, Sunday, and the Two-way algorithm which I mentioned above. why it did not guarantee a $$$O(n+m)$$$ time complexity though, is that it only used the two-way algorithm when the pattern string is relatively shorter (as already mentioned above, its preprocessing step has some extra constants, making it kind of undesirable for use with big patterns).
Hi, Since this is my first Hackercup, I was curious as to how hard is it get a below 2000 rank in round 2. If there is any relevance at all, what CF rank/rating does it correspond to? Thanks.