eatmore's blog

Google Code Jam 2018 round 3
By eatmore, history, 7 years ago, In English

Google Code Jam 2018 round 3 starts on Saturday, June 9th at 14:00 UTC and last 2.5 hours. Top 25 contestants will earn a trip to the final round in Toronto.

Also don't forget about Distributed Code Jam round 1, which starts a day later.

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

Comments Comments (33)
| Write comment?
»
7 years ago, # |
  Vote: I like it +52 Vote: I do not like it

I've just noticed that I was supposed to register for Distributed Code Jam if I want to participate according to the following sentence in the email.

If you would like to participate in Distributed Code Jam, you must register here with the email address used for 2018 Code Jam registration (the one this email was sent to) by Wednesday, May 30th at 11:00 UTC.

However, I never noticed it before, and therefore didn't register. Is it a problem? Will I still be able to participate?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Response from Code Jam team:

    If you have an existing user profile in our system (say for a previous year's round of DCJ, participating in a spinoff competition like Kickstart or I/O) then our system registered you automatically. The best way to check this will be to login with the email where you receive our Code Jam email notifications, as this would be the account that we automatically registered.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +89 Vote: I do not like it

Google Geometry Jam 2018

Btw, how to solve C?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Even the first one is sort of geometry:))

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

    https://codejam.withgoogle.com/2018/challenges/0000000000007707/analysis/000000000004b90d

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I don't really understand the editorial for the third one. There are several blurred parts but what interests me the most is how to get the polynomial algorithm. There is an explanation for being at most 2 good choices for a third point of a valid plane when you have two points fixed already. And I agree with that (it depends in which direction you rotate). And it seems like the solution somehow concludes one of them is better without actually telling why is that. Can someone, please, explain?

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

        If I'm not mistaken you can chose whichever of these 2 points. No matter what you chose you can continue this process until nothing is left.

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

          I'm still trying to understand the rest, but could you tell me why you think that is like that? I can't see any way to prove it

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

            I keep an invariant that I have two points so that there exists third point such that all the rest lies below plane determined by these three. Note that this invariant is equivalent to "there exists a plane passing through P and Q only so that all the rest is below that plane", because I can rotate it around PQ and I will encounter some point which can be the third one from previous formulation. So let these points be P and Q (where P is further in order, so that it will be removed earlier) and let third point be R. I remove P, do assigment P:=Q, Q:=R and I know that there exists a plane passing through new P and Q which has all the rest below (which is second version of my invariant), so invariant is kept and everyone is happy.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              ← Rev. 2   Vote: I like it +5 Vote: I do not like it

              Thanks a lot! It makes sense, I've thought of looking for an invariant but I was too stupid to see it was in front of my eyes. So the initial choice should just be of 3 points that are above all the others, and we can do that by fixing all the points of max z (at most 3 of them) and then one other point and then rotating the plane around this line so it's a N^2+N^2. Makes sense. Thanks again!

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

                We just need two points and you can take arbitrary edge of a convex hull when projected onto OXY plane.

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

            I didn't got AC so not sure if I can talk, but you can easily understand the solution if you think for a 2D variant : y = 0, and triangle to line segment.

            Then, you can remove any point in a convex hull, remove another point that was adjacent in previous convex hull, and so on..

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

            Ultimately, this is about a general property of convex hulls: Let X be a set of points, Y be a subset of X, and p be a vertex of the convex hull of X. Then, if p is contained in Y, p must be a vertex of the convex hull of Y.

            This time, we keep three vertices that forms a face of the convex hull. Even if you remove arbitrary one of these three, the remaining two points must form an edge of the convex hull of remaining points, because these two points are vertices of the convex hull of remaining points.

            → Reply
»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Finding out the bounding rectangle of 2D points -- 14 points. Finding out line and plane intersection in 3D -- 7 points.

ggwp.

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

    I don't know how to prove the first one, but I know how to prove the brute for the third one:))

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

      I agree with you. Solution make sense but I don't have a proof, 3rd one is harder to code but it's just code anyway.

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

      Nevermind, I misread the task as every student follows a teacher. Okay. I take my complaint back.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Looking at standings not having red color on your flag is already gg

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    We don't need anything complicated in C-easy. We only need to check if a point is under a plane defined by three points. This can be done with a matrix determinant.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

Let me whine a little bit...

This year I got 51 points and 30th place. In last minutes I tried coding small C, but lacked something like 1 or 2 minutes and that would guarantee me place in finals. Half a minute before start of competition my computer got some fatal error and I needed to restart it what lasts ~3 minutes (however I read A's statement on phone, but it was distracting either way).

Last year when solving A I panicked and submitted solution that I was not sure about because I forgot that in GCJ time penalty is max not sum, so I could have solved that one later without any consequences. After solving all the rest (except large D) for half an hour only thing I could do was seeing how I am falling in standings finishing somewhere around ~30th place. In that half an hour I would be able to fix my A dozen of times (it lacked one line).

It seems that me and GCJ is not a very fortunate connection.

EDIT: Great, I have just commented out one stupid line in my solution to D and it passed large test xD ( ͡° ͜ʖ ͡°)

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

    I remember once the 34th person qualified, but last year even the 28th person didn't qualify, so you'll be nervous for a while.

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

    Is it "ignore self-loop" on construction of a dual graph? It was my stupid line.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      I guess that it you take any AC you can add to it a stupid line in many places :p. Mine was ignoring spanning tree's edges when deciding whether I can build some non-tree edge.

      → Reply
»
7 years ago, # |
  Vote: I like it +87 Vote: I do not like it

xd

I've started 20 minutes late because of terrible Internet connection in a train, and later I was rarely able submit. Maybe it's good not to look at the standings and to implement some problems first without submitting anything.

Two hard geometry problems, keep it up GCJ!

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can anyone challenge the following solution for D-small?

First, we rotate all points by a random angle, now we can assume that all points have different x-coordinates. For a segment connecting (x1, y1) and (x2, y2) (x1 < x2), assign the pair (x1, atan2(y2 - y1, x2 - x1)). Sort the segments using this pair.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    0 -5 5 0
    0 5 5 0
    0 -5 5 0
    4 0 5 0
    5 0 6 1

    Assume you rotate it by an extremely small angle. Then you will close a triangle (0,  - 5), (0, 5), (5, 0) before doing the two other segments (one of them is inside, one is outside the triangle).

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

      Thank you! I thought this way we can always find one of the outmost remaining segments, but it fails with your case.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        The editorial says: "Each way has its own pros and cons, but many of them also have the property that the reverse of the ordering they produce is also a valid ordering.". I realized that for my solution this property doesn't hold. We should always use the reverse order, and it passed in practice room (to handle K = 2, try various angles for the initial rotation).

        → Reply
»
7 years ago, # |
  Vote: I like it +62 Vote: I do not like it

The input limit of "Name-Preserving Network" problem is actually tight.

I wrote a program that uses Graph Isomorphism as labeling scheme after the contest. I found no solution for n in {5,6,7,8,9}. I tested all possible degree=4 graphs. The number is pretty small, only 1024380 (OEIS) for n=9.

n=10 was the smallest possible size.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    But for n=10 first random graph I generated worked

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +8 Vote: I do not like it

      Right, for n=10, the probability seems pretty good. When I tested n=10, more than 20% of the random graphs were positive.

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    This fact was quite an issue for me during the contest. Indeed I was testing my program with N=6 and it could not create a random graph without symmetries (as such a graph does not exist). Then, changing N from 6 to 10 made it work smoothlessly and only now I do understand why.

    Btw, very nice task!

    → Reply