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.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | jiangly | 3578 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | tourist | 3565 |
| 8 | maroonrk | 3531 |
| 9 | Radewoosh | 3521 |
| 10 | Um_nik | 3482 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 8 | SecondThread | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.05.2024 09:17:16 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
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?
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.
Google Geometry Jam 2018
Btw, how to solve C?
Even the first one is sort of geometry:))
https://codejam.withgoogle.com/2018/challenges/0000000000007707/analysis/000000000004b90d
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?
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.
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
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.
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!
We just need two points and you can take arbitrary edge of a convex hull when projected onto OXY plane.
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..
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.
Finding out the bounding rectangle of 2D points -- 14 points. Finding out line and plane intersection in 3D -- 7 points.
ggwp.
I don't know how to prove the first one, but I know how to prove the brute for the third one:))
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.
Nevermind, I misread the task as every student follows a teacher. Okay. I take my complaint back.
Looking at standings not having red color on your flag is already gg
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.
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 ( ͡° ͜ʖ ͡°)
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.
Is it "ignore self-loop" on construction of a dual graph? It was my stupid line.
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.
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!
Congratulations!
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.
0 -5 5 00 5 5 00 -5 5 04 0 5 05 0 6 1Assume 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).
Thank you! I thought this way we can always find one of the outmost remaining segments, but it fails with your case.
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).
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.
But for n=10 first random graph I generated worked
Right, for n=10, the probability seems pretty good. When I tested n=10, more than 20% of the random graphs were positive.
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!