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

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

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

The round will begin on August 27th, 2021 at 10am PDT and will last for 72 hours (3 days). The contest can be found here.

Everyone who solves at least one problem correctly will advance to Round 1, which will take place on September 11th. Please note that all submission judgments will only be revealed after the round ends. More details about rules and other information can be found in the FAQ.

Registration will remain open on the contest page until the end of the Qualification Round. Once you've registered, you may wish to confirm that the information in your competition profile is up to date. In addition to choosing a Display Handle for yourself there, you may now also indicate which country you’d like to represent on scoreboards.

This year's contests will feature a new submission flow making it easier to download large input files. For each problem, you'll now download the full input in a password-protected zip file, and the 6-timer will only begin when you then request the password to access your file. You'll also be given the option to directly download the raw input file (as in past years) in case you have trouble with the zip file. Please see the “How do I submit my solution?” section of the FAQ for more details.

Last year’s increased prizes are making a return in the 2021 Hacker Cup season, including 2,000 t-shirts to be won and a $20,000 grand prize.

We wish you the best of luck, and hope that you enjoy the contest!

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

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

I had a question : is 6 minute time limit when downloading the input the only TL constraint on our programs ? Or is our source code ran with a tighter TL in the background after contest finishes ?

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

    Your code will not be re-run, so the only time limit is indeed the 6 minutes you have to run your code and upload your output upon downloading the full input — please see the FAQ for more details.

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

      Thanks

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

      What happens if somebody submits a correct output, but wrong source code? For example, the source code of a problem A solution as a part of their problem B submission?

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

        For such cases noticed by the Hacker Cup team, you may be asked to provide your correct source code file after the fact, and intentional submission of wrong/fake source code may in some cases be grounds for disqualification.

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

Very Excited to participate as it will be my very first contest. I request every one who is reading this give your time to each question and try to solve at least anyone of them, you have 3 days.

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

How many official submissions can we make ? I am asking this because what if we aren't able to submit the solution and output in 6 minutes due to any reasons like Power failure or network issues. Will we be able to submit the solution and output for some other input file in 6 minutes ?

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

    You'll only have one chance per problem, meaning that you should be confident that you'll be able to complete your submission within 6 minutes before starting your timer.

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

      Thanks

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

      Last time I had coded the correct solution for a problem, but during submission my program crashed. I could not submit in 6 minutes. Later I found out that it was due to smaller stack size of execuatables on windows.

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

Have a small question. Why dont we have the feature of submitting the code directly and run in your server rather than we running locally like almost all the sites (eg. Google Codejam) ?

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

    There are a couple major advantages (imo) of this system:

    1. If you have local library code you want to use, you can simply import it into your main source file and not have to copy it over and clutter your code.

    2. The 6 minute time limit makes more unconventional solutions and strategies possible (and thus, allows for unconventional problems which might not be solvable with a traditional time limit), which makes for a unique experience. I actually enjoy this more than the traditional submission system.

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

      Even more than local libraries, you can use other tools and environments not usually possible in programming contests. Want to use a spreadsheet or some special math software like Sage? Totally possible in this format.

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

      Does that mean they only care about the output file and not the source code?

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

    Because it's way harder to setup a whole online judge?

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

    People can use different unconventional tools. Like the things then do in Advent of code.

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

can you tell where is the option to directly download raw input file without downloading the zip file, since I downloaded the zip file but was not able to extract the input file while I was trying to unzip it. It showed that an error occurred. Resulting, that I wasn't able to submit correct output file. Although I am pretty much sure that my solution is correct.

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

    The option to download the raw input file shows up in the same window right after you request the password. I also wasn't able to unzip the file right away, so I used this option. Appears that just running 7z x consistency_chapter_1_input.zip and then pasting the password from the clipboard didn't work correctly on my system and 7z rejected the password. Later trying it as 7z x -p12345678 consistency_chapter_1_input.zip worked (substitute '12345678' with the real password).

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

      do you mean that after verifying sample test file, in the same open dialog window, there is an option to download raw input file.

      I am concerned only because I fear to not a submit a solution within 6 minutes, because of these petty issues. Please help.

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

