Wednesday, July 25, 2018

A week without automorphisms

The Jun 11 - Jun 17 week was supposed to present the last chance to qualify for further TopCoder Open 2018 rounds in Round 2B (problems, results, top 5 on the left, parallel round resultsanalysis). However, because of technical issues an extra Round 2C was added two weeks later. Those issues notwithstanding, congratulations to gs14004 on creating just enough cushion during the coding phase to withstand the challenge push from maroon_kuri, sky_love_high and FizzyDavid! sky_love_high in particular actually had 1262.53 points after four minutes of the challenge phase, which would be enough for the first place.

Codeforces had its own share of issues with Round 488 on Saturday (problems, results, top 5 on the left, analysis), this time not technical but with an incorrect reference solution for the hardest problem. It turned out that the test data was luckily correct anyway, so this ended up being a somewhat theoretical discussion that did not affect the round. Congratulations to Um_nik and Errichto on solving all problems!

In my previous summary, I have mentioned an exciting Code Jam problem. You are given a number n between 10 and 50, and need to print a connected simple undirected graph with n vertices, and each vertex having degree exactly 4. The interactor will then randomly permute the vertices of your graph and give it back to you, and you need to then restore the permutation that was used. In other words, you need to find such graph without automorphisms, and be able to identify its vertices after they're shuffled.

This is another example where there are two main ways: either solve it "on paper", or try various random-looking things at the computer until one works. Since there are only 41 possible inputs, it's quite easy to verify if an approach works or not.

It turns out that in this problem even the expected solution went the random way. First, we have to come up with a way we'll use to identify the vertices. Then, we'll try random connected graphs with all degrees equal to 4 until we can uniquely identify all vertices in one. Of course, this last step also requires some way of generating such graphs.

As a way to identify the vertices, we can use an iterative approach: initially all vertices start with the same label. Then we compute some function for all vertices that depends on the existing labels and the structure of the graph, but does not change when we permute the vertices. In case the values of the function for some vertices is different, we can update their labels to be different, and repeat the process. Eventually we need for all labels to become different.

The function we compute can't just depend on the neighbors of the node: since every node has exactly 4 neighbors, and initially they all have the same values, we will never get different function values. However, we can look further and for example check how many of those 4 neighbors are connected to each other, or what set of labels we have at distance 2,3,... from the vertex, and then one of those ideas will be enough to find a solution for all 41 possible testcases (see the official analysis for more details).

Finally, in order to quickly generate such graphs, we can also use various approaches. I find the following one the most logical: start with any such graph, and then repeatedly apply random local modifications that don't change the degrees of the vertices (again, check out the official analysis for more details).

I have also enjoyed the way this problem used the interactive problem paradigm to encode the "challenge-response" setup that is not usually seen in programming contests.

Thanks for reading, and check back for more!

2 comments:

  1. Dear Sir,
    Could you please tell me how to good at competitive programming.I am a newbie in this arena.
    Please sir , reply this!

    ReplyDelete
  2. Dear Sir,
    Could you please tell me how to good at competitive programming.I am a newbie in this arena.
    Please sir , reply this!

    ReplyDelete