SecondThread's blog

By SecondThread, history, 3 weeks ago, In English

Meta Hacker Cup Round 2

It's Rabbit Hacker Cup Season! Round 2 begins in under 24 hours on the Hacker Cup site. We hope to see you there after Round 979!

As in previous years:

  • To qualify for the human track of Round 2, you must have finished within the top 5000 of Round 1.
  • For those competing in the human track, the top 2000 placing participants will win a limited edition Hacker Cup shirt. We'll distribute shirts and share more information about this after Round 3.
  • The top 500 placing human-track participants will advance to Round 3.

As always, we recommend taking care to make sure your code is correct before making submissions, and making sure you are familiar with how to run code on large files without trying to paste megabytes of data by hand. I'd highly recommend reading -is-this-fft-'s blog post on this if you haven't. Additionally, one problem this round has especially large input, so we recommend pre-downloading the zip file (and necessary tools to unzip it if you're using Windows) for that problem.

One thing that's different this year is that we're allowing anyone who isn't participating in the human track to register and compete in the AI track for Round 2, even if you didn't compete in the AI track for Round 1. You can register up until the contest begins here.

Good morning, have fun, and we hope to see you on the scoreboard! Hop on over after Codeforces Round 979!

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how can we pre-download the zip file ...

we should code the solution then pass a test file before we can download the zip file.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    SecondThread Can you actually elaborate on that question? I also don't understand what pre-downloading means if in order to get to the zip archive one needs to have at least some solution to the problem in order to pass validation tests.

    I've actually run into this issue with the large size of the archive — I had somewhat working solution 10 minutes before the end of the round but couldn't download zip archive in time. You might ask — how it's possible, it's just 100 Mb? Well, in some countries Meta services are blocked and we have to use VPN and sometimes it might be extremely slow. Also once I was solving MHC in a cafe and I only had mobile internet which was also not up to speed.

    So in order to solve this problem with the speed of downloading I suggest you to consider the following 2 options for the future:

    1) provide a generator so we only need to download a small file with generator parameters — the pros of this approach are obvious, the cons of this approach is that it's harder to provide a good test coverage due to the way the input is generated;

    2) provide zip archives with tests cases to all problems in the beginning of the round (or, maybe, even some time before the round) — and then give away passwords to the respective archives only when validation was passed and the button to start a 6-minute timer was pressed.

    Idea #1 is definitely not novel and was discussed multiple times but what about idea #2? I mean, it's not novel too but I don't remember seeing the discussion about such possibility in regards to the MHC.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I think #2 is what's OP is recommending. I think it's a reasonable request.

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

A friend of mine performed exceptionally well in last year’s Round 3 competition but was unable to participate in Round 1 this year due to illness. We are seeking guidance on how to contact the organizers, as we hope to inquire about the possibility of registering for Round 2 human track.Kindly exclude the official email address, as it has been over a week without any response.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    Rules are rules. No exceptions.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +74 Vote: I do not like it

    Unfortunately, we won't be able to make exceptions because doing so in this case wouldn't be fair to others who had to compete in Round 1. I wish your friend good health though.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +151 Vote: I do not like it

      But sir, I performed exceptionally well on my discrete maths exam back in 2010. Today I'm unable to participate in MHC Round 2 because I will be tired after Codeforces round and will need to rest and watch some TV. I am seeking guidance how can I get a bye to Round 3. Kindly exclude me from any refusal to my request.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

today when entering the contest i found out i didn't qual but two weeks ago the website said i did and got in the top 2700 but now it gave me WA on A but it was AC two weeks ago is anyone experiencing the same issue

»
3 weeks ago, # |
Rev. 3   Vote: I like it -29 Vote: I do not like it

