SecondThread's blog

By SecondThread, history, 2 months ago, In English

Meta Hacker Cup Round 2

Good morning! Meta Hacker Cup Round 2 starts on Saturday, September 24th in under 24 hours! You're automatically registered for Round 2 if you scored at least 15 points in Round 1.

Important info:

  • You'll qualify for Round 3 if you place in the top 500 in this round.
  • If you place in the top 2000 of this round, you'll win a limited edition Hacker Cup t-shirt.
  • If you qualify for Round 3 as well, and you place in the top 200 of round 3, your shirt will have a special "Top 200" badge on it.

We put a lot of effort into these problems, so hope you'll find this contest as almost as balanced Codeforces Global Round 5. Good luck, have fun, and we'll see you on the scoreboard!

Update: Editorial

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

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

Finally! I'm sick now but I hope I can get better tomorrow and get a T-shirt! Edit: I couldn't get anything. Maybe next year. Great problems through all the rounds though. I really enjoyed this contest

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

Very excited for this round!

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

Just curious, why did you guys decide to host hacker cup rounds in this time period which is different from other competitions like code jam and codeforces rounds?

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

    maybe u just answered your question?

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

      thats insane, but is that rly the reason tho. codejam is in different months and cf rounds probably will change their times for hacker cup

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

      Lol, how he answered his question? If Hackercup is decided earlier to be on an x date in y time, then Codeforces or CodeChef will try not to clash with that particular timing!

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

        Absolutely they will but the fact that it could cause a disruption in other contests' schedules is a good enough reason I suppose.

        Or for all I know, maybe Hacker cup timing has something to do with Meta being an American company.

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

Don't forget to increase stack size. Related link to increase it (c++ & windows)

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

    can you please tell what is the stack size in MB using that number which you mentioned in the video?

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

I am unable to log in to Facebook due to "required maintenance". Will the contest be postponed?

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

    Website is working for me, but the log in button is still broken.

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

      Seems to be working for us. Can you try refreshing?

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

        ok it is fixed now for me after resetting cookies and logging back in

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

    Can you check again? Its working for me.

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

Even in this round, do we get only 5 minutes for submission? Reply fast plz

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

Is there any way to see the number of contestants who solve a problem from the scoreboard?

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

just wanted to suggest something in the Scoreboard UI. Currently, when we fetch the next pages (either using arrow or using start param in queryString), and then we filter out based on country, it displays results from the previously selected offset. It would be better to start displaying results from first page for the selected country because the #pages for a country <= #pages in final scoreboard. I hope that makes sense ?

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

I am getting "This page isn't available". Am I the only one?

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

The editorial for A2 says that all numbers are up to 1e9, whereas the problem statement mention that they are up just to 1e6. Which one is correct?

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

Please make sure to send t-shirts this year. Didn't receive last years t-shirt. :3

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

From last year 2700th to this year 935th, I am making progress.

Although I didn't qualify for round 3, it is still satisfactory because I won both Code Jam and Hacker cup T-shirt this year (I didn't get either of them last year). Therefore, no regret.

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

