LoneFox's blog

Facebook Hacker Cup 2021: Round 1
By LoneFox, history, 3 years ago, In English

Round 1 of the 2021 Facebook Hacker Cup is less than 48 hours away!

The round will begin on September 11th, 2021 at 10am PDT and will last for 24 hours. The contest can be found here.

You're eligible to compete in Round 1 if you solved at least one problem correctly in the Qualification Round.

Everyone who scores at least 24 points (regardless of time taken) will advance to Round 2, which will take place on Sat. Sept. 25th. Please note that all submission judgments will only be revealed after the round ends. More details about rules and other information can be found in the FAQ.

We wish you the best of luck, and hope that you enjoy the contest!

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

Comments Comments (129)
| Write comment?
»
3 years ago, # |
  Vote: I like it +123 Vote: I do not like it

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

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

Can you please tell the scoring distribution

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

24 points out of 100?

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

    From the past rounds I've looked at, it's usually out of 100, and for round 1 you usually need to have gotten AC on the first two problems to advance.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

24 points in 24 hrs!

Nice :)

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

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?

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

    It looks like you've been able to submit since. That may be some transient infrastructure issue.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

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

    I think the easiest way to find out is to just look at the input, you can even instrument your code to measure coverage.

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

      Good idea, I definitely should have looked more closely at the input. (Though it'd be hard to see if it has edge cases that I didn't think of while solving the problem.)

      LoneFox, my question is more about the authors' intent, if you know.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it -189 Vote: I do not like it

      You guys are walking on a thin ice. This kind of communication may be interpreted as assistance in solving/debugging problems from the running contest if you push this further. And my question about the scoreboard UI probably wasn't very appropriate either if we interpret contest rules literally. So I'm dropping out of here.

      Edit: As usual, there's no shortage of simple minded lemmings on codeforces :-) Come on, downvote me more! You will never understand that I just warned people BEFORE they crossed the line. Whether they would or wouldn't make an accidental mistake without this warning is another question. Better be safe than sorry.

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

        I think the question is a good one. It's fine to ask about general things related to Hacker Cup at large.

        We typically want the validation input to prevent any possible misinterpretation of the problem, but we don't usually include a truly maximum case.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

    The scoreboard is realtime, though it doesn't show any summary stats like how many people have submitted for a given problem. You'd have to page through to get a rough estimate.

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

      Thanks! Are there any plans to implement summary stats? Before people start scraping web pages to automate this process and put an unnecessary burden on Facebook Hacker Cup servers.

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

        We're indeed considering adding such a feature, either next year or possibly even this year.

        → Reply
»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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.

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

    The input size was quite small compared to a normal Codeforces problem, it's possible you ran out of stack space or something.

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

    One of the reasons we added zip files this year was to avoid having you handle that relatively unpleasant format. Unfortunately the zip file for C has an issue that we're investigating. Once that's resolved, I do think the zip files are a much cleaner way of handling large input than making contestants generate the input on their own.

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

      What is the issue with the zip file for C? My program crashed on the judge input, and I only found out after the timer ran out that it was because the zip file had an "Unexpected end of data". Until now, I assumed that I didn't pay enough attention when downloading the file, but your comment makes me wonder.

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

      Have you guys resolved this? Would it be possible to set up the encrypted-zip-file format in practice mode so we can test?

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

        We're still working on it. We know what the problem is and when it's fixed we'll be able to be quite confident through our own testing. I appreciate the offer though :D

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

          That sounds good, though I wanted to test my own decryption scripts as much as your system.

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

    Input generation is terrible and it doesn't allow the test data to be as flexible as possible. I couldn't submit C too and I can guarantee with you that the input size is perfectly fine.

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

    Hey, my C also Segfaulted on the real input, and I couldn't fix it in the 6 minutes. It turned out to be a stack usage problem, because when I set my stack to 200 MB with compiler flags, it ran fine.

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

    Lol, you are probably the first person on planet Earth to advocate for compressed input format if there is an option to do it normally

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    vkgainz I have faced the same problem earlier. I solved it by increasing the stack space limit. If you are on ubuntu, the command to increase stack size is ulimit -s desired_space(in KB). For example, if I want to set the stack space to 1GB, I would run ulimit -s 1048576 in the terminal.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    I don't know if you solved your problem since, but my solution was actually crashing on a (slightly overloaded) DFS for the C, because of the stack size. When I switched to a native Linux (as opposed to WSL) and increased the stack size (using ulimit -s unlimited in the shell), there was no problem anymore.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -14 Vote: I do not like it

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?

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

    same even my pc crashed for A1 and B both and now i am out even after solving 2 questions

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

    A common issue was people writing O(N^2) solutions to problem A when O(N) solutions are necessary. You won't be able to run an O(N^2) solution in 6 minutes when N = 800,000.

    → Reply
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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.

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

    where to add , i have submitted the wrong output but then also Edit- i added inside the vs code terminal where flags like c++ , a.out and more like that are given its only taking time and no output is coming and on sublime its giving wrong

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      My cpp code runner (VS code extension) executor map in vscode
      → Reply
