Good luck have fun, and see you all on the scoreboard!

Can you please tell the scoring distribution

24 points out of 100?

May be we will need to solve at least 2 problem to advance to Round 2;)

24 points in 24 hrs!

Nice :)

Am I the only one who get "This page isn't available" error when trying to access https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1? I got that error when logged in, but managed to load the page when in incognito.

LoneFox can you help check on this issue?

Are there any prizes like T-shirts for this round?

How strong should we expect the "validation input" to be? Should we expect it to be similar to pretests on Codeforces?

My understanding is that on Codeforces, authors aim to minimize FST, so they try to make pretests as strong as possible, as opposed to intentionally leaving max-size tests or tricky edge cases for systests (aka "full input" on Hacker Cup).

Is there any way to see the total number of problem B submissions done by the other participants during a running contest? Does the scoreboard page track this statistics in real time?

Where did the compressed input form go (i.e. used here last year)? The input was huge on C and I'm not sure if that's the reason my code started to segfault (I don't think I used too much memory nor time), but it sucks to pass validation and not be able to even submit on the real thing :\

If the input size has no affect on that, then it's fine, but I was still a fan of that form of input.

My pc wasn't responding when I tried to run the input for 1 problem and the time expired. Did it happened to anyone else too?

Those who are using c++ and facing problem with stack size adding this "-Wl,--stack=268435456" compiler flag may help. I think facebook should reconsider their judging system as current system is extremely annoying.

It is really annoying. I couldn't submit my A2 due to stack size of my laptop and it is not like I am using too much memory or time.

Facebook should consider changing their judging system to something like what Codejam is using in the future.

Got my A2 validated, but got RTE on the main tests. Figured out it was because of the stack size as I declared the variables in my main function, only after the time passed.

I believe LoneFox had made problem 1 :)

My pc too wasn't able to handle the input file as it exceeded the stack_limit. After the timer expired I realized what I could have done is declared all my variables globally. So those who have low end pc can try declaring the variables globally as it worked in my case although I couldn't submit. Hope this helps.

To all the people whining about stack size on their machine: it's not about the physical limitations of your machine, the stack size is limited artificially to prevent infinite recursion that will eat up all your machine memory (or for some other reason, I don't know computers). Yes, it sucks to learn about it during a huge competition like FBHC. But believe me, many of us encountered the same issue years ago, and at that time you had to get to top-something in round 1 to advance, which meant solving all the problems. I strongly believe that organisers consciously made inputs in round 1 big so that you can check that you are prepared for running big inputs locally in a relatively safe situation: you still have 8 hours left and some problems to solve, you still can get enough points. And it's a good lesson because in the usual competitions you also sometimes need the ability to run huge inputs locally (to measure running time, for example), so go and learn how to set the stack size on your machine (one way for g++ is already in the comments section).

Sucks getting segmentation fault on A2 due to memory constraints and not setting up stack size. Anyways got to learn something now from this which I never paid attention to before

g++ -Wl,--stack=268435456 A2.cpp

IS this correct ?

If anyone is facing problem with cmd, then for codeblocks link

My computer shut down and I couldn't submit A2 in time :(
Me and my potato luck

It looks like 6,809 people advanced to the 2nd round. That's way more than usual.

Please, can stack size warning be put into FAQ? I remember this was an issue in the past which I fixed and then I got a new computer and forgot. Problem shouldn't be scored by who remembers best and has appropriate setup.

(Side note: I guessed the issue immediately, then I found out you can't set stack size on windows subsystem for linux, goodbye C. Don't use WSL, instead use native g++.)

Its really the most hurting moment when you are able to find out the logic of problem and able to code it also, but a single mistake (not putting MOD at the very end step) make your whole submission wrong.

Happened today with me (in Problem A3)

Takeaways: In problems, where we have to take mod , Don't forget to take the mod again at very last step also because putting extra mods will not create harm rather than missing single one.

I misread problem B and though the path lengths can be arbitrarily large, but you're limited to 1000 per cell. Does anyone have ideas on how to solve this problem with modified constraints?