Just got an AC on D2 10 seconds after the contest :( . Only if there wasn't any validation and all.

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

One small suggestion if downloading/uploading the tests/results remains in the following years: let people who downloads the full input very close to the final time to still upload the output until the timer is up (i.e. probably a few minutes after the contest ended). It has just happened to me that I downloaded the full input for problem D1 less than one minute before the end of the contest and couldn't upload the solution on time just for a few seconds, and without the overhead of downloading/uploading I would have qualified to the 3rd round :(

Beautiful problems by the way!

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

    Yeah same :(

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

    Bad idea. It basically means extending a contest from 3:00 to 3:05 — assuming that a participant hits "start a timer" early enough.

    (One must pass validation first but it can be done with a brute force.)

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

      Yeah, now that you mention it, probably it wouldn't be fair for some people to have a couple of minutes extra. An alternative could be to make validation optional.

»
2 months ago, # |
  Vote: I like it -48 Vote: I do not like it

I want to fuck everyone who created that system of accepting tasks... Is it so essential to run some testcases locally?

Some laptops have small stack so they got RE when they test their code locally////

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

From 0 solve last year, I finally qualified for round 3 this year.

But I am not a fan of the Hackercup download and upload format. For D2 it almost took 2 minutes to run my code. I was confused if it was TLE or if the input was too large to process.

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

    Didn't qualify for round 3, but yeah from 0 solved to 2 solved this year, feels good

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    So, you'd get TL in traditional format

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

    We had a solution that solved it in n*log(n) time. If you had an n*log^2(n) solution, we let that pass as well, though it was a bit more inconvenient for you to run.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -29 Vote: I do not like it

      Where is my t-shirt for last year's contest?

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

From what I understand, the hashing function's performance in A2 is based on the assumption that the values in the array would be randomly distributed.
During the round, I also thought that a simple order-agnostic hasher should work, but because any specially designed test case could easily break it, I stopped implementing half-way.
Since no info. was provided in the problem statement on whether the arrays generated would be random or not, is this something 'guarenteed' about hackercup test-cases, that they will always be random unless specified otherwise?

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

    I don't see how the solution assumes that the values are randomly distributed. We can guarantee that the hashes of combinations of numbers are approximately randomly distributed by randomly generating the hash of each integer.

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

      Oh, I'm sorry.
      I was grossly overestimating the probability of the sub-arrays differing with 2+ numbers, and was thinking of using the hash function only as a pre-check.

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

      sir it would be great if u can give some good resources to learn more about the topic.Thank you.

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

Submitted D2 in the last minute and made it to Round 3. Phew...

Spent too much time debugging off-by-one errors.

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

SecondThread

What's the process of getting the t-shirt? This is first time I have finished amongst top 2000 competitors..

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

A2 use sigma i, simma i^2, simga i^3%mod , failed on only one testcase.....

Small suggestions, can you make the validate input larger? Seems the validate cases are too little & too small

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

It would be good to allow users to download all system tests before the contest starts. Anyways, they will be able to open it only when they have the password.

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

Is there any hacking phase or system testing phase now after this? I wanted to hack my friend's solution

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

Will there be any plag checks ? I came really close to qualify for round 3 :(

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

I had a different solution for A2...

  • Use 3 seg trees: 1 for xor, 1 for sum, and 1 for product%mod.
  • Then check if the xor, sum, and product%mod match for the 1st half and 2nd half.
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i too thought about this idea but i have considered only sum and xor (didn't got idea of product).

    i realized that considering only sum and xor doesn't work.

    is there any way to prove that there exists same set of elements if sum and xor and product%mod of two different sets are equal ??

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

      I think no. This solution is hackable I guess.

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

        may be ,but i think it is very difficult to find that test case

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

          2, 7, 12 — sum 21 — product 168 — exclusive or 9

          3, 4, 14 — sum 21 — product 168 — exclusive or 9

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

        If, said, you hash the original input, and mod it with multiple primes P[] for cross-checks (like the tutorial suggest). Then, you have a new input array corresponds to a prime in P[].

        1. Can you pass the system test with a large enough P[], and 1 operation only ( xor, sum or product)?

        2. If the answer for the question above is yes, then is this an "acceptable" approach? I'm taking the reasoning of the problem setter as "as long as the tester cannot guess and break your algo, it should be good"

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

    I also Used 3 segment trees but 3rd one stored sums of log(A[i]) in range for product

    And I think it's deterministic

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

Less than five minutes penalty to reach rank 2000 , I shouldn’t double check my code after passing the validation set next year!

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

Sadly FSTed in A2 in failed to qualify for Round 3.

My rank became $$${473 \rightarrow 973}$$$ :(

UPD: I just double hashed my single hashed solution and got AC as it was getting WA on just 2 test cases earlier... Hashing is a thing in which we shouldn't trust ;(

I used multiplicative hash trick (similar to XOR hashing).

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

    Which platform did you use to run test cases of A1, my laptop was not able to run the final test cases ;)

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

      Sublime Text with custom input/output.

      suggestion
»
2 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Hi. This was my first Hacker Cup. So I don't really know how you operate things. Do I need to contact someone for the T-shirt? Or does someone reach us through email or Facebook?

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

    If you are lucky enough, you will be notified about your T-shirt.

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

    They don't reply to any contacts. You can only sit and wait

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

I got top 2000 in this round, how do I get the t-shirt? Do I need to contact them?

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

It's that time to get T-shirts again :D

Is there any chance we could get the T-shirts from last year as well? I know many of us didn't receive the T-shirts for 2021, so it would totally make my day to get one, even if it's one year after. (Having the T-shirt is more of a personal-pride thing than anything else; it feels good wearing a T-shirt that I won from a coding contest!)

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

    I read somewhere that they stopped manufacturing 2021 t-shirts, so chances are slim

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

I ranked 143rd in round 3 last year, where is my T-shirt?

Never got any email from facebook, neither do you reply to my email or DM.

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

Seeing many comments on the tshirt, I would like to share my experience last year. I almost missed the email on t-shirt because it was sent by a suspicious looking email address and ended up in my spam. I only learnt about it because a kind soul posted something on Codeforces that the weird looking subject title is actually the tshirt email. So I suggest: (i) checking spam folder regularly (ii) any kind soul who received the email to share on Codeforces so that we are all notified.

I also remember it won't be sent so soon — it was sent in Dec last year after the finals.