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

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

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

The round will begin on June 29th, 2019 at 10am PDT and will last for 24 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 1 if you solved at least one problem correctly in the Qualification Round.

Everyone who scores at least 30 points (regardless of time penalty) will advance to Round 2, which will take place on July 13th. Please note that all submission judgments will only be revealed after the round ends. 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!

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

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

Does the problems visible to the members who haven't attempted the qualification round??

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

Hi, I had commented on the FB post but no reply. I did not received the confirmation mail for the advancement to Round-1 though I had scored 30 pts. Please check that out.

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

This starts in under 1 hour! Good luck to all!

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

Which online compilers should I use for such large input and outputs..

Ideone doesn't seem to work for that

plz help...

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

plz help plz.... fast

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

LoneFox, What is the time limit of problem B.

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

    The only time limit for each problem is that you must be able to generate and upload your output file within 6 minutes of downloading the input file.

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

Great and interesting problems, thanks.

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

I first submitted the correct code and the correct output for the 2nd problem, but then I bymistakenly resubmitted the code and the output, but for the output I submitted the wrong file. What do I do? The code I submitted is correct. 6 min timer has expired.

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

    Please submit a clarification request in the Hacker Cup interface for issues like this.

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

    I too have a query, that whether the input file changes on each new submission or it remains the same because I just forgot to download the new input file and made submission on the old input file. Can someone confirm this, I am really worried about it :(

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

      The input file stays the same per user for the entire 6 minute window. You do not need to re-download it before resubmitting.

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

    I guess your solution will be judged as invalid. :< You can try submitting a clarification request and describing your situation, but I wouldn't hope for much. (As a good thing, you still have time to work on other problems.)

    A small lifehack for the future: you can look at the details of your submission (a link just above the submission form), where you can find the MD5 hash of your output file. You can then compare this hash to your local file (e.g. on Linux, md5sum my-output-file) to make sure you submitted the correct output.

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

What's wrong with this solution for 1'st problem- Add edges as given. Calculate all pair shortest distance using floyd-warshall and then check if it matches with the given information.

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

    I did the same and got accepted.

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

    I have similar idea and also got wrong, run floyd-warshall on gived edges. Check if distance is correct.

    Then, just printed edges for each pair of vertices in graph where there is a path with weight equal to the distance between them.

    Link to code

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

      You shouldn't print edges with weight > $$$10^6$$$.

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

        I am printing edges with weight=1 (for the nodes which are not mentioned in the input edge list. I am just joining all of them with a single node with weight=1)

        Still got WA.

        Here is the code: https://codeforces.net/gym/102264/submission/56359042

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

          But then you are introducing new edges and therefore possibly newer shorter paths. The statement says your output graph needn't be connected, so you can just print the input without adding extra edges (provided the input satisfies the triangle inequality).

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

            But I am adding the remaining nodes(which are not connected with any other node) with only one node(let's call it node A). How will this result in newer shorter paths because the remaining nodes do not have any constraints on them (i.e. Not mentioned in the input edge list)

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

              You're right, my bad. The issue is in your Floyd-Warshall code. It is important that your loop structure has the following form:

              for (int b = 0; b < n; ++b)
                for (int a = 0; a < n; ++a)
                  for (int c = 0; c < n; ++c)
                    if (d[a][b]+d[b][c] < d[a][c])
                      d[a][c] = d[a][b]+d[b][c];
              

              That is, your outer loop runs over all possible 'midpoints' to relax. To see why this works, imagine the optimal path. Every time the outer loop (over b) runs over a vertex in the optimal path, this vertex gets 'cut out' by the relaxation step (imagine removing it and connecting its endpoints a and c with a new edge).

              Conversely, your code currently has the following loop structure:

              for (int a = 0; a < n; ++a)
                for (int c = 0; c < n; ++c)
                  for (int b = 0; b < n; ++b)
                    if (d[a][b]+d[b][c] < d[a][c])
                      d[a][c] = d[a][b]+d[b][c];
              

              Here we loop over the point to relax over (b) inside. It's not easy to find a counter example for this, e.g.:

                0 -- 2 -- 3 -- 1
              

              .. where all edges have weight 1. This loop structure will never find the optimal path from 0 to 1, see here: https://ideone.com/rdJue1

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

                Ah, yes you are right. I thought the loops are independent because that's how they look, i.e. the initial and final values are 0 and n-1 in all of them, so I thought the order doesn't matter.

                Thank you so much for the clear explanation.

                Update: I submitted again after making changes and got AC now.

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

                  Hi, I am one of the author of this paper. Where did you know it? (Just for my curiosity)

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

                  There's a funny story behind this paper. They prepared a problem that requires Floyd Warshall on AtCoder. Then, they wrote incorrect solutions to make sure that they fail — but magically, with three repetitions, they passed.

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

                  Nice. What's next? Maybe it's enough to run greedy approach three times to solve knapsack? That would mean that P = NP. Even more, that would mean that 3*P = NP and you can compute N from that.

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

                  Actually no, the opposite is then true, if P = NP and 3*P = NP then 3*P = P so P = 0 and N is indeterminate :)))

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

                  I think I saw it on the "Theory of Computing Blog Aggregator" RSS feed as a newly posted paper on arxiv.

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

      What I did was first checked the given data with floyd warshall and if passed then printed the same data in the output. I got AC.

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

      Instead of doing what you did, just printing all the edges in your 'edges' vector gave AC.

      Your updated code

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

    Bear in mind that edge weights in your graph must be between 1 and 1,000,000, inclusive. Some pairwise node distances in the graph (aside from the ones in the restrictions) may exceed that value.

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

    Did you consider the case where multiple distance request are on the same pair of vertices?

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

