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

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

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

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

You're eligible to compete in Round 2 if you scored at least 24 points in Round 1.

The top 2000 competitors who solve at least one problem in this round will receive a Facebook Hacker Cup t-shirt! We'll begin shipping out t-shirts by early 2022 or earlier, at which point the winners will receive emails with tracking information.

Furthermore, the top 500 competitors will advance to Round 3, taking place on Oct. 9th. Please note that all submission judgments will only be revealed after the round end, and that time penalty will be used to break score ties. 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!

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

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

See you on the scoreboard! Good luck, have fun, and go win a tshirt!

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

    When will the solutions to some of the Hacker Cup editions be made available e.g. 2011? It would be great if they could be added to the solutions tab just like solutions are posted this year.

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

    Speaking of the scoreboard, we just added the ability to filter contestants on the scoreboard by country and/or by a user's name! If you'd like, you can set the country you wish to represent in your coding competitions profile.

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

      Hey SecondThread, Could you also add the ability to navigate to any page in score board (page number feature)

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

      The country filter is really nice! However, I think selecting a country should reset the page to the first one. Otherwise, you can occasionally encounter the bug where the number of pages for the filtered country is less than your current page.

      Also, one feature I'd like to request is the problem statistics (how many solved/tried a problem).

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

        Good idea! I'll add it to the list of things to work on after we have finished up round 3! :P

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

Will there be a 6minute submission timer here too? And only 1 submission rule?

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

Hi, I am not able to update my competition profile. Whenever I click on the "Save" button, it shows a message — "Error performing query". Can you help?

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

Can someone tell how to increase stack size in Sublime Text-Windows

I tried by this comment but not able to do it correctly .. https://codeforces.com/blog/entry/94726?#comment-838535

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

    If you have an existing build, head over to

    C:\Users\username_other_than_public_and_default\AppData\Roaming\Sublime Text 3\Packages\User

    This is my build, you can paste it and change to whichever version of C++ you prefer:

    { "cmd": ["g++.exe","-Wl,-stack=268435456","-std=c++17", "$$${file}&quot;, &quot;-o&quot;, &quot;$$${file_base_name}.exe", "&&" , "${file_base_name}.exe<inputf.in>outputf.in"], "shell":true, "working_dir":"$file_path", "selector":"source.cpp" }

    If you want to make a new build, Tools -> Build System -> New Build System (last option)

    Paste the above build and follow the same process and save. Next time you build, you have to manually choose the new build, and then onwards Ctrl+B should work.

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

      I created new build file and pasted your build. It is showing the error: g++.exe: error: : No such file or directory

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

        Maybe your input file and output file are not named as inputf.in and outputf.in as mentioned in the build

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

          semicolonised Sorry to bother you during the contest but I tried your build and changed input names too but still it show no directory found

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

            Here is the site from where I set up my sublime text, the build is also given, I just added the stack manually. Sorry for any inconvenience caused!

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

      Sad, I should have googled this trick earlier in the contest and would not have wasted 1.5hours debugging B trying to figure out what's wrong. In the end I changed my code from recursive to iterative out of desperation and AC. But, because of that, I did not have time to do C....

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

      I wish I had given enough attention to this after round 1. Will never forget this in life :))

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

Why my input file had some stupid gibberish. I was not able to compile it.

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

It takes quite a bit of time to download the input, and i think my internet isnt slow.

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

Looking forward to when FHC actually employs the standard CF/CC/AC rules

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

    Same thing happened with me man, notepad crashed when I tried opening the input file, as a result I wasn't able to submit. What nonsense is this.

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

      See my comment here: https://codeforces.com/blog/entry/95264#comment-843301

      Edit: Actually, this sounds like you may have just tried to open a large file, which is also something Notepad is really bad at.

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

        Same. I was able to open large file using WordPad. But was not able to copy it.

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

          Why trying to copy it? You can read from the file instead.

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

            Yeah I did this but it was too late. I always wait for 1 min and still 5 min remains. Today even 6 mins wasnot enough for WordPad to copy file.

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

        I later tried using Sublime Text to open the input file, the file opened, but I was unable to copy the input, selecting all the text took a really long time and Sublime Text became unresponsive. Thank you for clarifying though, my bad for not seeing the FAQs properly initially. Apologies if my message sounded too harsh.

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

          Yeah! The point is to use file i/o or input output redirection(using either Get-Content or redirection symbols ">" and "<") and not copy paste the whole input. It is bound to crash. The only case for opening the input file is to have a look at the testcases.

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

            Ahh I see, I'm actually not at all familiar with input output redirection, so I didn't really understand what you said :P

            But yeah I appreciate you explaining your method. I can see in your above comment that you've used some Git bash commands, I'll try and learn this if possible. Thanks a lot.

