| | In this problem you will be given a large graph formed by a random process. You will then be asked to find a series of subgraphs of ever-increasing size. Your task is to answer as many queries as possible before time runs out.
An undirected graph G = (V,E) is defined by a set of vertices, V, indexed from 0 to N-1 and a set of edges (u,v). As the graph is undirected, each edge will be listed in both directions. An induced subgraph H of G is defined by a subset of vertices V' and all of the edges in E where both u and v are in V'. See Wikipedia for a more rigorous definition.
In the induced subgraph isomorphism problem, you are given two graphs: a graph G with N vertices, and a graph H with K vertices. Your task is to find a mapping f() from 0..K-1 to 0..N-1 such that (u,v) is an edge in H if and only if (f(u), f(v)) is an edge in G. Again, see Wikipedia for a formal definition.
In this problem, you will be given a graph G, followed by a series of smaller graphs H5, H6, H7, ... (starting from H5 intentionally). Hi will be an induced subgraph of G on i vertices. For each such query, you should return a int[] with i elements, where element j of your return represents f(j) above.
Each graph input will be formatted as a single int[]. The first element of the array will give the number of vertices. The degrees of the nodes will then be listed one at a time, along the their lists of neighbors. Thus, the following pseudocode will decode the input:
ptr = 0
vertices = input[ptr++]
for (i = 0; i < vertices; i++)
degree = input[ptr++]
for (j = 0; j < degree; j++)
createEdge(i, input[ptr++])
where createEdge(u,v) creates an edge in whatever data structure you choose to use.
Scoring
You will be given 10 seconds of total execution time. A function initialize will take the large graph G, and should return an integer (it doesn't matter what you return here). A function query will then be called repeatedly, starting with H5. Your 10 seconds includes the time spent in these functions (both initialize and query). Your query function will be called until you either run out of time, or give an incorrect return (one that isn't a match, or isn't valid). Your score for each test case will simply be the number of queries answered correctly before time runs out (or an incorrect return). Your overall score for all test cases will be the sum of your scores on all the individual test cases.
Test Generation
The graph G will be generated by first picking three values: N, alpha, and D. N will be chosen uniformly at random in [1000,20000]. Alpha will be a floating point number uniformly at random in [1,3). D will be an integer chosen uniformly in [2,30].
For vertex i, a location (xi,yi) will be chosen with xi and yi each integers in [0,220). For each vertex i, we will then generate D undirected edges (i,j). Given a choice of i, each j will be chosen with probability proportional to (1+dist(i,j))-alpha, where dist(i,j) = sqrt((xi-xj)2 + (yi-yj)2). The choices of j will be made with replacement, so the same j may be chosen multiple times. After all selection are made, duplicates are eliminated, leaving a simple undirected graph.
To select each Hi, a seed vertex u will be chosen uniformly at random from the N vertices in G. All neighbors of u will be added to the set of frontier vertices. Then, a node is chosen randomly from the set of frontier vertices and all of its neighbors are added to the frontier. A node added to the frontier multiple times will have multiple chances to be selected (making the frontier a multiset). This process is repeated until i vertices are chosen. If the frontier set becomes empty before i vertices have been selected, the select process is restarted from scratch. Finally, the subgraph is extracted and the vertex labels are randomly shuffled.
Offline Tool
An offline testing tool is provided here. |