SecondThread's blog

Meta Hacker Cup Round 1 Editorial
By SecondThread, history, 19 months ago, In English

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 :)

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

Comments Comments (28)
| Write comment?
»
19 months ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

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!

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

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 :).

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

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

    → Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it -21 Vote: I do not like it

.

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

    That's not how the contest format works. Besides, what does it matter? The number of advancers is not bounded.

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

      It does matter!!!

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

        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.

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

          Can you please quote the exact section where it says

          Spoiler
          I actually found this
          → Reply
          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
            ← Rev. 2   Vote: I like it +8 Vote: I do not like it

            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.)

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

              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!

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

    Wow, how the hell this code passed?!

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

      Ah, maybe he just accidentally submitted A1 code along with A2 output, because it looks like the correct solution to A1.

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

Were A2 tests weak?

Looks like there isn't any test with K = 1 where the deck is "mirrored". Example:

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

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.

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

    I don't think the test cases are same for everyone.

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

      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.

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

        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.

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

          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).

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

            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.

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

    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 :)

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

My A2 "solution", which sorts the difference arrays and compares if they are equivalent, fails with the countertest

6
1 1 2 1 1 2

1 1 2 1 2 1

with any $$$k>1$$$. It still managed to pass pretests.

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

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.

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 5   Vote: I like it +10 Vote: I do not like it

    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

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

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

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

In A2 editorial:

One possible solution is to concatenate A with a copy of itself and search for whether B occurs as a substring using a linear time string-matching technique such as the Knuth-Morris-Pratt, Boyer-Moore, or Z algorithm.

I used python's str in s but 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.

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

    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?

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

      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).

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

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.

→ Reply