I came up with a max flow solution for C, but didn't have time to code it. Did anyone else take this approach?

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

    I think it is the only solution.

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

    I also solved it with max flow.

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

    Am I the only one who solved C with DP?. To whom it may concern, link to my code: https://pastebin.com/ziQz0hAp.

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

      I also used DP, but only had $$$N^2$$$ states compared to what seems like $$$N^4$$$ in your code.

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

      Can you please explain your approach?

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

I think I have been judged incorrectly for problem A, I have checked my output by running someone else's code whose code got accepted. Both the outputs match.

LoneFox

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

    I'm afraid your submission is indeed incorrect, there's at least one case for which it outputs a graph when the answer should be "Impossible". Please see this post for the official solutions and full input/output which you can download!

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

      I have matched my outputs by running two person's codes on the input I got and our outputs match exactly. diffchecker says the two files are identical

      If my solution got rejected, they how did their's solution get accepted, even when the order of the printing of edges exactly matches with theirs

      LoneFox

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

      I have submitted the same exact code on Codeforces Gym and my code got accepted. Now?

      LoneFox

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

        I've responded to your in-contest clarification with your submitted output file as well as the correct one, so you can see for yourself where exactly you went wrong. I can't comment on the CodeForces gym and how its own custom judger was set up.

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

A solution for problem D.

First, if V = number of points, then every line might be a vertical line, so consider this as an alternative.

Otherwise, at least one line must be horizontal. Sort the points by X and then by Y. Now for each point we think about the solution if this point is the last one with an horizontal line. If it has an horizontal line, all the points that are upper and to the left must have horizontal lines. The points that appear later have vertical lines. Finally, the points that are at the left and lower, might be vertical or horizontal. If some of them can have horizontal lines (based on the value of H), it is good for us (because the additional cost is 0), so we put horizontal lines in those that have a larger Y. This can be implemented efficiently with binary search trees (for instance using the ones in the STL). Of course, if the number of horizontal lines or vertical lines results in a too large value, this option is discarded.

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

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

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

The contest is in Codeforces::Gym: 2019 Facebook Hacker Cup, Round 1

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

Why solutions are not checked even on sample test?

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

Gym's Testcases for Problem A are weak

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

    Maybe you should read the proof of Floyd's algorithm and see why the order is important.

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

      Pfff, no. I'd rather ask it publicly and let somebody else rewrite the proof and explain it to me in a magical way.

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

    xd

    "I'm getting WA" changed to "testcases are weak".

    Also, if you get WA on some big test, you can still test it yourself on small random tests. Read more here.

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

      I got my mistake but still my wrong solution got accepted on Codeforces Gym. There was no option to delete the comment so I edited it so that people dont make the same mistake I did and run to Facebook telling that their solution got accepted on Gym but it gave WA on Facebook

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

        Then next time write a new comment for that. You modified your comment and now all replies don't make sense unless somebody clicks a small <- rev button.