Ignore.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    Why are you compiling the input data?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      In the final submission of 6 minutes, we had to submit code and output, which took a lot of time to run on the password-protected test cases. Nevertheless, I found out that my solution was not optimal

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Please tell me the intended solution for A2 isn't actually finding all $$$233,519,804$$$ possible mountains $$$\lt 10^{18}$$$ and just checking which satisfy each test case...

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    that's what I did after I couldn't see anything for one hour and it worked

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    There are only $$$73\,025\,424$$$ of them though.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      My code generates $$$233,519,804$$$ which means I almost certainly have duplicates or invalid values then, zero clue how I passed the hidden tests then ¯\_(ツ)_/¯

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

        I think you are checking 19 digit numbers which is unnecessary.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +48 Vote: I do not like it

    You can meet in the middle. All that matters is the height, the number of digits, the middle digit, and the mod values.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So, The person we are replying under has in fact checked for 19 digit numbers that is why there were 233519804 mountains but still he was able to submit and get correct answer. Meanwhile I checked for only 73025424 mountains but my code took around 5min 45 sec to run on my laptop and I missed submitting by exactly one sec(and I immediately sent both the source code and output in the clarifications page). I understand that my solution is not optimal however If I had to guess, most of accepted solutions for problem A2 would have been similar to mine and not to that of the optimal solution. My rank would have been around 1200 I believe if it had gotten accepted but now it is around 2500.Think about the difference in ranks because of the format of this contest. I am sorry, but it is hard for me to take this format seriously. By next year, my skill will hopefully be a lot better than it is now but unless the format changes I am not interested in attending this contest.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you show your code?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sorry, I forgot to reply to you after submitting on codeforces. https://codeforces.me/contest/4/submission/286850906. I know I could have optimized this solution but I checked the max case (0,10**18,1) before downloading the input and it ran in less than 5 minutes. So, I did not want to optimize this and do the max case to check again and take even more time. Also, I ran it just now, it took 5 minutes 2 seconds to finish this time.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            I did a brute force one and as far as I can remember after submitting the code for A2 I still had 3+ minutes left . You took that much time , is it because of Phython code? ( I again run it and it took 33 sec. )

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        A trick is to run python code using pypy instead of python. It goes much faster in loops.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Divide a mountain into prefix + center + suffix.
    For example, 1356442 = 135 + 6 + 442 (as a string).
    Fix the prefix & center, then you can find the value of suffix%m.
    By storeing all possible suffix, you can count how many valid suffix are there, by using g++ tree binary search.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is actually finding all $$$233\,519\,804$$$ possible mountains $$$<10^{18}$$$ ahd just checking which satisfy each test case.

»
3 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

Why many people failed B?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    When transitioning from one game state to the next, you have to make sure that the new piece added belongs to the current player, and not the other player

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Finally, after 4 years participate contest, I won the shirt

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    T-shirts are given for under 2k rank?

»
3 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

lol somehow all my 3 solutiong failed after tests lol

»
3 weeks ago, # |
Rev. 5   Vote: I like it +177 Vote: I do not like it

You may notice that ~95% of submissions to B were incorrect. Here's why everyone was wrong:

A player could win in some position, but might not be able to finish the game because it might be the wrong person's turn to continue playing at some future point before the grid is filled. For example, consider the following completed grid:

RRYYYYY
RRRYRRY
RYRYRYR
YYYRRYY
YRRRYRR
RYYRYYR

Y could win with this grid:

RR.YYYY
RR.YRRY
RY.YRYR
YY.RRYY
YR.RYRR
RY.RYYR

