The following is a description of a constructive solution to the Name-Preserving Network problem from round 3 of the 2018 Code Jam.
I was unfortunately unable to fully debug my code within the duration of the contest, but after the end, I was able to fix the code and get it working. I spent a while working around trying to put K_4's and K_3's (Complete graphs with 4 and 3 vertices respectively) together, then realized that most ways I tried to put them together, there would be two vertices that could be swapped and change nothing about the graph. I tried to draw things out in a manner that made things somewhat easier. (I did this with the K_3's and K_4's by just representing them as their outer edges, rather than drawing their inner edges.) While drawing graphs on paper, I came upon a sort of 'arm' structure (See image), that was fairly easily extendable, so I set about trying to uniquely identify sides of an arm. I then ended up drawing two arms on top of each other, and happening upon the following method of linkage, which guarantees only one vertex has its neighbors linked in the manner the vertex labeled '1' is. This allowed me to determine what the vertex labeled '1' was relabeled as regardless. It was then possible to 'grow' the arms as needed to get them to the right length. I then fixed the size of one of the arms, and let the other one vary to accommodate the desired size, anything at least 10. The resulting solution came out as in the link below for the graph. https://imgur.com/sUiO7i2 I'll leave the code out, as it's an interesting exercise, but should be fairly straightforward. The code runs in linear time, and is not dependent on randomness. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/871c8923-9a30-4d5d-a76a-cd0935a4c619%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