Like it's a bit weird since you can solve

4 4 7 5002 with:
1 1 1000 1000
1000 1 1 1000
1000 1000 1 1
1000 1000 1000 1

You can't solve 4 4 8 5003 (because the right path will just go through the 1s). same with 4 4 9 5003

But you can actually solve

4 4 10 5003 
1 2 1000 1000
1000 1 2 1000
1000 1000 1 2
1000 1000 1000 1

And also 4 4 11 5003 (just switch which numbers are 1 vs 2 in the left path).

My O(N) space bottom up solution for A2.

Also can be optimised to O(1) space easily

typedef long long int  ll;
ll P = 1e9 + 7;

void solve() {
    ll  n;
    cin >> n;
    ll ans = 0;
    string s;
    cin >> s;
    s = '#' + s;
    vector<ll> dp(n + 1);
    ll last = 0;
    for(ll i = 1; i <= n; i ++) {
        dp[i]=dp[i - 1];
        
        if(s[i] == 'X' || s[i] == 'O') {
            if(s[last] == 'X' && s[i] == 'O') {
                dp[i] += last;
                dp[i] %= P;
            }
            if(s[last] == 'O' && s[i] == 'X') {
                dp[i] += last;
                dp[i] %= P;
            }
            last = i;
        }
        ans += dp[i];
        ans %= P;
    }
    cout << ans << endl;
}

There's actually a solution to C which doesn't depend on the maximum capacity being small.

As with the official solution, it's easier to compute, for each edge, how much the capacities would decrease if it were blocked. Let's sort the edges in decreasing weight and insert them into the tree one at a time. Consider an edge between $$$u$$$ and $$$v$$$ with weight $$$w$$$, and let the current sizes of the components containing $$$u$$$ and $$$v$$$ be $$$s_u$$$ and $$$s_v$$$. Then, for each edge $$$e$$$ already inserted into the component of $$$u$$$, we need to apply $$$\text{ans}[e] += \text{subtree_size}_u(e) * w * s_v$$$, where $$$\text{subtree_size}_u(e)$$$ means the current size of the subtree of $$$e$$$ when rooted at $$$u$$$. It turns out this can be modeled using lazy propagation on HLD or a top tree, as the answer is a linear function of the subtree size at any point.

The top tree is a simpler interface, as we can reroot the tree by flipping the root path (this means that we need to store two lazy-increments, one assuming the root is leftwards, and one assuming the root is rightwards).

The HLD solution is more complex, but has the same ideas. It's essentially equivalent to the top tree solution, where we follow each solution with a reroot to the original HLD root; that view can help inform which pieces you need after each update.

At the end, we propagate all changes all the way down the tree to read out the answers.

How come there's a logarithm in the written analysis/editorial of problem $$$C: Blockchain$$$ ?

Editorial proposed complexity: $$$ O(N \times (\log(N) + maxC))$$$

whom should someone contact if he think that his output is correct but the judge has give wa verdict but that also only on 1 test case, the solution is exactly the same as given in the editorial and all the test cases are passing except 1. someone please help.

I thought the problems were reasonably fun. Missed C due to a stupid error (was packing fields into an int64 to speed up python sorting, and now realized that 0x3ffff is only 18 bits and not 20 bits, so I missed the 800k inputs). I'll try to be more careful in round 2.

It is showing me not registered for round 2 even I scored 24 in round 1

Guys, just uploaded approach for problem A2, you can checkout here: https://youtu.be/HWv1FWrrMj0

LoneFox Can you clarify the presentation error issue? Whenever I try to submit for practice in Round1 I always get a presentation error. To investigate the issue, I downloaded the exact file that got AC for me during the contest and that too showed presentation error, which is really confusing! Imagine getting a presentation error after solving the whole problem correctly in the real contest!

LoneFox In the scorecard of Round 1 many participants are named as Unknown Competitor. Is this a bug or something, or my system hasn't loaded the site properly.

Edit — fixed.