But if that happened, the bottom cell on the third column would be incorrect. It would be R's turn, but Y needs to play in that cell to reach the target end state. Very few contestants realized this.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Oh wow :(

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    so when for a state currently can not determine who can win -> 1 step that one can win, we also need to check later all the step is valid, right?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Essentially yeah. You need to check both:

      • can you be the FIRST to win, and also
      • if you are the first to win in that way, can you continue playing from there and get to the end state for at least one of those ways.
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    That proves that 95% of people can't read problem statements. Including me.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      AI had no chance with this problem as well :)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -113 Vote: I do not like it

    Even tourist, jiangly and Benq got it wrong.

    How is this a B? This has to be some crazy 3500+ rated problem. Since none of them could solve it.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +72 Vote: I do not like it

      "Crazy 3500+ rated problems" have lots of hard observations. This is completely different: there's just one thing that most people didn't realize they had to check.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -98 Vote: I do not like it

        "One thing" ?

        "Hard observations" ?

        Even the highest rated users on CF couldn't get it?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +61 Vote: I do not like it

          You realize that you can only submit once... Just like how the best mathematician in the world can get a school math problem wrong if he or she makes a careless mistake

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also got it wrong :(((((

    Even masters are failing it, give us grace marks lol

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +76 Vote: I do not like it

    Very nice and tricky corner case, and a great decision to keep it out of the validation set! Didn't have so much fun from failing systests in quite a long time.

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

      I wouldn't really call this a corner case (not even an edge case). My in-contest solution completely ignored the constraint that "C goes first and F and C alternate" and still passed validation.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    wait I didn't consider that it might not reach the end, hold on

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +115 Vote: I do not like it

    Nice trick! However, I have this test case in my data that I'm not sure about:

    CFFFFFF
    CFFCFFF
    CCCFFCC
    CCFFCCC
    FFCFCCF
    CCCFCFC
    

    My output is ?, and so is ecnerwala's (both failed). I have run ksun48's and never_giveup's codes, and they both output F. However, I think C can win here:

    • C goes to column 1;
    • F goes to column 1;
    • now, C and F go to column 1 and column 4 alternately, with C finishing their line first.

    This might suggest that the intended outputs are wrong, unless I'm missing something.

    EDIT: I see now, it seems I have misunderstood it, and the trick is even trickier than I thought! Ignore my comment :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Looking into it...

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Hi, I am confused how expected answer for below test case is $$$?$$$
        whereas my output is $$$F$$$. And even in final state, connie doesn't seem to have a winning pattern. Am i missing something?

        CFCFCCC
        FFCCFFC
        FFFFCCF
        CFFFCCC
        CFCFFFC
        FCCCFCF

        EDIT: I completely missed considering left upper diagonal paths. There are such winning pattern for connie.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +60 Vote: I do not like it

      If they play in this order, what are the last 4 moves?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +127 Vote: I do not like it

      To clarify my misunderstanding: it's not just that the person to continue playing is wrong; there needs to be a whole valid sequence of moves to finish the game from that point. Thus, I believe the test data is actually correct.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ironically enough, my solution didn't treat this test in any special way. However, I decided to miss a - 1 in one place; when I corrected this, it passed in upsolving

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    That makes so much sense, thanks for the example. In hindsight that was a beautiful problem, I like that MHC problems are somewhat of a different style than other CP competitions.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    SecondThread How did you construct such examples?

    Say, I'm a contestant and I think about this, and I want to create an example (to test my code) where it looks like both can win but actually only one player can win because of this. How should I even create such a grid? Can't find a way to make one.. (of course now it's easy because I have access to the test cases where I got WA)

    Did you just run code that didn't go all the way up to the end and code that did, both on many many inputs, and selected inputs that had mismatched outputs to include them in the final test set?

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't write data for this problem, but I believe we created both correct and incorrect solutions, generated thousands of cases, and kept only the most interesting ones which caused people to be most likely to fail. Some of these include our testers.

      I don't think any instances of this were things people were able to come up with by hand, I think they were generated and checked with code.

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Makes sense, seemed like the easiest way. See you next year hopefully :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to solve C faster than $$$O(R \cdot C \cdot \max(R, C))$$$?

I spent 20-30 mins hyper-optimizing my solution since it was around the 6 minute mark for 50 max tests. While I expected it to run faster on the actual tests, I'm still surprised they ran within 20-30s, is this the intended complexity?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    I did $$$O(RC \log^2 RC)$$$ using 2d BIT and binary search.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I use the same approach, but I can't meet the TL lol
      Any faster solution?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can use multiple threads, it will work 5-10 times faster (depends on your CPU). Tourist have a nice template for this

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I did O(N^2 * log^3N) with multithread and it works in around 15s.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wrote for the same complexity , passed validation but somehow on the large file , the program compiled successfully but somehow there was no output on my txt file , couldn't debug why :(

    code
  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    Yes. My solution runs in $$$O(R \times C \times log^2(max(R,C)))$$$. The official analysis should be published shortly.

    UPD: Published now: https://www.facebook.com/codingcompetitions/hacker-cup/2024/round-2/solutions

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    I believe my solution is $$$O(\frac{(R C)^2}{\max(R, C)}) = RC\min(R,C)$$$. My general idea is to calculate total number of hops for each score (ignoring the different owner condition) and then subtract the inter-owner pairs.

    I do a little trick where if owner has small amount of cells, I can calculate the total hops it has between its own cells in $$$O(n^2)$$$ where $$$n$$$ is the number of cells owner has. When this number is larger, I instead do $$$O(RC)$$$ approach with prefix sums.

    Code
»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

why the input is 100MB in C? My pc isn't that good so I couldn't submit within the 6 min. Sadly bc of that I didn't qualified to round 3 :(

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What was your complexity?

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it -10 Vote: I do not like it

      $$$O(RC\log{}^4RC)$$$ I think, doing a binary search using a 2D BIT in a map so I can query how many apperances of each element are in a rectangle. (sorry for miscalculating a log I guess)

      My code
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        On a brief glance, your solution isn't $$$O(RC log^3RC)$$$ but at least $$$O(RC log^4RC)$$$ (extra log from the fact that your BIT is a std::map). Probably even more, because you use a different BIT/Fenwick tree for each distinct $$$B_{ij}$$$

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        It's $$$O(R C \log^4 RC)$$$ (binary search, first dimension of the BIT, second dimension of the BIT, map). Your solution has been running on my computer for a while too, I doubt that it's intended. $$$TRC \log^4 RC \approx 2.7 \cdot 10^{11}$$$.

        You can remove one of the logs by not using a map.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          my bad, thx for the analysis ^^

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +15 Vote: I do not like it

    I did it 100% correct, but timer expired.

    That was my code using Fenwick tree and Binary search on possible scores code

    When I uploaded the output file, even the submission window had an error from meta side and at bottom left. Got some error message "Can't process your submission". I had to reopen the submit again and unfortunately, the code was re built by mistake, so output file became empty and output finished just 1 second after the timer expired!

    I did a clarification instantly during the round, but I don't know what will happen

    They just told me submission is created, Thanks meta.

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Really Bad Pretest for problem B

»
3 weeks ago, # |
Rev. 4   Vote: I like it +16 Vote: I do not like it

God B is so tricky to get all the cases.

I tried all possible prefixes of solutions, which are 7^7.

After that to see if there's a winning one for the player you need to:

  1. Make sure the number of F differ with number of C by at most 1. (C needs to be in front).

  2. There's only 1 winner, and that winner can put a piece at the top.

  3. Make sure it's actually possible for the players to reach this state by putting F and C, for example this state:

C??
C??
C??
C??
FFF

Is not reachable, since C needs to put the first piece, so this isn't a winning state for C. Also 4. Make sure you can continue to finish board

I only realized about 3 after the contest :(, and until comments missed 4.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could only solve A this time, but it was enough for the T-Shirt.

In fact, it was enough to advance, if you were very fast.

»
3 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

coding competition :)

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

problem B was a bloodbath

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The AI track went well.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Still better than Round 1 where there was 1 correct submission in the AI Open Track :P

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    They solved 40% of the problems before humans could. Not sure if this is ironic or not--obviously the smartest humans are smarter than the best AI, but lots of people came up with surprisingly not-so-bad AIs to do nontrivial problem solving on things they had never seen before.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      My mistake; at the time of the posting, there was only one submission with 0 points in the standings. I guess the AI track standings got updated later than the Human track ones. Now that I see the "real" standings, it's pretty impressive!

»
3 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

How is the expected output for this test case F?

CFFFFFF
CFFCFFF
CCCFFCC
CCFFCCC
FFCFCCF
CCCFCFC

I believe C can win first, so the answer should be ?. What am I missing here?

Simulation for C's win

EDIT: I see the issue. This is not a valid state, i.e. following moves can not end in the same state as the input.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not only does C have to be able to win, but you also need to be able to fill out the rest of the grid to reach the target end state. I suspect that's what you're doing incorrectly. Do you have a path to fill the entire grid?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Figured it out shortly after I posted the comment. Edited, thank you!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You cannot continue the simulation to generate the entire grid, as at some point you will not have any option to put F or C to put in any last available column.

»
3 weeks ago, # |
Rev. 4   Vote: I like it +19 Vote: I do not like it

My Meta Hakcer cup experience:

Year 2021: rank 2700+ in round 2, didn't get a T-shirt.

Year 2022: rank 900+ in round 2, get a T-shirt

Year 2023: rank 800+ in round 2, get a T-shirt

Year 2024: rank 200+ and proceed to round 3 for the first time. (Failed the problem B sadly)

So proud to see I am making progress. Wish this year I can change my T-shirt style to top 200.

For this contest, I just want to say the extremely weak pretest, especially B and C. But at least if you finish A1 and A2 or just A1 in 10 minutes, you can get a T-shirt.

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Increase the number of T-shirts to 3000, plz :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

IS next round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

ignore my bad english

i used this template for C stack_increasing which passed Validation testcases , so i submitted my code

code

which later failed on the final input file , but after the contest i tried to run it without using the template for increasing the stack size and guess what i got correct output

i just missed a meta tshirt just because of this T-T

»
3 weeks ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Time to retire

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

SecondThread can you help me understand why the expected output for following test is ?.

CFFCCFC
FFCCFCF
CFFFCCC
FCFFFFC
CFCFCFF
CCFCCFC
  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If the expected output is ? that means either player could win. Without tracking through the whole thing, I'd expect C can win with 4 going down and right on the left side, and F could probably win with the 4 horizontal Fs in the middle.

    There are other things you'd have to verify too to validate that though.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but there's no way C can have four consecutive burrows to be able to win no?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The burrows are allowed to be diagonally. There are four consecutive diagonal C burrows there.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          sorry, I really couldn't find four consecutive diagonal C.
          may be I am missing something. I think if we choose one direction, we must continue in the same direction, am I right?

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            First column, fourth character from bottom, it's a C, you can make a diagonal by going down and rifht

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              thank you, I get it now, I completely missed considering left upper diagonal paths.

»
3 weeks ago, # |
  Vote: I like it +58 Vote: I do not like it

Dude's blogpost has too many downvotes to appear in the "Recent actions" column. Say thanks to problem B :)

»
3 weeks ago, # |
Rev. 3   Vote: I like it +31 Vote: I do not like it

Why make the validation tests intentionally weak? They would have been much stronger if they were simply a representative subsample of the full test set:

A1 / A2 / C: Can pass validation without reading in input as long longs.

B: Can pass validation without even checking for diagonals. Also, although it makes some sense not to include the special case mentioned above in validation, I think it was a strange decision to effectively remove a whole problem from counting toward round 3 qualification for the vast majority of contestants.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

    But why not? This increases the variance of the results, making the competition more exciting, and rewards those who make less bugs much more than other contest formats.

    And unlike weak pretests in CF, here you have the validation input and can decide to do additional testing yourself after seeing it is weak.

    (Weak pretests in CF are totally fine as well in my opinion)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Well, I think at the end of the day, it is just the format of the competition, and it is a nice switch-up. Still, it was a very frustrating experience for some (including me) after stress testing B and C and FST both and not qualifying (Me failing C was totally again totally my fault but was influencd by not having a lot of time after spending most of it on B). Of course, people that don't advance will always be frustrated, but this makes it extra painful. They definitely knew a lot of people would FST on B, and that with B being implementation heavy, it feels a bit random if you get it. For instance, if you start the DP with an empty board, you get WA, but if you start with the full board, you get AC. (I don't know if it is because of weak TC or if it can be shown that doing it backwards is sufficient).

      With that being said, I think it is fair that I did not advance since my code was wrong; just not a good experience for me. 

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

B and D are nice, thanks! Though I did too bad at B during the contest, after upsolving I feel the problem is indeed hard (even after getting the right idea the implementation could miss many details and the debugging is not easy).

»
3 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

To showcase unique strategies available in the MHC format (and because I find it entertaining) I passed C during the contest with a $$$O(R^2C^2)$$$ bruteforce solution. The code is surprisingly straightforward and would have taken me way less time to implement than a "proper" one, therefore this is actually a viable strategy; it would be harder for me to qualify if this was not allowed.

My idea is like this: For each $$$d$$$ I want to count the number of pairs with distance $$$=d$$$. The answer is the first index with prefix sum $$$\geq k$$$. For one location $$$(i, j)$$$, all locations with distance $$$d$$$ from it lie on the edges of some square. We can easily count the answer on one of the edges of the square with 1 line of code:

for (int x = max(0, j - d); x < min(c, j + d); x++) if (grid[i + d][x] != grid[i][j]) count += 1;

Rotate the grid and repeat this 4 times, and sum over all $$$(i, j)$$$ and we are done. A few observations:

  1. Each (unordered) pair is counted twice, and we only need to do it for 2 edges (top and left) to count each pair exactly once. This cuts the constant factor by 2.
  2. It turns out the above code is very SIMD-friendly and LLVM happily generates fast AVX2 code for me.

With these optimizations, a worst test case (with answer = $$$799$$$) takes about 20 seconds to run on my Zen 4 laptop CPU, so processing test cases in parallel using 4 threads is enough to guarantee that my solution finishes in 6 minutes.

Submission link (warning: ugly code)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That must have felt great. Congrats!

    Did you compile/run in a special way to take advantage of fast AVX2 code?

    I tried to replicate in C++ but was unable. Curious if anyone was successful.

    My compile flags: g++-14 -O2 -std=c++20 -march=native

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In B, I encountered segmentation fault with DFS, and remembered we had to expand stack sizes in hacker cups.

In my old memories, 'ulimit -s unlimited' or something like that worked, but I couldn't manage to enlarge the size.

My environment is Apple M3 MacBook Pro with macOS Sonoma 14.7. Does someone have a solution?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    On Mac compiling with the flag -Wl,-stack_size,20000000 gives 512MB stack size.

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      It gives ~19MB stack size as number passed represents bytes.

      You need to pass 0x20000000 for ~536MB as the number passed here is hexadecimal and will convert to 536,870,912 in decimal.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It gives 512MB stack I have confirmed. If you try to increase it more it says that 512MB is the max limit. I used it in MHC.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I would recommend you to use the threads and during creating your thread allocate stack memory space as much as you want, this will help you i also did the same.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Simplest solution: cell mac, buy windows/linux.

»
2 weeks ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

I tried B for practice today and the input I got has 115 testcases, so there may be some extra ones that were not in the contest. SecondThread can you tell me please why this input has correct output F and not ?

CFFFFFF
CFFCFFF
CCCFFCC
CCFFCCC
FFCFCCF
CCCFCFC

There is a way for C to win after total 9 moves

C......
C......
C......
C..F...
F..F...
C..F...
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    you have to make sure that the game can continue in a valid way from this state

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      thank you, that makes sense. I didn't realize so many people had posted questions for this one. Sorry for spam.

»
2 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I have something interesting to share.

For A2, I tried generating all possible valid numbers by recursion. It was taking almost 2 minutes to generate on my laptop. Even though it was passing the Validation Test, I felt it would be risky to run the Main Test.

So to save time, I generated all the valid numbers and stored them in a text file (good.txt). Then downloaded the Main Tests and used the saved valid numbers from the good.txt file. This reduced the runtime by 2 minutes and was able to generate the output file within 2-3 minutes.

Did anybody else try doing it this way?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also generated all valid numbers by recursion and stored them into a vector.My code takes 2 minutes to generate the output file.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same, but somehow it was taking only 20 secs to generate all the valid numbers

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also tried to output to a text file too, but the file size is > 1 GB. I thought it would be too big to submit so I gave up this idea. Instead I generated the numbers on the fly instead.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My code is also recursive and I didn’t store all possible case. I just downloaded the main test and run them and it took 33s for me! I don’t get it why yours took that much time! It seems generating all possible beforehand is more time consuming?!

»
2 weeks ago, # |
Rev. 8   Vote: I like it 0 Vote: I do not like it

In the editorial for C they say:

I assume we can't use a 2D prefix sum to get the "sum in a rectangle" in O(1) since creating those would take O(number of bunnies * R * C) which can be up to 400*400*800*800 (400 because we don't need to care if there are not at least two bunnies of one kind) which is 10^12.

What's the simplest we could use? I'm not familiar with the column-Fenwick Tree they mention.

EDIT: I'm pretty familiar with segment trees but only 1-dimensional ones, is this something that would work here in 2D to get the "sum in a rectangle"? If so, any reference that would help me do that? Thanks!

EDIT2: I should've googled better, I assume that's a way of doing it? https://www.geeksforgeeks.org/two-dimensional-segment-tree-sub-matrix-sum/

EDIT3: Actually making all those 2D segment trees would be too much wouldn’t it?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You only use one 2D segment/fenwick tree and for each bunny you add all its burrows, make the query for each of its burrows, then remove all its burrows.

    For the column fenwick tree for each bunny we iterate over its burrows in the order of row first then column. At each burrow we want to count the other burrows at most $$$d$$$ away and less than $$$(i,j)$$$ lexicographically so we remove those too far away like with sliding window and then query $$$[\max(1,j-d),\min(c,j+d)]$$$ and finally add $$$j$$$ in the fenwick tree. This counts the unordered pairs so we need to multiply by 2 to get the ordered pairs.

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Ah that makes sense and at most, for the 2D segment tree, we have 2RC updates per iteration of the binary search so that’s ok?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        Yep which makes the total time $$$O(RC\log(R)\log(C)\log(\max(R,C)))$$$.

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thank you for providing details to what I wrote in my analysis. Take my upvote. Your explanation is exactly what I meant, but I only wrote the high-level idea.

      This counts the unordered pairs so we need to multiply by 2 to get the ordered pairs.

      I actually did not think of this. My implementation adds those burrows with row index ≤ i + d to the data structure and directly counts the ordered pairs. I can imagine the implementation of your solution is slightly simpler.

»
11 days ago, # |
  Vote: I like it +49 Vote: I do not like it

SecondThread when will you remove/disqualify the users from Round 2 who submitted correct output txt document searching from somewhere and submitted wrong code. I still see many such users in the standings and I don't know how many others are there. For example there is an Indian guy at rank 361, who submitted anything in code and got correct output. How is this possible? Definitely Cheating!!!! Please remove all such users from the standings.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Plagiarism checks should now be complete.

    I'm not sure what individual you're referring to, but Aditya Mandal (temp) [rank 361 from India], has passed the plagiarism check. At a glance, his solutions all seem reasonable to me--do you have evidence otherwise?

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it +44 Vote: I do not like it

      SecondThread here is the link of his submission for problem B. You can run his code in your editor and you will see its definitely wrong.

      Submission Link

      Upd 1: Also this is his submission link for problem A2. Also 100% wrong

      A2 Submission Link

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        We've disqualified the submission to problem B, thanks for flagging this case. However, the code for A2 does work properly (it just happens to contain a bunch of dead code).

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          wjomlex and SecondThread why just flag problem B? Isn't it clearly showing a cheating case and that user must be disqualified and removed from the standings coz its the same level offence cheat like that of someone copying a plagiarized code? Also, this is just one of the users in top 500, also there might be so many more in top 2000 because of whom many deserving candidates lost the opportunity to play in Round 3 (like me) or maybe win a Tshirt.

          This clearly shows the weak link in the Meta Hacker Cup Competition. Just get an output txt document from somewhere and in the source code maybe write a Shakespeare Poetry to avoid plagiarism checker... I would suggest to check all users submission code, its hard to find so many others. If this is infeasible maybe from next year Meta Hacker Cup should be held normally like a CodeForces Contest.

          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
              Vote: I like it +20 Vote: I do not like it

            Isn't it clearly showing a cheating case and that user must be disqualified

            There's a difference between obvious, malicious patterns of cheating and potentially just submitting the wrong source file for one problem.

            there might be so many more in top 2000

            I'm happy to investigate any cases you find.

            • »
              »
              »
              »
              »
              »
              »
              6 days ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              There's a difference between obvious, malicious patterns of cheating and potentially just submitting the wrong source file for one problem.

              So CodeForces policy is nonsense when it removes the user even if it find plagiarism even in just 1 code. CodeForces must also just flag that particular problem and not disqualify that candidate from the standings. sarcasm...

              I'm happy to investigate any cases you find.

              This potential failure leak is caused by the competition rules Meta has decided. Why should I check all 2000+ users and find the possible cheaters (which are definitely many more). I don't care about playing Round 3, but the thing is many such candidates including must have been ROBBED (RM fans don't cry over Vini Jr here)

              • »
                »
                »
                »
                »
                »
                »
                »
                6 days ago, # ^ |
                  Vote: I like it +23 Vote: I do not like it

                So CodeForces policy is nonsense when it removes the user even if it find plagiarism even in just 1 code.

                We also disqualify the contestant entirely when we see plagiarism in any of their submissions.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                  Rev. 2   Vote: I like it -7 Vote: I do not like it

                  Alright to help you, I found another INDIAN cheater for you, Nishchay Nilabh (rockhopper130) rank 363

                  This is his submission link for problem B: B Submission Link

                  And this is the result I got it while checking it on Ideone, its a RTE code, hence 100% wrong.

                  Ideone Link

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it +73 Vote: I do not like it

                  Pretty sure we can have a civil discussion about potential plagiarism without bring country of origin into it.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it -10 Vote: I do not like it

                  Alright I apologize, I didn't know that telling nationality is also considered racist :(

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 days ago, # ^ |
                  Rev. 3   Vote: I like it +30 Vote: I do not like it

                  Yessss. Those output file cheaters who submit any shit in source code. I recently told a friend about this vulnerability in Meta Cup formats. RTE when ran his code on the IDE.

                  Disuqalify rockhopper130

              • »
                »
                »
                »
                »
                »
                »
                »
                5 days ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it
                Why should I check all 2000+ users and find the possible cheaters

                You don't have to. And no one actually asked you for this... Just chill

                If this is infeasible maybe from next year Meta Hacker Cup should be held normally like a CodeForces Contest

                Oh shit, here we go again. If you don't like that format, just skip the competition. If you want to participate, just participate. There are a lot of competitions in the world (actually not so many as it used to be) and they don't have to be all the same

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 days ago, # ^ |
                  Rev. 2   Vote: I like it +24 Vote: I do not like it

                  Alright I'm just a 14 yo kid, but I assume you to be 26 or 27 and you have been a LGM. Just let me know where have I offended you or just presenting my case is nonsense? The competition coordinators had no issue with my complaint then why do you have it Sir?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 days ago, # ^ |
                    Vote: I like it +6 Vote: I do not like it

                  Why can't he have issue with your comment if he doesn't agree with it? You do realize that people are allowed to voice their opinions just the same as you have already been doing, right?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 days ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  First of all, I never wanted to offend you personally. But words and phrases that you use sounds quite passive aggressive or toxic. That's why I replied

                  I can perfectly understand how frustrating it might be if you just a little bit missed some top in a competition. I've been in such situations a lot of times and it never ends. But there's a better way than finding cheaters and blaming others. Try to improve yourself, upsolve problems. Learn how to run solutions locally, if you have any troubles with that. So that next year you'll perform much better, get in that top and wouldn't bother about any cheaters

                  After all, t-shirt is not such a big deal

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 days ago, # ^ |
                    Vote: I like it +11 Vote: I do not like it

                  "it never ends" "not a big deal", yeah let's normalize cheating and positively reinforce cheaters with prizes, genius idea 10/10.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  zfnu, that is definitely not what I've meant

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 days ago, # ^ |
                  Rev. 2   Vote: I like it +8 Vote: I do not like it

                  budalnik Its not the issue, idc that I missed Round 3 by small margin but I genuinely love CP and things like this is definitely frustrating for anyone in any sport. Anyone would try to find possible ways to get what they deserved instead of trying next year. I assume that you reached the top of CP before such plagiarism cases started to grow and the competitions where you missed next level was genuine loss, it was not that a cheater stole your spot

            • »
              »
              »
              »
              »
              »
              »
              5 days ago, # ^ |
              Rev. 2   Vote: I like it +19 Vote: I do not like it

              There is another cheater guy/girl ranked 430 (ts12) , whose code gives a compilation error for Problem B. wjomlex, please flag this submission as well. The Problem C Submission, even though its wrong anyways, seems GPT generated suggesting a possibility of cheating. Submission Link: For problem B

              Another user ranked at 366, (noobcoder1106)'s B submission gives 0 for all test cases, hence its 100% wrong (that also looks GPT generated) IDEOne link for B ,Submission link for B

»
4 hours ago, # |
  Vote: I like it +11 Vote: I do not like it

Is there any info about the shipping of t-shirts?