Google Code Jam 2018 round 3

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

6 лет назад, # ^ |

+13

Even the first one is sort of geometry:))

→ Ответить

jonathanirvings

6 лет назад, # ^ |

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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?

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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!

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

ko_osaga

6 лет назад, # ^ |

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..

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

eduardische

6 лет назад, # |

+24

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

ggwp.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

kalimm

6 лет назад, # ^ |

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.

→ Ответить

eduardische

6 лет назад, # ^ |

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

→ Ответить

Coder

6 лет назад, # ^ |

+20

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

→ Ответить

Errichto

6 лет назад, # ^ |

+18

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.

→ Ответить

6 лет назад, # |

← Rev. 2 →

+25

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 ( ͡° ͜ʖ ͡°)

→ Ответить

6 лет назад, # ^ |

+10

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.

→ Ответить

snuke

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

+23

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.

→ Ответить

Errichto

6 лет назад, # |

+87

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!

→ Ответить

Gassa

6 лет назад, # ^ |

+46

Congratulations!

→ Ответить

6 лет назад, # |

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 (x₁, y₁) and (x₂, y₂) (x₁ < x₂), assign the pair (x₁, atan2(y₂ - y₁, x₂ - x₁)). Sort the segments using this pair.

→ Ответить

Errichto

6 лет назад, # ^ |

← Rev. 2 →

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).

→ Ответить

6 лет назад, # ^ |

+10

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

→ Ответить