Meta Hacker Cup Round 2

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.

Rules are rules. No exceptions.

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.

Why are you compiling the input data?

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

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

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

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.

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

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

T-shirts are given for under 2k rank?

Oh wow :(

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?

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

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.

I also got it wrong :(((((

Even masters are failing it, give us grace marks lol

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.

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

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

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

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.

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?

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

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

void solve(ll tt){
    ll r,c,k;
    cin >> r >> c >> k;
    ll a[r][c];
    for(ll i = 0 ; i < r ; i++){
     for(ll j = 0 ; j < c ; j++){
        cin >> a[i][j];
     }
    }
    ll b[c][r];
    for(ll j = 0 ; j < c ; j++){
      for(ll i = 0 ; i < r; i++){
         b[j][i]=a[i][j];
      }
    }
    for(ll i = 0 ; i < c ; i++){
       vector<ll> temp;
       for(ll j = 0 ; j < r ; j++) temp.push_back(b[i][j]);
       reverse(temp.begin(),temp.end());
       for(ll j = 0 ; j < r ; j++) b[i][j]=temp[j];
    }

    ll cnt[maxm(r,c)]={0};
    for(ll len = 1 ; len < maxm(r,c) ; len++){
       ll x = (2*len)+1;
       ll ct[(r*c)+1]={0};
       for(ll i = 0 ; i < r ; i++){
        for(ll j = 0 ; j < c+x; j++){
              if(j<c) ct[a[i][j]]++;
              if((j-x)>=0)ct[a[i][j-x]]--;
              if(j<c){
              if((i+len)<r&&(j-len)>=0&&(j-len)<c) cnt[len] += minm(x,j+1)-ct[a[i+len][j-len]];
              if((i-len)>=0&&(i-len)<r&&(j-len)>=0&&(j-len)<c) cnt[len] += minm(x,j+1)-ct[a[i-len][j-len]];
              }else{
                if((i+len)<r&&(j-len)>=0&&(j-len)<c) cnt[len] += minm(c,x-(j-c+1))-ct[a[i+len][j-len]];
              if((i-len)>=0&&(i-len)<r&&(j-len)>=0&&(j-len)<c) cnt[len] += minm(c,x-(j-c+1))-ct[a[i-len][j-len]];
              }
        }  
       }
       x = (2*(len-1))+1;
       ll lena = len-1;
       for(ll i = 0 ; i < c ; i++){
        for(ll j = 0 ; j < r+x; j++){
              if(j<r)ct[b[i][j]]++;
              if((j-x)>=0)ct[b[i][j-x]]--;
              if(j<r){
              if((i+len)<c&&(j-lena)>=0&&(j-lena)<r) cnt[len] += minm(x,j+1)-ct[b[i+len][j-lena]];
              if((i-len)>=0&&(j-lena)>=0&&(j-lena)<r) cnt[len] += minm(x,j+1)-ct[b[i-len][j-lena]];
              }else{
               if((i+len)<c&&(j-lena)>=0&&(j-lena)<r) cnt[len] += minm(r,x-(j-r+1))-ct[b[i+len][j-lena]];
              if((i-len)>=0&&(j-lena)>=0&&(j-lena)<r) cnt[len] += minm(r,x-(j-r+1))-ct[b[i-len][j-lena]]; 
              }
        }    
       }
    }
    ll sm = 0;
    for(ll i = 1; i < maxm(r,c) ; i++){
       sm += cnt[i];
       if(sm>=k){
         cout << "Case #" << tt << ": " << i << ed;
         return;
       }
    }
}

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

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.

using ll = long long;

void solve() {
  int r, c; ll k;
  cin >> r >> c >> k;
  unordered_map<int, vector<pair<int, int>>> ownership;
  for (int i = 1, owner; i <= r; ++i) {
    for (int j = 1; j <= c; ++j) {
      cin >> owner;
      ownership[owner].push_back({i, j});
    }
  }
  int max_score = max(r - 1, c - 1);

  vector<ll> total_pairs(max_score + 1, 0);
  for (int score = 1; score <= max_score; ++score) {
    // note that this loop is not O(max(R,C)^2) below, it's just O(1)
    for (int dx = -score; dx <= score; dx++) {
      for (int dy = -score; dy <= score; dy++) {
        if (max(abs(dx), abs(dy)) != score) {
          continue;
        }
        total_pairs[score] += 1ll * max(0, (r - abs(dx))) * max(0, (c - abs(dy)));
      }
    }
  }

  vector<ll> total_same_owner_pairs(max_score + 1, 0);

  vector<vector<int>> prefix_area(r + 1, vector<int>(c + 1, 0));
  for (const auto& [owner, cells]: ownership) {
    int n = cells.size();

    if (n <= 800) {
      for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
          int dx = abs(cells[i].first - cells[j].first);
          int dy = abs(cells[i].second - cells[j].second);
          int score = max(dx, dy);
          total_same_owner_pairs[score] += 2;
        }
      }
      continue;
    }

    for (int i = 0; i <= r; i++) fill(prefix_area[i].begin(), prefix_area[i].end(), 0);

    for (const auto& [x, y]: cells) {
      prefix_area[x][y] = 1;
    }
    for (int i = 1; i <= r; i++) {
      for (int j = 1; j <= c; j++) {
        prefix_area[i][j] += prefix_area[i - 1][j] + prefix_area[i][j - 1] - prefix_area[i - 1][j - 1];
      }
    }

    vector<ll> owner_counts(max_score + 1, 0);
    for (const auto& [x, y]: cells) {
      for (int score = 1; score <= max_score; ++score) {
        int x_min = max(1, x - score), x_max = min(r, x + score);
        int y_min = max(1, y - score), y_max = min(c, y + score);
        int area = prefix_area[x_max][y_max] - prefix_area[x_min - 1][y_max] - prefix_area[x_max][y_min - 1] + prefix_area[x_min - 1][y_min - 1];
        owner_counts[score] += area - 1;
      }
    }

    for (int score = 1; score <= max_score; ++score) {
      total_same_owner_pairs[score] += owner_counts[score] - owner_counts[score - 1];
    }
  }

  ll total = 0;
  int answer = -1;
  for (int score = 1; score <= max_score; ++score) {
    total += total_pairs[score] - total_same_owner_pairs[score];
    if (total >= k) {
      answer = score;
      break;
    }
  }

  cout << answer << endl;
}

What was your complexity?

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.

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

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.

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?

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.

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.

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)

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

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

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.

Simplest solution: cell mac, buy windows/linux.

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

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

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

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.

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?!

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.

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?