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

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

The first online round of the 2017 Facebook Hacker Cup. Open to all. All participatns who answer at least one problem correctly will advance to Round 1. The contest will be going 72 hours, from January 6, 2017 4pm PST till January 9, 2017 4pm PST.

Good luck and have fun in first great competition on 2017!)

To register, visit https://www.facebook.com/hackercup/register.

More information on https://www.facebook.com/hackercup/.

UPD Registration page was updated.

UPD2 Link to the contest: https://www.facebook.com/hackercup/round/1760504744276109/

UPD3 The contest finished, results is here. Congratulations for qualified to the Round 1.

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

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

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

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

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

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

"Good luck and have fun in first great competition on 2017!)" — let me disagree. First great contest will be Snarknews New Year Prime Contest (I hope it will be held as usual) :p.

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

What the hell... It's been almost a week and the registration page still says it's for the 2016 cup.

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

This is the first time I hear of facebook hacker cup...

What are the problems like...Is there anywhere that I can see the problem set of an older year ?

:)

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

Just for remind.

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

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

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

Why not it's being started yet ?

Please help us providing a link when you get :)

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

Where is the link to the Facebook Hacker Cup 2017 contest page ?

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

    I think it is only published on the Hacker Cup Facebook page close to the start of the contest.

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

Bump. Contest has started.

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

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

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

Are outputs of the form "0.4553223e-08" in the third problem acceptable?

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

The reader and writer don't matter, right? I just uploaded an output file(made with fstream) and after that I switched the reader and writer to iostream, and I uploaded the code. Is it correct? The output file had a random name.

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

What's the need of source code when we submit the output?

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

    To make sure that you didn't just copied/stole the results from someone else.

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

      Can I send a hello world program instead?

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

        As far as I know they have system test as well.

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

          There are no system tests. They only check, if the output is uploaded output-file contains the correct solutions.

          But I still would submit the used program. Terms and conditions says, that if there is an alleged discrepancy between the source file and the solution, they will check the code and the competitor might get a time penalty or might loose his points. Can't really imagine them doing so (with over 6000 participants), but still ...

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

    It is stated in terms&rules on their facebook link.

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

      I believe that your premise is false. Facebook does not specify any requirements about the source code, languages or libraries used at all, so one is free to use anything available in the world. Say, if your solution contains several files, you can zip them together and send an archive. Automating that kind of testing would be incredibly hard.

      As far as I know, there is no automatic testing of submissions. Submitted output file check is the only thing which matters for OK/WA. Source code is probably used for plagiarism check. Some submissions still could be checked manually (say, if it's someone passing to the onsite round).

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

        I have a question. Do they give random inputs for different participants and check their outputs according to output produced by their own program using same inputs or it's same for everyone? If it is the latter case then they are ought to have screwed everything up. Person A can solve and give output to person B and they upload random sources and tadaa... nobody can prove you did fishy things.

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

          IIRC, each participant is given a randomized data set.

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

          Even if the input is different. Person A can just run it's code for person B and pass B the output. What's the difference?

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

            So I emailed them and asked about possible ways of cheating including your point and how could they prevent it. They said; "That's true, cheatin­g can never be fully ­prevented in any onli­ne competition."

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

              Ya, my point is that regardless of given random inputs to participants, "cheatin­g can never be fully ­prevented in any onli­ne competition."

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

There is a "Download Input" button, clicking on which you'll get a file of the input .We have to generate output and submit it along with our code in 6 minutes. If you fail to do this in 6 minutes than you won't be able to submit the code for the problem. So click on "Download Input " only when you are ready.

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

On the "Progress Pie" problem, is the given point considered black if it lies on the circumference of the pie?

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

    Do not discuss problem from ongoing competition. And read constraints/problem carefully btw

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

      Well, I agree with this question. It wasn't clear. It's better when you don't need to guess what understanding is more probable.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +38 Проголосовать: не нравится
        Whenever a point (X, Y) is queried, it's guaranteed that all points within a distance of 10-6 of (X, Y) are the same color as (X, Y).
        

        I believe this is clear. A given point in the input will never lie on the circumference of the pie.

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

        Maybe it's not specified but it's not needed because you can't get such query

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

After submitting, I can theoretically download my output and source to check that everything went as planned. The output can be downloaded alright. However, when I try downloading the source, it gives me a page with the following message:

Sorry, something went wrong.
We're working on getting this fixed as soon as we can.

Now I wonder whether the system actually stored my source.

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

    I experienced the same thing and asked clarification.

    Answer: "We apologize for the inconvenience, we're working on fixing the issue with downloading source code files. Your source code has been successfully submitted."

    So, most probably your source is stored as well.

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

When and where can we get to know the result of Qualification round and check if our program passed on the system test?

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

to wjomlex and other Facebookers

There were several improvements that were suggested last year such as

Could you share any news on this features (e.g what is done, what is planned and what is not planned) or any other FBHC updates?

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

    Ad statements for non-competitors: I saw the statements without being registered, if that's what you mean (seeing them without being logged in is probably a feature of FB). Dunno if it will be different in other rounds.

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

    Mobile version: You can view the page on mobile, but it's definitely not optimized for mobile. This is a low priority since you basically need to be using a desktop/laptop to be competitive.

    Test distribution: Every problem has a set of tests that you're guaranteed to get, and this includes ones that test edge cases.

    Samples: The samples are always included in your input file, though not as the first K cases. So we don't really have that sort of pre-testing. However, the logic for presentation errors has been made more lenient, and you get a warning if you try to upload something that has the wrong number of lines, or bad "Case #x:" formatting. I talked about this last year: http://codeforces.com/blog/entry/15981?#comment-274649

    Giving encrypted files: We've been trying to avoid this problem by simply not having problems that have large input or output (our goal is to constrain both to about 3MB, and generally smaller than that). At onsite finals we relax this restriction since we can guarantee that everybody is on the same quality connection.

    Downloading output: You can do this now.

    Past rounds page: You can find it here: https://www.intern.facebook.com/hackercup/past_rounds/1760504744276109/

    Statements for non-competitors: The problems are now viewable by anybody, even if they're not logged into Facebook.

    We made the scoreboard show immediately upon round completion this year, since our previous approach required about a 10-minute delay.

    Also, we'll be rolling out a new clarification system, ideally for the next round, which'll make it easier for us to respond to clarifications, and let you view your clarifications in the Hacker Cup UI rather than having to go to your email.

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

      Looks like the new clarification system will be ready for next week, but we'll use the normal one this week again.

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

      Cool, thanks.

      As for usability from mobile: it is redirecting me to the m.facebook.com, which just shows "Sorry, something went wrong"

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

        Good to know. We should at least make sure it doesn't totally break :)

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

From the Progress Pie statement: "Envision your screen as a square on the plane with its bottom-left corner at (0, 0), and its upper-right corner at (100, 100)." Does it mean that the circle diameter is 100 or 101? Surely there are 101 pixels between 0 and 100 :) In the editorial solution the center of the circle is (50;50) with the radius=50. Why not (50,5;50,5) and radius=50,5?

ProgressPieCenter

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

    Don't think about pixels. I was confused by this at first too, but in fact the problem statement does not mention pixels at all. Simply think of the points on the plane (0,0) and (100,100).

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

      Since the problem statement started with the description of progress bars and then mentioned the screen and "Every point on the screen is either white or black." I somehow assumed we are not talking about points on the geometry 2D plane, but about the actual screen with the points being the alias for pixels.

      In the context of "a screen" I would be more inclined to read the expression (100, 100) as a pixel coordinate (ie. integer) than a real numbers coordinate.

      Anyway, I have read the problem statement once more and when I forget about the screen metaphor (ie. completely ignore visualizing the progress bar, "There are no pixels." etc.), then your explanation makes perfect sense. Thanks.

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

    The top right point in your pic is (5, 5), not (4, 4).

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

      It really depends on whether you're talking 2D plane geometry or pixels on the screen, on which the progressbar is drawn.

      "While you wait for the progress pie to fill in, you find yourself thinking about whether certain points would be white or black at different amounts of progress."

      I mean, while you are waiting are you thinking about the abstract 2D plane or about the pixels you are looking at? It probably depends on whether you're a math geek or a computer geek:)

      My mistake was focusing too much on the "screen" part of the story and not enough on the "abstract 2D plane" part.

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

        I fully agree: the statement had poor legend which could misdirect some participants (as it did with me). Strictly speaking, the "abstract 2d plane" interpretation is the only one that makes sense if we think that jury has provided all necessary details, but you never can be sure.

        1. If we talk about "screen" and "pixels screen", then it's natural to assume that all pixels are discrete, as they are in real screens. So, I did exactly that and assumed that we have a square grid.
        2. Next question: are the coordinates given of grid points or grid cells? I believe that's the question raised by tafit3 in their first comment. As there were no mention, I've started suspecting something.
        3. Next question: if everything is discrete, we cannot draw a perfect pie. So, some rasterization should be performed. It also depends on the previous question: are we talking about grid points (this case is pretty much obvious) or grid cells (and we probably should apply Bresenham's algorithm)?
        4. Next question: if the world is discrete, what is the sense of talking about answer being same in 10 - 6-ball around the point asked? At this point I finally decided to mostly ignore the statement and solve the problem on continuous 2d plane. Ranging it as the simplest problem of the round helped me to conclude that the solution should be simple and definitely won't include any fuzz with rasterization.
»
7 лет назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

In the first problem (Progress Pie), corner cases would be 0 50 51 and 100 50 51. The point 50 51 is on the axis corresponding to 0% or 100% progress. For the first one, the entire board is still white. For the second one, the point and its surroundings are all black.

However, there were no cases with substring 0 50 at all in my input. Were they intentionally avoided by the jury? Or maybe I misinterpreted the problem somehow, and they are not in fact corner cases?

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

    "Whenever a point (X, Y) is queried, it's guaranteed that all points within a distance of 10-6 of (X, Y) are the same color as (X, Y)."

    This is not true for the point (0, 50), thus it does not exist in the input.

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

      All points in an epsilon-ball around the center are the same color when the entire circle is the same color.

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

        Maybe I am idiot and my lack of geometry is showing. But (0, 50) is not the center, (50, 50) is the center, and (0, 50) is on the outer edge of circle, and therefore it is exactly at the discontinuous point of color where one side is black and other is white. Or are you saying something else?

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

          The input is given as the progress percentage, then the coordinate. The coordinate in the proposed input is (50, 51), not (0, 50), which is a valid coordinate to be included in the input.

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

            Oh sorry I misunderstood the whole proposed input, you and Gassa are correct, and indeed it is a good question as to why such cases were not included in input.

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

    (50, 51) is a nice hacking case, however (50, 50) for p=0 and 100 are also nice hacking cases. All of them are absent in my input.

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

      Yeah, the point 50 50 is basically the same deal as 50 51. It could have also appeared only at 0% and 100%, and the answers would be also white and black, respectively.

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

      I was expecting to have those edge cases, but my input also doesn't have them.

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

      As Gassa says, those points can only appear with P = 0 or P = 100, so they're not actually very interesting, with the constraints as given.

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

        By far the most common error I saw was using raw atan2() output (0 degrees to the right, 90 degrees up) and not transforming it to match how the progress pie actually fills in (0 degrees up, 90 degrees to the right).

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

        Why aren't they interesting? They are valid and they should fail some solutions, right?

        Or maybe they aren't valid? I think that all input constraints are satisfied for p = 0, x = 50, y = 60 and my accepted program doesn't solve this input correctly.

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

        They are completely valid and I am sure they will cause some solutions to fail (my solutions works on them, but it is just a lucky coincidence, because they didn't come to my mind when I was coding it). They are so called corner cases and even if it is simple to deal with them one has to be aware of their existence and handle them with appropriate care. And it is organizers duty to do their best in order to accept only those solutions which give correct answers on all valid data. Working on real software should teach one that corner cases and error handling are crucial part of creating good software.

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

        Yeah, those cases are valid, I just didn't consider them to be as particularly interesting as some of the other hardcoded corner cases, since the problem is pretty trivial when P = 0 or 100.

        As I read the clarifications for this round though, it became clear that a lot of people were missing the line where I state explicitly that all the points are white when P = 0, so I could have been more thorough about stress testing people on it.

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

What mistake I have with my code (Second Problem)? Problem with file?

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

In problem C, a simple way in C++ to read the input (with optional Z) was

  int H, S, X, Y, Z;
  char dummy;
  string spell;
  cin >> H >> S;
  while (S--) {
    cin >> spell;
    stringstream ss(spell + "+0");
    ss >> X >> dummy >> Y >> Z;

Adding "+0" or just " 0" makes sure that Z = 0 when it is absent in the input.

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

    Initializing Z to 0 also seems to work fine if we do not add "+0".

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

    That's how I did it:

        scanf("%dd%d%d", &spell.times, &spell.sides, &spell.z);
    

    Don't forget that scanf can be used for formatted input too.

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

      I thought about sscanf but I believe you should have checked the return value to know if Z was read or not. Otherwise, I'm not sure, but I suppose the value of spell.z is undefined.

      In any case, I prefer using stringstream because the code is concise and leaves me no doubts of its correctness (same with the comment from anuraganand).

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

        If z is initialized to zero then there is no need to check the return value.

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

          Could you give me a reference for this?

          I did a quick search but could not find a guarantee that scanf or sscanf don't touch arguments that it couldn't successfully read.

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

            There you go. The link contains relevant quotes from the standard so yes, it's safe to use both scanf and sscanf in this case.

            Please don't assume that I'm against the cin usage, but there could be a lot of reasons (outside of the scope of this discussion) one would like to prefer scanf over cin.

            Know your tools and choose what's best, I'm sure my method would be helpful to someone especially because it's a one liner and does not require any additional dummy variables.

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

When the next round starts? I checked the official page but I didn't find anything about that.

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

When can we upsolve?

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

Out of the 12804 participants, 1750 got the perfect (100) score.

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

Can someone please tell me where I made a mistake in my code for first problem.

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

    Just download one of the correct solutions, then compare the result produced by that solution to your own (for the same input), and compare the 2 outputs.

    You can use diffchecker to compare 2 files.

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

I downloaded progresspie.in from Dropbox (link is in the editorial). It contains T=2005 tests. While in the problem it is stated that T <= 1000. And the progress_pie.txt I got during quals contains 1000 tests.

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

How does everyone decide that their solution will work within six minutes. What is the bound on the number of calculations for this 10^6 or 10^7 or 10^8 .. ?

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

    Depends on your machine. A safe estimate would be 108 per second. And typically you only need a few seconds to solve the problem. The 6 minutes is just to make sure everyone has time to fiddle with files and uploading etc.

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

I passed Elemination Round. Now i want particpate 1 round. When I want log in to facebook,site asked ID from.Then i sended Photo of my Passport.Then this message comed.
We'll get in touch with you at the email address you provided after we've reviewed your ID. You will now be logged out of Facebook.
What can i do,to participate this round quick as possible?