»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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.

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

    It is really annoying when purples can't set stack size

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

      How to set up stack size on Windows , Sublime text 3 , MingW compiler ?

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

        Add -Wl,-stack=268435456 to your build file.

        Here's how my C++.sublime-build looks

        { "cmd": ["g++.exe", "-Wl,-stack=268435456", "-std=c++17", "-DLOCAL", "$$${file}", "-o", "$$${file_base_name}.exe"], "shell": true, "working_dir": "$file_path", "selector": "source.cpp", }

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

          The size will be 256 MB ? What if I wanna make it 512 MB ?

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 3   Vote: I like it +11 Vote: I do not like it

            Idk how to increase it further, I've never tried it. The stack size I mentioned is usually good enough.

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

        or just use Linux.

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

          There is limit in Linux as well , u need to use a flag to make it unlimited

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

      Never needed it untill now. Lesson learnt. Will take care from next time onwards.

      Maybe next time on you should try helping people out with it rather than passing sarcastic comments. That is what the community is for I guess :)).

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -22 Vote: I do not like it

        There was already a solution 2 comments above yours.

        Every year, every contest hundreds of people complain to the same issue (that they are unable to read comments).

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

          Yes we all suffer from the same problem don't we ( that people are unable to read comments).

          P.S : You should have read the reply to it.

          → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it +64 Vote: I do not like it

          So, if every year hundreds of people complain (and i guess many others that don't complain publicly) about the same issue, maybe it could be considered to include these common problems in the FAQ? The FAQ already has "What do I need to compete?" as a question and mentions problems "line endings" and "online visibility". This could be expanded with/this could link to an technical FAQ with common problems for common languages/Compilers. Like stacksizes. Pinging LoneFox, are there some discussions in this direction? Or would this clutter the FAQ too much?

          Spoiler
          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            Thanks for the suggestion, we'll definitely consider including such information in the FAQ.

            → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it -25 Vote: I do not like it

          You are wrong , since I was the one replied to your comment , I read the comment above and also searched through old blogs on CF , but for Windows there wasnt a single comment or blog I found describing where to exactly add the flag , they just wrote add that flag .

          → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      It is really annoying when a master doesn't know how to talk in public.

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

    For the sake of completeness I'd like to note that GCC can kind-of auto-grow the stack if you specify the -fsplit-stack compiler flag, — see https://gcc.gnu.org/wiki/SplitStacks There's some overhead involved, of course.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    Same bruhhhhhh but for A1 , from now on i will declare all arrays and matrices in global scope :(

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +18 Vote: I do not like it

      Using vector would solve the problem. As you cant make large arrays in stack memory. So either use dynamic arrays or vectors (in c++) or global arrays. Dynamic allocation stores in heap memory in which you can take big size arrays. If I am wrong please correct me.

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

I believe LoneFox had made problem 1 :)

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +251 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    Does declaring all variables globally solves the problem of stack size?

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

      No

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

      If using global variables reduces the number of recursive function arguments, then this reduces stack usage too. Sometimes this may be enough, but I wouldn't count on it. It's always safer to use gigantic 256M+ stacks with deep recursion.

      → Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

IS this correct ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -78 Vote: I do not like it

    LoneFox Sir, I ran code on Dev-C++ and A1 submitted successfully. But for A2 my code was correct but couldn't figure out how to set stack size in Dev-C++.

    Please give a chance to all those who did the 1st question, if you want I can send my source code for A2 to check my submission.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -79 Vote: I do not like it

      Also LoneFox Sir, if you keep 10 points as criteria for qualifications than we will have 9000 selections out of 12,700 eliminating 3,700.

      And if you keep 24 points we will have around 7000 selections. I think giving a chance to people who didn't knew about stack size but had correct solution for A2 would definitely be a great move.

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

        If you see previous years, then only 2k participants qualify for round2. So, 42 should be kept as qualifying points.

        Anyway, B was much easier than A2 imo.

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

    You can set stack in WSL2 (you cannot in WSL1). Just do ulimit -s unlimited and it's gonna work. That's what I did.

    Also I feel like people should be prepared for this. It happens every single year. Especially if you hit it before.

    I hit it on a Round 3 and failed the B problem, and I knew it was only my fault I didn't prepare to have stack extra command up. So people should complain even less that it's happening on a round that only qualification matters.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -44 Vote: I do not like it

      I was using WSL1 since 2 required more work to install. I forgot since it didn't happen to me last year.

      It should be reminded to participants in the FAQ instead of giving experienced users the unfair advantage. This should not be technicalforces or "I remember having the same issue 2 years ago"forces.

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

        I disagree, preparation for FBHC matters, and this is one of the things you should prepare for: running your solution locally. Similarly how you have a library of pre-implemented things (that's where I store how to increase stack size for different environments).

        Secondly this complain is even less relevant, as I previously mentioned, considering it was on a round that everyone with >= 26 points qualifies. This happened to people on Round 3 (me for example), when actually every point matters.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -35 Vote: I do not like it

          A warning to keep your limbs in the vehicle on an amusement park ride is not replaceable by a trial ride at 10 km/h where you will only get a laceration instead of an amputation

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

    Putting it into FAQ would be surely useful. But the whole situation is really weird. People, who are supposed to be competent programers, happen to be unable to create programs that run correctly on their own computers! A wheelbarrow without a wheel.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -29 Vote: I do not like it

      I don't think most of "competent programmers" can install new tools within 6 minutes, so this doesn't create a contradiction

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

        Did you never test any of your recursive solutions with max constraints edge cases on your own computer when participating in other contests?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it -6 Vote: I do not like it

          I stopped doing that years ago, there's no meaningful algorithmic insight to learn from giant cases. I only do small cases and mental checks.

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

            Isn’t “well, my code doesn’t crash or run incredibly slow” on max test a good enough insight?

            → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    You don't need a stack to solve it.

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

    Just in case you don't want to deal with platform specific issues, there is a way to use allocate a custom stack on the heap, and use that for the duration of the program. I found this code in some comment quite a while back, and it works on Linux at least (it would be great if someone could confirm if it works on other platforms, although I would presume it to work on Windows/MacOS as well).

    To get a 1GB stack
    → Reply
»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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.

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

    ...Or you could generate random maxtests to check wheither your solution processes them reasonably fast and then notice that the answer overflows. That was precisely my case with that problem.

    And, by the way, "always do not forget to test wheither maxtest processing fits in time limit" was my takeaway from another failed round (it's highly possible that was a FHC round).

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

      Thanks for sharing experience:)

      How to generate random maxtests in given input format?

      Can you please provide me any sources...

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

        Here are my solutions for A2 and A3. One can see that both contain testing functions.

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

    There are a couple of ways you can avoid falling into this pit. If you look at lots of solutions from top competitors you'll see that they use a structure called 'Mint', on 'Mod_int', or something similar. The functions +, — etc are then re-defined according to modular definitions. This means you can't 'forget' to take the mod, as it happens automatically.

    My solution contains a similar idea, where I define operations add_, sub_, etc. I've pasted it here for you. I think the first way is probably neater but I developed this myself before I saw that and it works for me.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

Also can be optimised to O(1) space easily

Spoiler
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey could you please explain this?

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

      Oh Thanks for reaching out. This dp[i] denotes the number of hand changes for all subarrays ending with position i. To compute this. if the current character is F we do not need to do any computation as no hand changes will be there on reaching to i from i — 1. remember dp[i-1] already have answer to all the subarrays ending with poistion i — 1. so in case current character is 'F' dp[i] = dp[ i — 1]. else if current character is 'X' and last non 'F' character is also 'X' then also we need not compute anything as dp[i — 1] already contains the moves.

      if current character is 'X' but the last non 'F' character is 'O' then for all subarrays which ended at last 'O' WE need to change the hand once thus adding the answer as index of 'O' which represents number of subarrays ending with 'O'.

      → Reply
»
3 years ago, # |
  Vote: I like it +60 Vote: I do not like it

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.

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

    I had no idea what top trees are and decided to look them up. According to Google, Penn State is very concerned about the dangerous environmental impact of a data structure this OP becoming common knowledge:

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

    ecnerwala Do you know of any tutorial for top tree?

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

      There might be one in Chinese, but probably not, because they're very overkill/advanced and are essentially never necessary. HLD will essentially always suffice. If you really want to learn top tree, learn Link-Cut Tree first; top tree is a (conceptually) straightforward extension. This paper describes the standard splay-tree-based implementation: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9754&rep=rep1&type=pdf

      I might write a tutorial someday, but no promises on that. If I do, it'll still assume HLD knowledge beforehand, so focus on that at most.

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

    I fail to come up with the way to lazily propagate push to all nodes of a connected component in HLD. Usually what I would do is to just increase all values in a subtree, which is expressed as range addition. Can you provide some insight on that, please?

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

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

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

My proposed time/space complexity (if you can call >1GB worth of stack use 'efficient', kappa)
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The official solutions suggested a traditional sort of the edges to seed the DSU at the beginning. O(N log N) -- Radix sort could have been used to get that down to N*maxC as well, but they didn't mention that.

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

      The whole first paragraph in the solution is unnecessary. We can just compute that while we're computing $$$D_{i, j}$$$ anyway.

      → Reply
»
3 years ago, # |
  Vote: I like it -40 Vote: I do not like it

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.

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

    We're pretty confident that the judge data is correct. Not only do we have multiple independently-discovered judge solutions which have the same output, but we agree with lots of LGMs who participated in the contest, some using completely different approaches to any of the judge solutions too.

    If you disagree with the judge data on a case, please double check your solution first.

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

      yes it was my fault i used value >1000 in problem B which wasn't allowed. sorry for any inconvenience caused.

      → Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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!

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

    I don't know the exact reason but I want to share how I resolved this issue.

    You can see the template in any of my codes and notice that I use functions to input and output variables. For example, to output, the code is like this

    inline void op() { cout << '\n'; }
template <typename T, typename... Types> inline void op(T var1, Types... var2) {
    cout << var1 << ' ';
    op(var2...);
}

    So what it does is that while outputting the last variable, it outputs like variable_value + space + '\n'. In codeforces and many other sites, this rarely gives me a problem(It only hampers me sometimes in very old questions as I think new checkers trim the white spaces or something, IDK), but sometimes it does WA's my code just due to this.

    So I just changed it to normal cout<<variable<<'\n' and it got accepted!

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

    Okay, it's resolved, who would have thought that the final input of the problems gets changed!. During the contest, the final input files had different inputs and the final input files for practice submits are different!

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

      Yup, once the contest is over we use the full input file in practice mode, which is a bit bigger than the files you receive during the contest.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply