Google Code Jam 2022 — Qualification Round
source link: http://codeforces.com/blog/entry/101509
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By kostka,
29 hours ago,
The Code Jam Qualification Round has officially begun! → goo.gle/cj2022
You've got until 02:00 UTC on April 3 to register AND score enough points (at least 30) to advance to Round 1.
Registration closes at the end of the round!
22 hours ago, # |
lol they actually implemented Punched Card Python. I'm curious if anyone used it to solve a problem.
-
I sent a e-mail to them on 20th November 2021, requesting to add
-freleaseoption to their GDC compiler command line:SpoilerThey thanked me for my feedback, but did nothing. Now I know that they were too busy implementing this Punched Card Python thingie... Because priorities do matter.
22 hours ago, # |
Hey, are you guys also facing the same problem for Twisty little passages ? My code passes well above required in the testing tool but gives wrong answer while submitted.
-
Yep, it looks like the testing tool does indeed test, but only with graphs of a certain structure, unlike with system tests. You can see how I handled this at 1:25:25 in my screencast/solution video which will be available as soon as the contest ends.
10 hours ago, # |
Is there system testing? I have enough points to make round 1 if everything passes, and I'm too tired to get more than that.
10 hours ago, # |
Is there still an opportunity to somehow edit the list of users one's following? If I remember correctly, there was a star-like button in standings, but now I see no things like that.
-
Just below your name where the search button is, click in to the search space and wait for a pop up menu. Then click on following. You'll have a list of all your starred participants.
-
My question was about editing that list, i. e. how to add a new user to it.
-
Search for the person's name the same place you search for countries and then click the star beside the persons name to add to your list.
-
-
So, I solved Twisty Little Passages by an intutive guess. It appears to be correct since the analysis lists it as a correct approach, but doesn't help in proving the correctness since it offers no proof as to why its works:
My idea is to perform the following k2k2 times:
- Teleport to a random node we haven't teleported to before.
- Walk to one adjacent node.
Then the guess is (2nk⋅(sum of degrees for teleport nodes))+sum of degree of walk nodes that haven't been reached by teleport(2nk⋅(sum of degrees for teleport nodes))+sum of degree of walk nodes that haven't been reached by teleport.
My intuition for this was that:
- Randomly chosen teleport nodes represent the average, makes sense to scale them.
- If a few larger degree nodes exist, they are way more likely to be selected by walks, so it doesn't make sense to scale them.
- Since the error is relative, a few smaller degree nodes barely matter at all.
But I have zero clue how to prove anything about that the accuracy or precision of this heuristic.
I even ignored this idea at first and left the contest since I didn't think this would work, only coming back to code and submit it 12 hours later when I was far more bored.
-
My solution was slightly different, but using same ideas.
- Rather than walking one room and then teleporting away, I kept walking until I visited 2 rooms I already was in in a row.
- I actually didn't differentiate between how I reached the node when I learned its degree. So to accomodate large-degree nodes, I took median instead of average.
On the proof, I had flashbacks to my Master's degree's thesis in sublinear algortihms. For example if you want to tell with a certain confidence whether the graph is bipartite, it can be proven that if you choose a specific sublinear size sample of nodes and check whether the sample graph is bipartite or not, you can actually prove that that answer will hold for the whole graph with certain probability.
So I had a hunch that you just need to sample, and the fact that they gave us walks was a big hint.
Although I imagine there's certain element of luck to it and some sensible ideas probably wouldn't work in reality.
-
Section 3 of this paper gives a solution to this exact problem. It is indeed very similar.
Here's my solution to Twisty Little Passages:
First note that if N<=KN<=K then we can visit all the rooms, and calculate that the number of passages is exactly (sum of degrees) / 2.
Now if K<NK<N, if we know the average degree DavgDavg then the answer is Davg∗N2Davg∗N2. How can we estimate DavgDavg? An initial approach is to teleport to KK random rooms, and guess that DavgDavg is the average of degrees of the visiteed rooms. However, this will not work well for a 'star' input, with one vertex of degree 99999, and 99999 vertices of degree one. (In general, it doesn't work well for graphs where most vertices have 'low' degree, and very few vertices have 'high' degree, because the few high-degree vertices can have an impactful shift on the average degree yet not make it into our calculation.)
So we save a few (I used 50) commands just for finding the ultra-high degree vertices. Note that if most vertices have low degree, but a few have high degree, we are likely to find one of the high-degree vertices by just walking from a random node. Here is the algorithm sketch:
- Visit 7950 random points, and let their degree average be DavgDavg and max degree be DmaxDmax.
- Set S = 0, it is the sum of degrees of ultra-high-degree vertices, which we define as vertices with degree > DmaxDmax.
- When visiting the last 50 of our initial random points, do one "W" command. If any of these hit a previously unseen vertex with ultra-high degree, add its degree to SS. Let UU be the number of ultra-high-degree vertices seen.
- Final guess is S+Davg∗(N−U)2S+Davg∗(N−U)2.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK