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

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

Round 3 of the 2019 Facebook Hacker Cup is less than 48 hours away!

The round will begin on July 27th, 2019 at 10am PDT and will last for 3 hours. You can check the start time in your local timezone here.

The contest will be available here shortly before the round begins.

You're eligible to compete in Round 3 if you were among the top 200 contestants in Round 2.

The top 25 contestants will advance to the Final Round, which will take place on October 24th-26th onsite at Facebook's offices in Dublin, Ireland! Please note that all submission judgments will only be revealed after the round ends, and that time penalty will be used to break score ties. More details about rules and other information can be found here.

Good luck!

The corresponding Facebook post can be found here.

Update: The round has ended, and solutions have been posted here. Thanks for participating!

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

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

Reminder!

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

It is sad to solved all the problems yet still missed the top 25 :'(

(can Facebook be kind enough to invite all the fullscorers instead? :))

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

    I'm in the same position, but I think it is totally fair. Usually, the best strategy in FBHC elimination rounds is to aim for as many problem points as possible without paying much attention to the penalty time. This causes people to use "slow" strategies — implementing stress-tests before submitting, coding slowly and carefully, etc.

    This time was unusual — for non-top-grade participants, in order to advance, they had to optimize the time, choosing problem order correctly and taking risks by saving time on stress tests. Having such strategic diversity adds fun to the competition IMO.

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

      Yes it looks like a very strategic round. Unless you are extremely fast and even your "slow" strategy is fast enough, in order to advance, you somehow need to notice that the round is unusually easy (preferably in the beginning of the contest) and switch the strategy.

      My question to advancers — when and how did you notice that?

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

        I slept about 5 hours the night before due to the translation session, then spent 5 hours manually verifying each submit on Scissors and Tape to make sure our checker is correct. I had a cold and a fever and wanted to go to sleep soon. I even considered not competing at all. So I didn't really think about strategy and just solved things.

        When I found out I am third after ABC, I concluded I have a decent chance of advancing and solved D properly with brute force solutions and stresstesting. This almost costed me advancing, as I mistakenly used the $$$O(n^3)$$$ brute force to solve the test input. After three minutes I noticed it and just changed brute() to smart() and called it a day.

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

        B was trivial, and A / C is really hard to write any brute forces. How did you implement the stress tests?

        I wrote the brute force for D and tested against a single $$$n = 1000$$$ test case, which took almost no time. I don't claim that implementing $$$O(n^3)$$$ is trivial, but you can just directly translate that code into $$$O(n\log n)$$$. For problems like D, it's helpful to implement brute force even if you have complete feedback.

        And not optimizing speed sounds really bold to me. Respected coders like you can only do that. I believe the majority of participants go to FHC/GCJ/etc because they just solved problems fast. Even if you want to only focus on problem points, you should solve problems fast enough, because contest time is only 3 hours. Isn't it?

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

        After solving A and B quickly, I thought that I'm able to solve everything and that likely it will be required to advance. I'm replying to ko_osaga below.

        There are a lot of factors you need to consider in order to smartly choose whether and when to spend a minute or five minutes checking your solution.

        It's easy to check N=1, sometimes also easy to check running time for max N. You can use a lot of asserts that might help you when running your solution on a downloaded input file. Spending an extra minute in A will increase your total penalty time more than doing the same for C or D so you shouldn't test A (or B) too much.

        Use the time after submitting. Check if your solution doesn't print any stupid values (negative or infinity), run with sanitizers to check for overflows or RTE. Read the code one more time. Some of my friends don't open the next problem before the timer runs out. This is too extreme IMO but still not that stupid for someone on high-red level.

        For A (light show / lasers) in this contest, even if it was trivial to implement some exponential brute force, I wouldn't do it. One reason is explained above, the other is that the problem looked very hard otherwise (if my simple dp idea didn't work) so I wouldn't solve it anyway — so why waste time for testing?

        It made sense to test B but also sample test looked strong enough. I just made sure that my sample output is correct as there were multiple valid solutions you can print.

        In C, my friends later told me a nice idea. If your solution computes some probability for different possible events, their sum should be equal to $$$1$$$ — make an assert for that. I didn't do that but before starting timer I noticed that the sample test doesn't have $$$A = B$$$ cases so I ran my solution with line $$$A = B = 1$$$ and $$$A = B = n$$$, both should give my all answers $$$0$$$.

        After coming up with an idea for D, I wasn't sure about the correctness so I started with a brute force. It didn't work, I drew and analyzed one of test cases, came up with a fix, got it working for sample tests. Then implemented the fast version, spent a few minutes implementing random generator ($$$par[i] = rand(1, i - 1)$$$ and permutate vertices), tested the two solutions on random tests. Actually, with nice time on ABC it was optimal for me to test my solution for half an hour more before submitting. So I should have implemented something exponential because ofc. my testing didn't check if my idea is correct at all. And I should have created various max tests to see if my solution isn't quadratic. But well, I was busy that day and wanted to get back to something else.

        All that being said, I used to use a completely different strategy and I still think it makes sense for people that are not likely to advance. Just take a huge risk. Assume that your idea is correct, don't implement any brute force, submit immediately after passing samples. Actually, I still use some of this in onsite finals to fight for the first place. And I will use it in TCO R4 because I'm below top8 level.

        One final thought: IMO, people suck in qualification rounds compared to regular CF/ATC/TC rounds. Maybe a single best piece of advice is: just solve problems and don't think about the competition too much.

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

          Not sure which part you are trying to reply, but that's a nice afterword anyway.

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

      Hey, What do u mean by saying " implementing stress-tests before submitting"?

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

        That's a typical practice on such contests. After your solution is finished and works on samples, you implement some easy-to-code but slow approach and test it against the main solution on random tests. And only then you actually submit your solution.

        The downside is time lost on this, that's why on contests like ICPC it is rare to do stress-tests before submitting. But on FBHC there is only one attempt, and the cost of mistake is high, so many people actually do it. Of course sometimes there are rounds like the one in question, where time penalty turns out more important than usual, and people without stress-tests (and without mistakes) have advantage.

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

Where’s the joy?

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

Funny that the hardest problem among all the rounds this year was in the qualification round.

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

    That's actually true xD

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

    This round felt somewhat "standard", especially B was probably used somewhere. However, I found A quite nice.

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

    I definitely over-thought D, and I suspect it's because I just assumed it would be harder. I was trying to do it fully online i.e. bribing one person at a time with no knowledge of the future bribes. I think it can be done in $$$O(n\log n \log n)$$$, but it was getting very messy before I realised I could simplify things a lot with preprocessing.

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

      My solution to D is online and $$$\mathcal{O}(n \log n)$$$. The main idea is to keep track for every node which of a few states it is in: no nodes in its subtree are bribed; one of its child subtrees contains a bribed node; or 2+ of its child subtrees contain bribed nodes. (Note that once we actually bribe the node itself, this supersedes the other states.)

      Tracking these states allows us to do a total of $$$\mathcal{O}(n)$$$ seg tree updates to solve the problem: each time we bribe a node, we need to update the states of all of its relevant ancestors (i.e., the node has no bribed nodes in its subtree or has only one bribed child subtree that is different from ours). One last optimization is we need to avoid $$$\mathcal{O}(n^2)$$$ time traversing ancestors, so we use path compression to skip nodes that we can no longer update.

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

        I have quite easy log(n) online too. I don't compress paths though. Just don't go further up once you have someone with at least two active descendants.

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

        That sounds like the basic idea of my solution, but I was using heavy-light decomposition and for each path storing a std::set of the nodes in each state so that I could find the nodes that needed to change states. But then I also needed some Fenwick trees for counting, and a bunch of extra state to ensure I didn't count a single subtree with two bribed nodes as being 2+ subtrees, and it was getting very messy.

        What I did in the end is precompute the time at which each node would enter the state of "2+ subtrees with bribed nodes or bribed itself". That's pretty easy to do (just compute minimum ID in each subtree, and then look for the second-smallest child subtree of each node).

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

      It could be done in O(n log n), with just two BITs.

      Let Up[v] : 1 if Subtree(par[v]) — Subtree(v) has at least one bribed person, 0 otherwise.

      Then, for a bribed person u, the maximum controlled chain length of u is 1 + (sum of Up[v] for v in Path(u,root)).

      For each bribing, we can update Up[] in linear time in total, and can calculate the newly added value with BIT.

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

    The round was not bad, which is good because GCJ had some bad rounds. D was pretty fun.

    Maybe it would be better to replace B or C into qualification D, but that will leave me disqualified :(

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

Auto comment: topic has been updated by LoneFox (previous revision, new revision, compare).

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

I feel like changing $$$10^9$$$ to $$$10^{36}$$$ in B would've made a better problem.

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

    Yes, it would certainly be more interesting. Do you have a solution that runs in polynomial time (in the number of bits of input), or is it just that the numbers you need to factor are some root of the input values? I have an idea for a solution that doesn't depend on any factoring, but I haven't worked through all the details to be sure it works yet.

    Unfortunately it wouldn't be particularly friendly to people using languages without good 128-bit integer support (GCC has __int128 but I don't think it can do I/O on them).

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

      Looks like it's workable — I've implemented it and it produces the same answers as my contest solution.

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

      Right, you can check majk's solution for reference, it makes $$$O(n + \log \max a_i)$$$ calls to GCD.

      It takes just a couple of lines of code to parse a string into an __int128 and back manually, and also you need to use double to check if LCM doesn't overflow. I'd say __int128 doesn't cause much implementation trouble and there is no big Java/Python advantage.

      All those factoring solutions are oh so boring.

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

    Think twice before downvoting tourist, most probably you miss something.

    The essential part is to find the minimum $$$X$$$ that satisfies $$$lcm(X, V) = R$$$ without factoring them (when $$$V$$$ is a divisor of $$$R$$$).

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

      It seems the test data is weak. My first attempt at a non-factoring solution actually gets this wrong, and gives the wrong answer for

      1
      1
      L 100 1000

      but passes the official test data.

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

        That's true, I actually checked this during my 6 minutes and noticed that my solution does at most one useful iteration of the while (ok) loop on all 250 test cases.

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

    You could use the fact that either $$$V$$$ or $$$R/V$$$ is less than $$$10^{18}$$$ and still solve it with Pollard's rho algorithm.

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

      Well, perhaps you're doing something more insightful, but the official solution requires factoring both $$$V$$$ and $$$R$$$. Doing $$$250 \cdot 2000$$$ Pollard's rhos of $$$10^{18}$$$ in the worst case sounds a bit slow, too.

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

        Assume that there exists $$$i$$$ such that $$$O_i = \text{'L'}$$$ and $$$V_i < 10^{18}$$$. Then for each prime dividing $$$V_i$$$ we can find its power naively and for each prime that doesn't divide $$$V_i$$$ its power is the same as in $$$R_i$$$ so we divide $$$R_i$$$ by all divisors of $$$V_i$$$ and multiply by the result.

        If for all $$$i$$$ with $$$O_i = \text{'L'}$$$ we have $$$V_i \geq 10^{18}$$$, then for all such $$$i$$$ find prime divisors of $$$R_i/V_i$$$. Let $$$P$$$ be the set of all these primes. Then for each $$$p \in P$$$ we know the power of $$$p$$$. For all other $$$p$$$ we have some unknown upper bound on its power. Let's forget about it, calculate lcm of our current answer with all $$$R_i$$$ with $$$O_i = \text{'G'}$$$ and check that this number satisfies all conditions in the end.

        Regarding 250 tests, most of them are small, there even were some complaints regarding that.

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

          Of course you could increase $$$n$$$ as well, then it would not pass.

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

    After reading B I rushed into factoring ideas and I think I made them work, but fortunately quickly after that I came up with an easier to code approach. If there is any requirement of type L and R be the value associated with it then my set of candidates are divisors of R. If there is no such requirement then my set of candidates is just a single elements which is LCM of all values of R. Then for every candidate I just check whether it fulfills condition in a naive way.

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

    What is the time complexity of uniqueprimeFactors function?

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

      The usual O(N^0.5). The inner loop is just optimized to have a smaller constant. If you wanted to factor numbers beyond 10^16 or so, you'd want to go with a primality test followed by Pollard's rho algorithm, for an O(N^0.25) runtime. But I don't have that in my library. :)

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

Great, and again in majority we get sth like T<=250, but actually get 4 maxtest or whatever, BUT in problem A we got something like half of them! My outputs for BCD were computed in no time, but for A I became quite worried after I saw that it doesn't terminate in something like 5 seconds. I thought maybe my code loops or hangs somewhere, maybe I have corrupted input file (as my friend had last round because of some connection issues), maybe I compiled binary with all of my debug flags or whatever else, BUT NO, authors just decided to break this silent assumption which they made us believe holds and made majority of testcases to this problem maxtests and my code was legitly processing them for sth like 0,5-1min. At least I didn't qualify to the finals so that I will not have to worry about it again soon 8).

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

    Hmm are you complaining that your deduction that most test cases are not max tests was wrong this time and blaming the staff for it? Sweet.

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

      I am not sure if we live in the same world, but that's kind of ridiculous that we as contestants have no clue about how big is actual input. If you like guessing then from today on, on all contests you have $$$t \le 10^9, n \le 10^9$$$ in statement, even though $$$t=10, n \le 1000$$$ in system tests, wouldn't that be sweet 8)?

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

    +1, organizers are so inconsistent about the number of big test cases. It might be sometimes hard for a participant to predict if a solution is fast enough.

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

      Well my understanding is that you always need to assume the worst case scenario. If u want to risk the test cases not being max-tests, that's on you. It's a valid strategy but obviously comes with the risk of your assumption being incorrect

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

        Well, if you are dealing with sane problemsetters then that's good assumption, but not every problemsetter is like this. I actually had a pleasure of participating in a lot of contests organized by Jagiellonian University that has many solid people producing actually decent task, but they always do some shit like "t<=2e9" or "t<=1e6, n<=1e6 (and n numbers in the input per testcase) and they never gave any constraints on sum or whatever and we need to rely on an implicit never stated assumption that if our program is fast enough to pass one maxtest in a reasonable time then it is fast enough to get AC. Even after many complaints from many people they refused to change it ever and they were getting away with some really stupid arguments behind it. And it was quite serious issue since they organized CERC for 3 years (contest qualifying to ACM ICPC finals). And FBHC is bringing to me these haunting flashbacks again.

        Of course you are right that relying on some unwritten assumption is a risk, but I don't want to be in a situation where some people took that low risk and got away with some slow solution whereas I don't know whether I should be submitting my solution cause I don't want to take that risk. This is programming contest where your result should depend on your skill, not some casino where your result depends on risk you decided to take and your luck. Moreover in discussion about recent FBHC rounds you can read some comments like "but in FBHC number of maxtests is always small", or "oh, this solution to that new hypothetical task with enlarged constraints would actually be fast enough since there were just a few maxtests". It's not just me and people kinda take it for granted, but I don't want to have that uncertainty.

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

          I see what you're saying. It's really annoying when some constraints are not mentioned when they need to be. In case of FHC, they don't need to be mentioned because they're just solvable nonetheless. In case of those ACM contests, I just assume that as long as my solution works fast on one test case, it should be enough. I hate to have to do that, and sometimes it ends up not working fast enough.

          So I'm okay with FHC, because u don't need additional constraints to solve the problems. The fact that people can get away with slower solutions just adds to the strategic side of the contest. You said you think of it as a programming contest where only programming skills should matter. But to me, it's not like that. I like the idea of thinking about what's the best course of action to take, and not just hurriedly solving problems.

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

            Imagine the constraints say $$$n \le 10^6$$$ and there is indeed some complicated linear solution, but actually tests satisfy $$$n \le 2000$$$ and all quadratic solutions passed. Are you sure everything is fine as long as the problem is solvable?

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

              That's just exaggeration of what we're dealing with here. It's not that common, and the difference in complexities is not so drastic. And I believe it takes some cleverness to make it work.

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

    While I share the same opinion with you on the constraint issue, wouldn't your problem be easily avoided if you print out the number of current test case?

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

      You can also refresh the file from time to time, or just use tee that prints to both file and screen.

      But the main issue is you can't predict if your solution is good enough or not.

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

      I tried seeing whether something is output to the file during the surprisingly long execution, but somehow nothing was there after some significant time, I think it was caused by the fact I used "\n" instead of endls.