Блог пользователя LoneFox

Автор LoneFox, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +131
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +123 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Can you please tell the scoring distribution

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

24 points out of 100?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

24 points in 24 hrs!

Nice :)

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +45 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      5 лет назад, скрыть # ^ |
      Rev. 2  
      Проголосовать: нравится -189 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +64 Проголосовать: не нравится

        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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +26 Проголосовать: не нравится

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.

»
5 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится -14 Проголосовать: не нравится

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?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +22 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      5 лет назад, скрыть # ^ |
      Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится
      My cpp code runner (VS code extension) executor map in vscode
»
5 лет назад, скрыть # |
 
Проголосовать: нравится -15 Проголосовать: не нравится

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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

I believe LoneFox had made problem 1 :)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +251 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

IS this correct ?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится -78 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, скрыть # ^ |
       
      Проголосовать: нравится -79 Проголосовать: не нравится

      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.

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +22 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, скрыть # ^ |
       
      Проголосовать: нравится -44 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +11 Проголосовать: не нравится

        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.

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +22 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится -16 Проголосовать: не нравится

    You don't need a stack to solve it.

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +36 Проголосовать: не нравится

    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
»
5 лет назад, скрыть # |
 
Проголосовать: нравится -13 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
5 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится +5 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

Also can be optimised to O(1) space easily

Spoiler
  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    hey could you please explain this?

    • »
      »
      »
      5 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +60 Проголосовать: не нравится

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.

»
5 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится -8 Проголосовать: не нравится

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)
»
5 лет назад, скрыть # |
 
Проголосовать: нравится -40 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +22 Проголосовать: не нравится

    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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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!

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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!

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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!

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

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.