Can anyone tell me how can we run our code on an input text file and produce an output text file. I am using code blocks IDE on windows system. I also tried to manually create the output file by copy pasting input and output . But it's showing me presentation error.

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

    ./file_base_name<input_file_name.txt>output_file_name.txt

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

      Thanks for replying. Can you please tell me where to use this command. I used this in command prompt and it's not working.

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

        Assuming your program is taking input from standard input and outputting to standard output ( e g cin, cout in c++) . Let s say your executable is called a.out after compiling the code. Let s say you have a1.in as input file, and ypu want output to be at a1.out . Then ./a.out < a1.in > a1.out in terminal

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

        You need to replace:
        1)file_base_name — with the executable
        2)input_file_name.txt — with the input file file.
        3)output_file_name.txt — with the file in which you want the output
        This will work in the command prompt once you locate your folder. You can locate your folder using cd +(folder_path). Here replace folder_path with the path of your folder where your CPP file is.

        for generating the executable for your c++ files uses the command. g++ file.cpp -o file (replace file.cpp with the name of your file) It should work after that.

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

it would be really cool to provide participation/progression certificates to participants like the CodeJam, ignore this if already implemented this year <3

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

    Such certificates are in fact available as of this year! You can find past certificates in My Competition History within your profile page, and links to certificates for the 2021 season will also be available as the season progresses.

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

what is the password?

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

    After downloading the input zip file, password is used to open and access that file.

    Note down, You have only 6 minutes for :

    Enter password -> unzip the file -> Run code on it -> generate output file -> submit(source code + output file )

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

imagine having a supercomputer and being able to run any kind of bruteforce...

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

    Even simply having a multicore processor allows to use OpenMP pragmas or the other easy tricks to parallelize the code and make it run faster. And it is fun, because these are the skills, which are never tested in the other competitive programming contests.

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

    It gives us 6 minutes to submit the output. I am pretty sure even my potato computer can do in this time.

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

I can't open the zip file by macOS default application.

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

After reading "Xs and Os" I wonder: why are we being encouraged in such a stupid cheating? :)

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

LoneFox when I am clicking on download validation input file, it starts downloading an index.html file. I have tried it 4 times. what should I do?

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

I had a doubt, when it says solution validated does it mean it was correct for that test case or it just means it was submitted successfully?

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

Solved!

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

Well, it's nice to see the "password protected input" feature implemented, but do you really need to use some fancy compression method that standard tools don't support? This is not nice:

$ unzip consistency_chapter_1_input.zip 
Archive:  consistency_chapter_1_input.zip
   skipping: consistency_chapter_1_input.txt  unsupported compression method 99
  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Check out their FAQ page. They have clearly mentioned about unzipping and tools that would work without any issue.

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

      The point is that a standard tool such as unzip should work. I spent some time and couldn't find any way to open a FHC zip file in my system (I didn't want to install new software just for this contest). Fortunately it was also possible to download the input normally.

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

    It's indeed necessary to use this type of encryption (AES-256), as the default "ZipCrypto" encryption is highly insecure (further reading here).

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

      Thanks for the explanation. So maybe unzip should support AES-256 (if it really is industry standard).

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

      Oh wow, thanks for the info! It feels so counter-intuitive that zip and unzip are not the right tools to handle [encrypted] zip archives.

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

    install 7zip in MacOS. then run this command on terminal: 7z x problemName_input.zip

    This command will prompt for password. Paste the password with (Command+v) that you copied.

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

I've just registered on Facebook, but it buns me without any reason. I send them my photo and now have a message that they will check it , but I can't write a qualification round without an active Facebook account. Can they unblock my account faster or can I solve problems from this round without a Facebook account?

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

I would have preferred the source code to be submitted during validation to have a less panicky 6 minutes.

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

I created a Facebook account yesterday to participate in Hacker Cup. But Facebook has disabled it twice. When it disabled it the first time, it asked me to verify my phone number which I did. Now it is again disabled and Facebook asked for a photo which I have sent but I haven't received a reply. Now I am scared if my account remains disabled, I won't be able to participate. I have tried to create another account with different emails but all are disabled after they are created. Someone, please suggest what I should do. LoneFox please tell me something.

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

It might be a dumb question but do we have to solve any one of A1, A2,B, C1,C2 or one question is A1,A2,B and other is C1,C2.

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

After the end of the contest , how much time it will take to evaluate the submitted solutios?

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

What if I submit wrong code but correct output?(I ask for people to try to escape plagiarism checker(if it exists))

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

Why do you have to make the process more tedious by adding password protected inputs? I had issues with extracting the file.

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

    We added this feature so that there's less chance of a slow internet connection interfering with your ability to submit.

    You're still able to download the input directly instead of downloading the zip file, if you desire.

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

    People can face issues while downloading the large input file (like slow net, power cut, system crashed, etc). Password was introduced so that the timer will start after the user has finished downloading the input.

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

Hi, I'd like to suggest you could add functionality to the scoreboard to filter by country, like Google Code Jam has.

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

Any intuition as to why this is wrong for C2? Only fails on large cases from the official test set.

Fix first path from $$$1$$$ -> $$$a$$$, last from $$$b$$$ -> $$$1$$$ for all possible distinct pairs of $$$a$$$, $$$b$$$ such that the paths don't have common edges, mark used edges and set $$$c_{x} = 0$$$ for nodes visited. Then $$$k - 1$$$ times, choose the next best path as the diameter with respect to $$$c_{x}$$$ using only unused edges (also mark used edges and set $$$c_{x} = 0$$$ for used nodes). This logically seems correct on examination with exchange arguments on $$$i$$$-th and $$$j$$$-th paths taken in optimal order, considering cases where paths have / don't have a common node separately.

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

    Consider the case where $$$k=2$$$ and vertex $$$1$$$ has only one edge coming from it, like:
    4 2
    1 1 1 1
    1 2
    2 3
    2 4

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

      But, for that case you can choose $$$b$$$ to be equal to $$$1$$$ (root).

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

      Yes, I should clarify that $$$a$$$, $$$b$$$ can be $$$\textbf{any}$$$ pair of nodes for which the paths from $$$1$$$ to $$$a$$$ and $$$1$$$ to $$$b$$$ do not have common edges. Otherwise this would have failed on the samples itself.

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

    https://imgur.com/a/yvjkA9z

    Your approach might not work in the case mentioned in the image above, as there is no such pair of a and b according to the conditions you have specified.

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

      I should have clarified, b can be equal to any node, include $$$1$$$ (the root itself), so in this case choose a = the bottom left node, b = the root, then the max diameter picked in the 1 remaining step will just be the bottom right node.

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

    Got the mistake, my proof is wrong since the exchange arguments proof only considered common nodes, forgetting about common edges.

    Assume we get the above structure as one of the trees of the remaining forest after fixing the paths $$$1$$$ -> $$$a$$$ and $$$2$$$ -> $$$b$$$. Additionally let $$$c_x = 1$$$ for all nodes. Then we can consume all resources in $$$2$$$ paths ([1, 2, 3, 7, 8] and [6, 5, 4, 9, 10]), but if we take any diameter it will require $$$3$$$ paths to consume all. So taking the diameter isn't always optimal.

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

      Did I get something wrong or in your optimal solution you used the diameter of the node $$$4$$$? (path $$$6$$$, $$$5$$$, $$$4$$$, $$$9$$$, $$$10$$$ is the diameter path).

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

Created video solutions for Facebook hackerCup solutions, if interested please checkout:

https://www.youtube.com/watch?v=hjTAshY60Xo&ab_channel=AlgoShalgo

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

Question:

How do I know if I qualified for Round 1 of the hacker cup? Would there be any official communication from the Facebook team?

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

    You can check the unfinalized scoreboard here, which would tell you if you got any of the problems incorrect. We will be sending out official advancement emails later this week once the results are finalized.

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

I have a doubt that why they use 6 minute timer?

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

    Since you get to run your own code locally, if there were no timer, you could write naive solution that should be too slow, but just wait a long time for it to finish running.

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

      But you guys are also taking our code right? Also, why not just be like other coding competitions where you just submit and get instant feedback?

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

    To have enough time to sort out how to unpack this thing

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

I appreciate the step taken be facebook to provide certificates but I would like to point out that the rank cannot be seen clearly/visible.

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

I don't have any idea. How did I miss this year hacker cup :(

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

I think that the problem B had weak testcases. I initially implemented a very suspicious messy solution, which passed the validation input:

A buggy implementation in D language
A buggy implementation converted to C++17 language

I wasn't happy about it and reimplemented my final solution in a different way before submitting. Turns out that my initial implementation was indeed buggy and failed the following simple testcase (printed "Case #2: 1 2" instead of "Case #2: 1 3"):

A small testcase

But the official "xs_and_os_input.txt" input file from the contest was unable to catch this bug, so both buggy and correct implementations produced the same output. Did all participants receive the same "xs_and_os_input.txt" file or are the input files randomized to some extent?

Edit: Added a C++ variant of my broken solution if anyone wants to hack it (this code is very broken and should never pass any reasonable tests). But it happens to generate correct output for "xs_and_os_input_practice.txt" too (downloadable in practice mode now). Tagging LoneFox and SecondThread if they are maybe interested in fixing at least the practice mode.

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

    Your code always excludes some value from tmp even when it's not an optimal answer. When it's an optimal answer, the way tmp being constructed is incorrect, too.

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

    Hi, yes, I'm interested in potentially adding a case to the practice input at least if it won't create technical difficulties if we later need to re-judge things for some reason.

    However, the small case you give isn't legal according to the problem spec. Note this part of the statement:

    In the game's current state, both players have made an equal number of turns (in other words, the number of Xs is the same as the number of Os), neither player has won yet, and the game has not yet ended in a draw (meaning that at least one cell is still empty).

    Can you please provide a case that you think would be equally powerful that satisfies these conditions as well?

    Regarding your question:

    Did all participants receive the same "xs_and_os_input.txt" file or are the input files randomized to some extent?

    Different participants may receive different inputs. We use this for plagiarism checks and validation to sanity-check participants to make sure they are submitting the right thing.

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

      Thanks for your reply. You are right. There has to be the same number of Xs and Os on the board. One of the minimal testcases that satisfies the conditions would be:

      Spoiler

      In general, the most tricky part of any solution for this problem is handling the case when minimum k = 1 (the number of Xs to add for a win). Let's call a row or column interesting if it contains all Xs except for one dot. And a test is interesting if the combined number of interesting rows and columns is at least 2 (but 3 or more is even better). I think that a strong testcase for problem B needs to include a lot of interesting tests to catch a wide range of possible bugs in handling of the k=1 case.

      I also see that the practice testcase includes 82 tests. But the problem constraints are T<=70. Maybe problems of this kind could benefit from a much larger limit for T? Otherwise it's hard to fit a lot of interesting tests in a testcase and make it strong.

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

How can I see the leaderboard for a specific country?

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

Could someone (un)justify this idea for C2? There are N * (N - 1) / 2 paths in a tree. Consider all the paths as vertices in a new graph, where weight of a vertex is sum of the corresponding path. Now, two vertices in a new graph will be connected if their corresponding paths share at least one edge. Then the problem reduces to finding maximum weight independent set in the new graph (with a restriction that at least one path must contain vertex 1 in original graph and cardinality of the set must be at most K). But the new graph is bipartite, so one can find maximum weight independent set by means of maximum matching which can be done efficiently in bipartite graphs by some max flow I believe. The thing is, I don't know if it's possible to use maximum matching for finding maximum weight independent set (it seems possible for unweighted case), i. e. by somehow tweaking the max flow algorithm. In addition, it could be hard to ensure that path with a root in original graph would be a part of the max independent set. But is this solution path correct in general?

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

The rank in my certificate isn't visible clearly. Can you fix this?

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

I solved C1 using information from direct children of node 1 (counting edge cases of having single child seperately). I have not done much question on tree-dp. Can anyone explain simpler method for C2.

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

what is the criteria of getting t-shirt LoneFox?

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

    From https://www.facebook.com/codingcompetitions/hacker-cup/2021

    What prizes can I win? The top 2000 competitors who solve at least one problem in Round 2 will receive a Facebook Hacker Cup t-shirt. The top 200 competitors from Round 3 will have a "Top 200" badge on their shirt.

    I would say that both of us at least have a chance. Finishing in the top 2000 is sometimes possible if the stars align right ;-)

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

Surprisingly, my C2 has passed, while C1 has failed with the same solution. I suspect weak tests for C2.

For C2 I used O(N*K*K) DFS-based DP, where for every node V, DP[V][i] is the max sum taken from the corresponding subtree using at most i paths (with disjoint sets of edges), where i is either an integer or an integer with a 'half' (the latter means 'open' path extended outside the subtree). The last step in the solution is correct interpretation of DP[1] for obtaining the result (we either add 1 or not depending on whether a found set of paths passes through the vertex 1).

Has anyone experience the same or does know why my C2 solution doesn't work for C1?

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

    Could you please post a link to your C2 solution? And also pastebin your C1 testcase somewhere?

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

How do I know if I have advanced to Round 1? When I open the Round 1 page, it shows "You have not registered for this contest". I was able to solve 1 question & it is correct.

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

Is it only me who solved C1 with LCA? LCA seems unnecessary here.

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

    I also overkilled the problem using LCA. I checked for every leaf pair and checked their LCA, if it is 1. Although I realized later that this was a simple problem that could be solved just by getting information from direct children of 1 (if any).

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

Hi, I'm trying to understand a C2 solution. I can't get the concept of extension points for the paths in the subtree. I understand that the path, which has one endpoint (extension point) in the subtree root, can be extended from the parent, by using parent-child edge. However, I noticed that there is a dp state, which has 2 such extension points — could somebody explain this situation? How could the path in the subtree be extended in 2 places?

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

I have a doubt regarding the round 1. Does the 6 minute timer appear only once and after that time, we cannot submit for that problem? I tried running my A1 solution and I use online codechef IDE and the input was too large for that and the timer ended before I could install a local compiler on my laptop and I can't submit for that problem again :(

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

Does after solving A1 and A2 , is it guaranteed that I am qualified for round 2.

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

    Everyone who scores at least 24 points (regardless of time taken) will advance to Round 2
    Source

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

    Yes, you will qualify if both of them are correct. But you won't get the final verdict whether they are correct until the contest ends as per my interpretation

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

How to run the input files for a1 every compiler says input too large.LoneFox

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

    in linux/windows for cpp

    g++ codeFile.cpp
    
    ./a.out < inputFile.txt > outputFile.txt
    

    in macos/linux/windows.

    g++-11 -Wall -O2 -std=c++11 codeFile.cpp -o code
    
    ./code <inputFile.txt > outputFile.txt
    

    codeFile contains your code in a file name codeFile.

    inputFile contains input

    and outputFile may or may not be in your disk if it is not then it is automatically created in the same directry.

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

I was confident about the code which I wrote for A2 , it passed validation tests but while compiling the code crashed on sublime Text . What precaution should I take such that it does not crash for remaining problems ?

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

    Same happened with me too.. It was because I was not creating the N sized array globally.. After the time ended, I tried on the same input with globally declared array and it executed properly on Sublime..

    Maybe your crashed due to same reason :/

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

I got a problem in the final input file of the problem A1("Weak Typing — Chapter 1") of round 1 . The characters of the file are different from the input format of the problem.

Screenshot

Is this a problem with my PC ?

LoneFox Pls Help !!