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

B1/B2: Watering Well

C: Lemonade Life

Feel free to leave your thoughts on the problems below :)

• 23 hours ago, # ^ | Ah, thanks, fixed the link

• 22 hours ago, # ^ | FWIW a lot of people tried a version with quadratic memory and 35k^2*log memory, which we wanted to fail, yeah.

23 hours ago, # | I observed that Some of the Accepted solution on Question A2 are Actually Giving Wrong Output. For Example Prashant's Code [Global Rank 422 ] is giving wrong Answer , still it got Accepted His Code Input : n = 6 , k = 1 A = [ 1 2 1 3 4 6 ] B = [ 1 3 4 6 1 2 ] His Code Output : NO Expected Output : YES I request SecondThread to Re-Evaluate all the submissions of Problem A2 .

• 22 hours ago, # ^ | That's not how the contest format works. Besides, what does it matter? The number of advancers is not bounded.

  • 22 hours ago, # ^ | It does matter!!!

    • 22 hours ago, # ^ | 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.

      • 21 hour(s) ago, # ^ | Can you please quote the exact section where it says Spoiler I actually found this

        • 21 hour(s) ago, # ^ | ← Rev. 2 →   +8 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.)

          • 21 hour(s) ago, # ^ | 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!

• 81 minute(s) ago, # ^ | Wow, how the hell this code passed?!

  • 78 minutes ago, # ^ | Ah, maybe he just accidentally submitted A1 code along with A2 output, because it looks like the correct solution to A1.

2
4 1
1 2 1 2
1 2 1 2
6 1
1 2 3 1 2 3
1 2 3 1 2 3

• 21 hour(s) ago, # ^ | I don't think the test cases are same for everyone.

  • 21 hour(s) ago, # ^ | 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.

    • 21 hour(s) ago, # ^ | ← Rev. 2 →   0 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.

      • 12 hours ago, # ^ | ← Rev. 2 →   0 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).

        • 3 hours ago, # ^ | ← Rev. 6 →   0 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 -g will 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 use ifstream and ofstream. Or just run your program like ./b < in.txt > out.txt so you don't have to use freopen.

• 86 minutes ago, # ^ | 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 :)

• 19 hours ago, # ^ | ← Rev. 5 →   +10 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

  • 18 hours ago, # ^ | Oh right, it is indeed $$$O(n^2)$$$. I guess I am just one of those who got lucky with A2.

• 16 hours ago, # ^ | ← Rev. 2 →   +8 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 strstr function 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?

  • 16 hours ago, # ^ | 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).

• 15 hours ago, # ^ | ← Rev. 2 →   0 Speaking of speeding up string matching using built-in API, I mapped input numbers to 0,1,2... and it turned out to be almost 3 times faster than searching directly in the input numbers.