LoneFox's blog

By LoneFox, history, 3 years ago, In English

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!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +146 Vote: I do not like it

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

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

    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 years ago, # ^ |
      Vote: I like it +102 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

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

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

        You can do it changing URL query.

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

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

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

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

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

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

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

    That's right, the contest format will be the same as for past rounds.

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

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We apologize for the issue, it should have since been fixed.

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

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.net/blog/entry/94726?#comment-838535

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

    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 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

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

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

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

          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 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

»
3 years ago, # |
Rev. 9   Vote: I like it -49 Vote: I do not like it

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

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

    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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      See my comment here: https://codeforces.net/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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

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

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

            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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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

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

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 years ago, # |
  Vote: I like it -42 Vote: I do not like it

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 years ago, # |
  Vote: I like it -76 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +79 Vote: I do not like it

    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 years ago, # |
  Vote: I like it -30 Vote: I do not like it

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 years ago, # |
  Vote: I like it +69 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

    lol

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

    I agree; this format is very fun! This is the first contest I've done where it doesn't put me at a disadvantage to use Java.

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

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 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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

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

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

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

    +1.

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

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      -Wl,-stack_size=0x10000000
      

      to your compile line

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

      https://codeforces.net/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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      -Wl,-stack_size -Wl,0x20000000

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

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
  Vote: I like it -39 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +108 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +112 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

        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 years ago, # |
Rev. 2   Vote: I like it -27 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

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

      Agreed, although that's the change of one constant in my code.

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

        So just do brute force, only need to consider rows [k — min(R, C), k + min(R, C)] and maintain fenwick tree is enough.

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

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

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

    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 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +116 Vote: I do not like it

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

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

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    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 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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 years ago, # |
  Vote: I like it -85 Vote: I do not like it

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

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

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

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

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 years ago, # |
  Vote: I like it +53 Vote: I do not like it

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

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

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 years ago, # |
Rev. 4   Vote: I like it +18 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why does it work fast enough though?

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

      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 years ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +197 Vote: I do not like it

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 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Two downwards alone is better than one upward and two downwards I think

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

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 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it
  • 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 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    The top 200 competitors from Round 3 will have a "Top 200" badge on their shirt.

    It matters a little then?

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

      Oh you're right. My point still stands for those who ranked top 201~500 though lol

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

        It's in round 3. So everyone (even 201-500) get a chance at a better tshirt

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

      Last year, there is no "top 200" in my "top 200" T-shirt.

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

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 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

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

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

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

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Those with ranks 501 and 2001 would be so happy.

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

@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 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

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

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

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.

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

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.

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

    That email is indeed legitimate, thanks for checking!

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

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

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

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