GOODGAL - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak

DIFFICULTY:

HARD

PREREQUISITES:

Graphs

PROBLEM:

You are given a graph and you have to decide if it is a halved cube graph which is a subgraph of hypercube graph formed by connecting pairs of verices at distance exactly two from each other in the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph.

CHARACTERIZATION

Let Qd be a hypercube of order d and let Hd be a halved cube of order d.

Let’s consider a hypercube graph Qd first. Qd has n = 2^d vertices and there is a very handful way of defining it. Let vertices of Qd be the set of all binary strings of length d. We connect two vertices if and only if their corresponding binary strings differ by exactly one bit. Based on this definition, it is easy to see that Qd is a d-regular graph with 2^d-1 * d edges and diameter d.

Let’s consier a vertex v of Qd. In order to know how to form a halved cube, we want to know how many vertices are at distance exactly two from v. Our handful definition shows that there are binomial(d, 2) vertices at distance two from v, because there are binomial(d, 2) binary strings different on exactly two bits from the string assigned to v.

You can try to construct one such graph it by hand. For example H3 is a complete graph over 4 vertices.

QUICK EXPLANATION:

You can implement the algorithm described in this paper.

EXPLANATION:

All fact below are based on the paper. I don’t give here a complete solution, because it is well presented in the paper.

You can assume that d >= 5, because we can recognize every Hd for d < 5 which is really easy.

It is known than Hd has 2^(d-1) cliques of size d.

Here is a sketch of the algorithm:

The algorithm works in steps:

Input: graph G on n vertices

  1. We identify all cliques of size d in G
  2. We construct a new graph G’ in the following way. For any cluque C found in step 1, we add a new vertex and join it to every vertex of C. The edges added in this process are all edges of G` - we remove all old edges of G at the end.
  3. We check if G` is a hypercube. If it is, G is a halved cube, otherwise G is not a halved cube.

Paper describes every step with all details. In order to understand the logic behind the construction in step 2 let’s consider any clique C. If G is a halved cube graph, then all pairs of vertices in C are at distance 2 in the corresponding hypercube graph. Based on this fact, it is easy to see that in there must be a vertex u in Qn such that u is as distance 1 from any of vertices in C. Please check the paper for more details.

AUTHOR’S AND TESTER’S SOLUTIONS:

To be uploaded soon.

RELATED PROBLEMS:

To be uploaded soon.

2

I think most people (including me!) were lucky to get away with just checking if the graph was ( (d choose 2), 2^(d-1) )-regular and checking that the size of intersection of the neighborhood’s of every pairs of points was 2*(d-2). But awesome question, and well written up as well :slight_smile:

3

I’m the author of this problem. I noticed the fact that wrong solutions passed with checking just 2*(d-2) property during the contest. I tried to generate tests against these solutions. I used brute-force with some heuristics to find graphs with necessary d-regularity property and this 2*(d-2) property. Brute-force found ~30 000 graphs with N=16 and all of them were halved-cubed graphs. Unfortunately it wasn’t enough fast to find at least one graph with these properties where N=32. So I didn’t managed to generate tests against this simple heuristic and still have no idea what is the smallest value of N where a contrtest can be found.
So it would be nice if someone had ideas how to find a contrtest against this heuristic and shared with us.

1 Like
4

Hopefully there is someone and then you can add this test in practice :wink:

5

I also used the fact of the binary strings :slight_smile:

Original graph:

  • give all nodes a number from 0 to (2^n)-1
  • connect all numbers which differ exactly 1 bit
  • Why is this true? The size of the graph at each step is doubling in size, and each vertex has exactly one edge to the new half. Try this on paper if you don’t get this.

Graph after passing commet (good galaxy):

  • The graph is now splitted in 2 parts by bit parity (0, 3, 5, 6, …) (1, 2, 4, 7, …)
  • connect all numbers which differ exactly 2 bits
  • Why is this true? If you’ve got the previous part, you can see the same here. We are connecting all vertices on a distance of 2.

Algorithm:

  • Do some quick checks (size of N, size of M, …)
  • assign 0 to one of the vertices, and bfs this value to all other vertices in the graph as a constraint. E.g. a vertex at distance 2 will differ 4 bits from zero.
  • take a next vertex and according the constraints so far, set the first possible number.
  • If you can assign all numbers, your graph is a good galaxy.

Although it’s sure, the graph is a good galaxy if all numbers are getting assigned.
The opposite is not true. Due to the original sequence, we may assign the wrong number at some stage.
And this may give incorrect, while it is a good galaxy.

I solved this by just trying 2 different sequences and this worked for me.
I’m sorry that this is not fully correct, but I thought that was the trick.
As long as the probability of passing is high enough.

1 Like
6

I found the paper mentioned about an hour from the point when I read the question, got AC after 7 days. In retrospect, I should have figured out the mistake waaaaaay earlier.

The given test input has got an empty line between each case which I was taking in accordingly, but it is not there in the hidden test cases, so I was essentially ignoring one line of input. An extra empty line doesn’t matter in C, C++. It does in Python. :expressionless:

By the time I figured out the problem, I didn’t have much time to form the whole solution, tried just the 2*(d - 2) constraint and it worked. :smiley:

I also tried the bit assignment approach. Assigned d-bit numbers to all nodes such that the hamming distance between adjacent nodes should be 2. Unfortunately, that was while I was taking input incorrectly so I am still not sure if that approach would have worked, gonna have to try that out later.

1 Like
7

what i did was:

in order to be a good galaxy, a galaxy must satisfy the following:

1)no. of planets should be equal to a power of 2. let this power be p.

  1. each planet should be directly connected to p*(p+1)/2 other planets.

  2. all the planets should form a single connnected group

  3. and the graph so formed should be a strongly regular graph.( for this property, i checked that every 2 directly connected planets should have equal number of neighbours)
    This approach worked fine for me (although i am not able to understand the terms given in the editorial)