»
3 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Can anyone help me with the stack overflow error...I am unable to pass even the validation test case for problem B.

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

3rd time failed Facebook Hacker Cup(being able to solve problem).

2018: stack overflow in round 2

2020: started too late and didt pass to round 2

2021: can't copy 46mb file OMG

2022: stackoverflow because 1.5Gb isnt enough

2023: can't download input because my HDD has no 200Mb free space

»
3 года назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

Well, it was another Facebook InfiniteStack FastInternet HugeFiles Cup for me xD. Why the f**k did i wake up at 02:00 a.m. xD)))

»
3 года назад, # |
  Проголосовать: нравится -76 Проголосовать: не нравится

What a shitty contest it is! So, many issues with downloading input and submitting soln files. Moreover , the problem statement for A is also not clear. Total waste of time!

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

    Sounds like your problem, not the contest's. I found the questions to be enjoyable and the process went very smoothly. I am quite sure this is the case for many others as well.

»
3 года назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

this is a smurf account, but really had a bad experience with the stack thing even after figuring out soln in just 25 mins — 30 mins for B

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

The tasks were very pretty, and the contest was so educational. For example, I discovered that my stack size is 8 Mb) And also discovered how to increase it =). (Spoiler: pragmas didn't work). By the way, it is sad that there are so few only-output type contests, because I really like this format(.

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

Wrote solution for C1, submitted, passed pretests, made final submission.

Realised bug 5 minutes later while implementing C2. Compared fixed code with old code and output was greater by one in exactly one test case.

As expected, I FSTed in exactly that test case by 1. Took my rank from less than 150 to greater than 800. RIP.

(PS: I really, really don't like this format of checking. Too many ways to mess up from extracting to piping input file to stack overflows to whatnot, and the 6-minute-to-death timer for imposing this weird format)

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

Did anyone else used $$$O(S \cdot \min(n,m))$$$ approach for $$$C2$$$ :)

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

Just here to commiserate with everyone else that couldn't figure out how to increase Mac OS stack size above 10 MB :(

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

    +1.

    Does anyone have a working solution for increasing stack size on macOS?

    I didn't find any useful result on basic googling.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      -Wl,-stack_size=0x10000000
      

      to your compile line

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

      https://codeforces.com/blog/entry/94726?#comment-839042

      #include <bits/stdc++.h>
      using namespace std;
      void main_() {
          int n;
          cin >> n;
          cout << n << '\n';
      }
      static void run_with_stack_size(void (*func)(void), size_t stsize) {
          char *stack, *send;
          stack = (char *)malloc(stsize);
          send = stack + stsize - 16;
          send = (char *)((uintptr_t)send / 16 * 16);
          asm volatile(
              "mov %%rsp, (%0)\n"
              "mov %0, %%rsp\n"
              :
              : "r"(send));
          func();
          asm volatile("mov (%0), %%rsp\n" : : "r"(send));
          free(stack);
      }
      int main() {
          run_with_stack_size(main_, 1024 * 1024 * 1024);
          return 0;
      }
      
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I use this flag on my macOS. I increased it to 512MB just to be safe.

      -Wl,-stack_size -Wl,0x20000000

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

Imagine having AC code for the second problem but you can't submit because you have a stack size error in the last minute.

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

    I also had similar issue with problem B.I converted the recursive soln to non recursive using two stacks(postorder traversal) but sadly after 14 mins contest ending.

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

      I am new to C++. I was getting segmentation fault with recursive dfs. But I realised it after the contest that recursive function may use a lot of memory. Then wrote bfs using queue and I didn't get any segmentation fault... It's so sad :(

»
3 года назад, # |
  Проголосовать: нравится -39 Проголосовать: не нравится

Can FHC consider changing the contest so that tests are run on a FB test server instead of on the contestant's computer? (Or have a validation input which can trigger max-stack-size issues?) Ran into stack size issues on B and my solution was fully correct (submitted for practice shortly after the contest ended).

Based on how many "Submission timer expired" I see on B, it looks like this was a very common problem: https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-2/scoreboard?start=1350

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

I am very sure that my solution to Problem B was correct But my system doesn't allow that much memory which was required for test cases. (nlogn memory).

I tried a lot to somehow manage it but can't overcome the issue.

At least you can warn about it in this blog post .

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

Test in D were weak, greedy (wrong) solution that fails on my tests and bruteforce for small inputs passes. Maybe it was impossible to create good tests for such problem.

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

    It's very hard to create tough data, but I suppose how likely it is to break the greedy depends on the greedy. Also, if you shuffle the input before hand that makes it even harder for us to make you fail.

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

When I saw B I remembered the threads from the previous round of people complaining they couldn't figure out how to make the stack bigger in 6 minutes. (Since the stack breaking tests were in the BIG test). I was thinking people will complain again about this and was mildly amused.

Then to my surprise I see that there's actually a line test in the validation, how nice of the authors to do that, that will make people stop complaining.

Then to my ultimate surprise I come in the CF thread, and still see people complaining about the stack.

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

    You'd be surprised how many people we had submit clarification requests saying things like "Why did you make validation data so big for problem B??? It doesn't run on my computer!" lol

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

      do you know how to increase stack size for java? I have 8gb heap space in intellij still got stackoverflow.

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

        I use this thing called stack trick. You can change your main method to a different method like M(), and then this in your new main method (which just wraps your old one):

        Thread t=new Thread(null, null, "", 1<<28) {
          public void run() {
            M();
          }
        };
        t.start();
        t.join(); //you're going to need to mark your main method as "throws SomeException", I forget the name of the exception exactly, your IDE will tell you
        
»
3 года назад, # |
Rev. 2   Проголосовать: нравится -27 Проголосовать: не нравится

Yo someone please tell me there's a clean way of doing C2 or else somebody ought to be fired from problemsetting.

My idea: you first shift up or down some number of times, then perform single remove operations on what's left on row $$$k$$$ (so same idea as C1). Let's assume we only shift up for now (down is analogous). I precompute the cost of each shift. The thing is, when shifting, in certain columns you might no longer be able to shift because there's too many cars and no room to keep pushing. Thus, for each column I compute the number of shifts after that column gets stuck and you can't shift it anymore. After a column gets stuck, the state of the $$$k$$$ th row will no longer change.

When we introduce spells, changing one cell only affects that column. Specifically, the number of shifts at which the column gets stuck could move up or down. So we use sets to find that, and range update operations on a segment tree to change the cost values.

Thing is, this is way easier said than done because there are quite a few cases to consider, and my implementation ended up being disgusting. Here's the code, don't even bother trying to understand it lol: https://ideone.com/iv4U5d

EDIT: Ok there are definitely cleaner ways of implementing C2. I still can't say I like the problem, but I'll cool off on it.

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

    We don't need to shift more than min(R, C).

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

    Yeah I also was trying to code that solution, mine was a bit cleaner but also didn't manage to finish it in time. I was using M fenwick trees to calculate blockage, and then one interval tree to compute best rotation.

    One way you can cut your code in half is just write code for downward, then reverse all column in M, and compute again but for K = N — K + 1.

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

      Ah that's a good point, I was in a rush in contest and just copy pasted the whole thing again.

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

    My implementation. There are a few cases, but in general I think it's pretty clean.

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

    Looks like we had very similar implementations, down to the quirk of using both a segment tree and a Fenwick tree :P

    Couldn't complete this mess up in time though :(

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

    I think there's a pretty clean way, plz don't fire me :)

    There are only a few squares in a column that might change. In particular the first +/-5 things in a column and the last H-K +/-5 things in the column. Sure, you can case all of that out, but that sounds annoying. Instead, why not just remove all of their contribution to the answer, add the new space in, and then add their new contributions back in?

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

    Lol you only shift up or down at most $$$O(min(n, m))$$$ times, so you can replace segment trees with for loops and array

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

    Others already mentioned the $$$min(N, M)$$$ observation, which makes everything much easier.

    But I didn't have it, and my code (with the approach very similar to yours) looks manageable: link.

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

    What are the cases to consider? What I did was: For each column we count cars, from top to bottom. The moment we got at least $$$k$$$ cars, we fill the remaining places downwards with virtual cars. I also add an additional row at the end with no cars, it will only virtual cars (this removes the case if we push cars as much as possible). Now I check all rows $$$k$$$ to $$$r+1$$$ for the sum of cars/virtual cars they have plus the distance to row $$$k$$$. The minimum sum is the answer.

    Here is my implementation: https://pastebin.com/QJSdbs87

    The main logic happens in Lines 353-374, which is pretty short. I think this has a very small amount of case work here.

    For the other push direction I just turn the parkings around and repeat everything (Line 332-341).

    For the spells I use segment trees. A Minimum-Tree to find the answer, and $$$c$$$ trees with range updates but only point queries, to manage the virtual cars. (line 391-404 and line 408, 409)

    I didn't use $$$min(R,C)$$$ as the minimum amount of operations needed.

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

Huge congrats to Radewoosh for clinching Round 3 fourteen seconds before the end of the contest!

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

Seems there are a lot of possible solutions for B.

Mine is to just count the number of bridges on the tree but add a long cycle for each of the same frequencies, which I found very interesting.

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

    I tried the same thing but didn't have enough stack size for the main tests :(

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

    You can also count complete subtrees(ones where any node $$$n$$$ with a distinct color contained in the subtree, $$$n$$$ is also present in the subtree) then combine the sums from children with small-to-large merging.

    Similar problem: Link

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

    My Solution: Get LCA of all nodes v having same frequency. for ewach v,LCA pair do sum[LCA]++ and sum[v]--. This will activate edges between v,LCA

    Do simple dfs by adding sum[i] to curr at each point and when cur = 0 increment ans. O(NLogn) time, O(NLogn) space

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

    Yeah I did something similar. I constructed a graph with the following bidirectional edges :

    A. Real edges given in the input

    B. Edges from vertex i to i+N

    C. Edges from vertex i+N to j+N iff i and j have the same frequency.

    Now if a1,a2,a3..ak have the same frequency, only connect a1-a2,a2-a3... So that there are O(N) edges of type C. Aka construct trees of same frequency.

    Now just find the bridges of the graph in O(N+M), [M = O(N) here] and only add the bridges which are real edges to our answer.

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

    My approach (couldn't finish in time though) For each frequency, calculate the first and last discovery time of any node having that frequency and also the in_time and out_time for each node. Now for each node excluding the root, the condition for the edge between the node and it's parent to be removable is that there should be no frequency for which the interval [first_discovery,last_discovery] intersects with the interval [in_time,out_time]. This can be achieved using 2 segment trees and binary search.

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

      You can actually check if there are any intersections without segment trees and binary search.

      Let's observe that for each node U the edge between U and its parent being removeable only depends on the frequencies that occur at least once in the subtree of U. We're not able to remove the edge if there exists any frequency F in the subtree of U such that first_occurrence[F] < in[u] or/and last_occurrence[F] > out[u] , So all we really care about is minimum of first occurrences and maximum of last occurrences of all frequencies in the subtree.

      This can be done pretty easily in O(n). you can check the code here.

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

    Let $$$S_x$$$ be the set of all vertices $$$u$$$ such that $$$F_u = x$$$. We want to add a path from each element of $$$S_x$$$ to the LCA of the set. Just compute the LCA and for each $$$u$$$ in $$$S_x$$$ go upwards connecting $$$u$$$ with each element you find using DSU, stop when they are in the same component. To guarantee it will work you need to eval $$$S_x$$$ with lower LCA depth first.

»
3 года назад, # |
  Проголосовать: нравится -85 Проголосовать: не нравится

why hackercup can't follow similar format like google codejam ? why this 6 — min timer and output file upload shit ?

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

    Why GCJ can't give us a multiple-choice test with a/b/c/d answers instead of this coding shit?

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

TFW you attempt to solve C2 by writing code for the case where you shift cars up, then flip the board and run it again, but you forget to flip the updates too :(

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

Well, that was fun, thanks! :) Adrenaline. I guess Radewoosh has the same emotions :)

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

Screencast https://youtu.be/nGCeL0y2T1Y

Here's my heuristic solution for D. (passed 5 minutes after the contest end)

I want to focus on two types of elements. The first type is those that are not divisible by a number that is a divisor of many elements. The second type are elements that are far away from other elements (like 500 in a sequence 1, 2, 3, 500, 1000, 1001, 1002).

I put aside top elements of those two types. Greedily assign all the remaining elements. Then run knapsack on those few special ones.

how many special elements?

Anybody sees a way to break this solution?

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

D: If we have a set of $$$K$$$ numbers such that max number is $$$M$$$, and $$$2^K > K*M $$$ then we can choose two non-empty subsets with the same sum (pigenhole principle, pigeons <- subsets, holes <- sums).

For M=200000, K=23 works.

If N is small do bruteforce, if N >=25 it is always possible.
Use the following schema again and again:
1. take 23 smallest or random (both seems to work) untaken numbers
2. start generating subsets and computing their sum (stop when you detect two with equal sum).

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

    Why does it work fast enough though?

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

      My intuition is the bday paradox. Usually you will need around 10 elements or less to find some subsets with equal sum. So this will be around 1024n ops.

      You can have a stress test for small set of numbers like 1,2,4,...,2**17 but good luck finding one with 200k numbers.

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

These problems are good, but I just blow it in this round.

Problem A is my nightmare, I tried to implement it by DP, but failed from time to time. I then jumped to problem B, but cannot find any hint.

After one hour and half, I found I can use greedy in problem A, then I move back to A. However, there are two bugs and miswriting in my code and it spend another hour to correct it.

I submit the answer 2 hours 30 minutes, and I move on to problem B, but still cannot find any hint. Finally, I find problem C1 are much easier, so I jump to problem C1 in last 20 minutes. I thought I must do it before the end of the contest, so typed very fast, and made many silly mistakes.

When I correct all of the mistakes and try to download the full input, the contest has ended 5 minutes ago, and my final ranking is 2700+, a result that cannot even win a T-shirt. My answer just get accepted in the practice mode. I cried at last, very very sadly.

I really cannot accept my current result, I am too nervous, and I think I can do better. In order to prepare for this contest, I practice nearly every past round 2, and can pass most of them.

The most reason I failed in this contest is that I was too eager to win, since Facebook is my dream company and I want to behave well in the contest to get an interview. I am about to graduate this year and looking for jobs afterwards. That is my main reason. If I just do for fun, I can behave much better.

Afterwards, I need to move on, and delete my hacker cup experience in my resume. Thanks for this contest, I find so much to improve.

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

    Facebook is my dream company and I want to behave well in the contest to get an interview.

    I don't want to rub in your feeling but how well does one need to perform to get an interview? I'm still assuming that these results don't matter much unless you get all the way to the onsite finals.

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

      Last year, all T-shirt winners received an invitation in the T-shirt email to submit a resume/request more information on jobs at Facebook. I don't recall receiving any additional recruiting-related communication as a finalist (though I could be mistaken), but obviously, I can't say with any certainty whether finalists were prioritized for interviews/opportunities at Facebook in general.

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

    Cheer up! You don't need to be top 1000 or get into round 3 to get into Facebook. The correlation between interview result and codeforces rating is not linear and tends to be less as your rating rises

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

during this round i dowloaded input file to submit problem A but it contains wrong words not test cases and my time is expired, but after the round ended i download this input again but it contains correct format of test cases ,why this happened to me ??

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

I don't like the statements. I hope they will be shorter in further rounds.

A is unnatural and difficult to understand.
B is very long. In particular, why do you need this paragraph in the middle?

Mining is a ...

I would appreciate the diff between C1 and C2.
Finally, D is such a cute problem that you could describe in one paragraph... and you butchered it with an unrelated story. Making a nickname-related pun isn't cool if the original problem had nothing to do with it.

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

In the solution section of C1. There is a sentence "It cannot be better to combine both upward and downward shifts, nor to perform car removals before the desired shifts are done.". I think to combine upward and downward is possible to be better. For example

*X*X*X*X*X*X*X*X*X*X*X

X*X*X*X*X*X*X*X*X*X*X* // this is the k'th row

XXXXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXXXX **********************

We need to free up the second row

In this case one upward and 2 downward is the better solution. What do you think?

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

Thanks to authors for the contest!

Plus, thanks for maintaining a non-mainstream format, and working to improve it on top of that, like validation and pre-downloading large inputs.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится
  • Don't know if I should be sad that I couldn't advance to Round 3 (because I spent more time double-checking my solutions for silly mistakes than actually solving problems)
  • Or if I should be happy that I won a Hackercup T-shirt (because I spent more time double-checking my solutions for silly mistakes than actually solving problems).

 

Or alternatively:
»
3 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Just a small suggestion: Show the number of test cases in input files so that I don't have to open large input files just to ensure that my code runs on all the test cases.

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

EDIT: Fixed, turns out the input is randomized each time

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

So happy to get a T-shirt in hacker cup. It's my dream since I started to learn CP last year. (^ω^)

»
3 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Those with ranks 501 and 2001 would be so happy.

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

@Facebook Hackercup admins please disqualify the people who have not written a single line of code in their source code and just submitted the output file in both source code and output files. Like the person now ranked 1490 has not written a single code in his source code. Pls look into this matter and disqualify these type of people.

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

My rank with 10 mins left was 1900 something and seeing the rate at which it was increasing I was worried ill miss the cut by just a bit, with this motivation I debugged my C1 superfast and submitted it with 5 mins left on the clock. Felt extremely happy to see both passed and even more that I've won the T-shirt with a final rank of 1405 !!

Also, when will the T-shirts be shipped, I am too excited to wear it!

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

I solved problem B in a different way: Do an Euler tour (single occurring). Now your aim is to just count the number of such nodes whose subtree contains all the occurrences of a certain value,i.e., no value should be there which is in the subtree and outside that subtree as well. Subtree denotes a subarray of the flattened tree. Hence, you will have n ranges to query for and for that you can apply Mo's Algorithm to compute the final count of such nodes.
Time Complexity : n3/2
Code : https://ideone.com/hlTvaM

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

    That's a cool idea!

    In your code: you can also do updates of "moving L, R boundaries of [L, R] interval by +/-1 and maintaining array tot and variable cur" (using your notation) with this helper function:

    void update(const int what, const int delta, int& cur, const vector<int>& cnt, vector<int>& tot)
    {
    	cur-=(tot[what]!=cnt[what] && tot[what]!=0);
    	tot[what]+=delta;
    	cur+=(tot[what]!=cnt[what] && tot[what]!=0);
    }
    

    and using it by calling update(what is a[freq[EITHER L OR R]], delta is EITHER +1 OR -1, curr, cnt, tot);

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

I did something for B that i havent seen and i think it was a cool solution

Basically i used DSU on trees, so for each node i had the number of times each frequencie appears in its subtree, and i also had two more values: how many different frequencies the subtree has and for how many frequencies of that subtree the number of times it appears in the subtree equals the numbers of times it appears in total, finally to delete an edge coming to the current node from its parent you need these two values to be equal, because it means you are not separating any two nodes with same frequencie.

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

Does anyone receive an email from [hackercup2021-33527 at eventsatfacebook.com] about job opportunities? It requires me to login into a strange website so I don't know if the email is legitimate or not.

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

wrote about my experience in hacker cup 2021 in this medium blog article: https://shadek07.medium.com/facebook-hacker-cup-2021-experience-519f594bec7e

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

What will be the inscription on the t-shirts? "Facebook Hacker Cup" or "Meta Hacker Cup"?