Time Limit: 30 sec / Memory Limit: 1024 MB
問題文
頂点集合 V 、辺集合 E よりなるグラフを G=(V,E) と書く。二つのグラフ G=(V,E) と G_{emb}=(V_{emb},E_{emb}) が与えられている。 下記制約のもとで、以下で説明する得点ができるだけ高くなるように、 V のすべての要素に対し V_{emb} の頂点の部分集合を対応させよ。 なお、 G_{emb} は以下の図で示すような、一行に含まれる頂点数と一列に含まれる頂点数が等しい正方形型の King's Graph である。King's Graph の頂点の番号付けについては、 左上が 1 であり、以降左から右に順に番号を振り、行末に到達したときは次の行から同様に順に番号を振るものとする。
得点計算について
各テストケースの得点およびこの問題の得点は、以下のように計算する。
- 以下では V の i 番目の頂点に対応する V_{emb} の部分集合をs(i) ⊂ V_{emb} とする。初期の持ち点 5000 点に以下のように加点または減点することで各テストケースの得点を計算する。
- グラフ G の各辺 (u,v) \in E に対し、s (u) に属する頂点 a \in s (u) と s (v) に属する頂点 b \in s (v) が存在し、それらがグラフ G_{emb} の辺で結ばれている、すなわち (a,b) \in E_{emb} であるとき、100 点を加点する。
- グラフ G のすべての辺 (u,v) \in E に対し 100 点加点されたとき、さらに 100000 点をボーナス点として加点する。ただし、すべてのテストケースについてボーナス点が獲得できる入力であることは保証されていない。
- 上の合計点から ∑ _{u \in V} (|s(u)|-1) 点を減点したものが、各テストケースの得点となる。
- 以下の条件のいずれかに該当する場合は 0 点となる。
- グラフ G_{emb} から、部分集合 s(i) ⊂ V_{emb} に含まれない頂点とそれに隣接する辺を全て削除してできたグラフが連結とならないものが存在する(下図の赤色の四角を参照)。
- 異なる 2 つの部分集合 s(i), s(j) (i \neq j) において、共通部分が空でないものが存在する(下図の青色と紫色の四角を参照)。
- 部分集合が空であるもの、すなわち |s(i)| = 0 となるような部分集合 s(i) が存在する。
- 実行制限時間またはメモリを超過する、ないしは出力が正しい出力フォーマットに従っていない。
- テストケースは全部で 30 個あり、各テストケースの得点の合計がこの問題の得点となる。
- コンテスト終了後にシステムテストを行い、この 30 個とは別のジャッジデータ 150 個に対する得点の合計が最終得点となる。
入力
入力は以下の形式で標準入力から与えられる。入力はすべて整数値である。
|V| |E| u_1 v_1 u_2 v_2 : u_{|E|} v_{|E|} |V_{emb}| |E_{emb}| a_1 b_1 a_2 b_2 : a_{|E_{emb}|} b_{|E_{emb}|}
- |V| と |E| はグラフ G の頂点の数と辺の数を表す。
- u_i, v_i はグラフ G の辺についての情報であり、頂点 u_i と頂点 v_i が辺で接続されていることを表す。
- |V_{emb}| と |E_{emb}| はグラフ G_{emb} の頂点の数と辺の数を表す。
- a_i, b_i はグラフ G_{emb} の辺についての情報であり、頂点 a_i と頂点 b_i が辺で接続されていることを表す。
グラフ G についての制約
- 2 \leq |V| \leq 5 \times 10^2
- 1 \leq |E| \leq min ( \frac{|V| \times (|V|-1)}{2}, 2 \times 10^4 )
- 1 \leq u_i \lt v_i \leq |V|
- i \neq j ならば、 u_i \neq u_j または v_i \neq v_j
- 与えられるグラフは連結である。
グラフ G_{emb} についての制約
- G_{emb} は正方形の King's グラフである。
- 4 \leq |V_{emb}| \leq 3.6 \times 10^3 かつ |V_{emb}| は平方数
- |V| \leq |V_{emb}|
- 1 \leq a_i \lt b_i \leq |V_{emb}|
出力
出力は以下の形式で標準出力に |V| 行で出力せよ。
n_1 x_{1,1} x_{1,2} ... x_{1,n_1} n_2 x_{2,1} x_{2,2} ... x_{2,n_2} : n_{|V|} x_{|V|,1} x_{|V|,2} ... x_{|V|,n_{|V|}}
- n_i は V の i 番目の頂点に対応する V_{emb} の部分集合の要素数 |s (i)| である。
- x_{i,j} は V の i 番目の頂点に対応する V_{emb} の部分集合の j 番目の要素である。
出力についての制約
- 出力は |V| 行からなる
- 1 \leq n_i
- 1 \leq x_{i,j} \leq |V_{emb}|
- i \neq j または k \neq l ならば x_{i,k} \neq x_{j,l}
グラフ G の生成について
すべてのテストケースについて、与えられるグラフ G は「ランダムグラフ」である。 これははじめに、 |V| 頂点からなる木をランダムに生成し、その後 |E| - |V| + 1 回ランダムに辺を張ることで生成される。詳細はサンプルコードをご覧ください。
入力例 1
7 14 1 2 1 3 1 6 1 7 2 4 2 5 2 6 2 7 3 5 3 7 4 5 4 6 4 7 5 7 25 72 1 2 1 6 1 7 2 6 2 3 2 7 2 8 3 7 3 4 3 8 3 9 4 8 4 5 4 9 4 10 5 9 6 7 6 11 6 12 7 11 7 8 7 12 7 13 8 12 8 9 8 13 8 14 9 13 9 10 9 14 9 15 10 14 11 12 11 16 11 17 12 16 12 13 12 17 12 18 13 17 13 14 13 18 13 19 14 18 14 15 14 19 14 20 15 19 16 17 16 21 16 22 17 21 17 18 17 22 17 23 18 22 18 19 18 23 18 24 19 23 19 20 19 24 19 25 20 24 5 10 10 15 15 20 20 25 21 22 22 23 23 24 24 25
出力例 1
3 14 15 20 1 19 1 9 1 23 1 18 1 25 1 13
この出力例では、入力グラフ G の各頂点に対して、V_{emb} の部分集合は以下の図で対応付ける。すなわち、入力グラフの頂点の番号を v_1 から v_7 としており、各頂点に対応する V_{emb} の部分集合 s は、それぞれ同じ色で囲まれている。
出力例 1 で V_{emb} に対応付けられた結果、得られる得点は以下のように計算される。
- 基本得点として 5000 点を加点する。
- グラフ G_{emb} において保持されている辺に対して 11 \times 100 = 1100 点を基本得点に加点する。 例えば、グラフ G の辺 (v_1, v_7) において、 v_1 に対応する V_{emb} の部分集合 s(v_1) の元である G_{emb} の頂点 14 と、 v_7 に対応する V_{emb} の部分集合 s(v_7) の元である G_{emb} の頂点 13 との間に辺 (13, 14) が存在する。 従って、辺 (v_1, v_7) はグラフ G_{emb} において保持されており、 100 点を加点する。一方、辺 (v_3, v_5) に対しては、各頂点に対する部分集合 s(v_3) と s(v_5) の間に辺が存在しないため、その辺に対して 100 点を加点しない。 これをグラフ G のすべての辺に対して見たとき、保持された 11 個の辺に対しては加点されるが、図の赤の×印で示すように、保持されなかった 3 個の辺に対しては加点されない。
- グラフ G の辺で保持されていないものがあるため、ボーナス点 100000 点は加点されない。
- 各部分集合 s(v_1) から s(v_7) の要素数に対して、(3-1) + (1-1) + (1-1) + (1-1) + (1-1) + (1-1) + (1-1) = 2 点を減点する。各括弧内の最初の項は、各部分集合の要素数を示し、ここで s(v_1) は 3 個の要素数を持つため、2 点が減点される。
以上のことから、合計 6098 点がこのテストケースに対する得点となる。
入力例 2
10 30 3 10 3 6 5 10 5 8 2 6 2 7 1 5 1 9 4 10 5 7 4 6 2 8 1 2 7 10 2 4 1 3 7 8 1 8 6 9 2 9 1 4 2 10 2 3 6 10 8 10 6 8 5 6 3 8 7 9 4 9 16 42 1 2 1 5 1 6 2 5 2 3 2 6 2 7 3 6 3 4 3 7 3 8 4 7 5 6 5 9 5 10 6 9 6 7 6 10 6 11 7 10 7 8 7 11 7 12 8 11 9 10 9 13 9 14 10 13 10 11 10 14 10 15 11 14 11 12 11 15 11 16 12 15 4 8 8 12 12 16 13 14 14 15 15 16
出力例 2
1 5 2 7 10 1 1 1 2 1 12 1 6 1 15 1 9 1 4 4 3 8 11 14
この入力例を図示したものは以下の通りである。
ジェネレータとテスターおよび参考文献
- この問題のジェネレータおよびテスターはここからダウンロードできる。
- この問題を解くにあたって、以下の文献を参考にしながら解答を作成しても良い。
J. Cai, et al., "A practical heuristic for finding graph minors", arXiv:1406.2741 [quant-ph]
Problem
In what follows assume we are given two graphs. The first graph G=(V, E) consists of a set of vertices V and edges E. The second graph G_{emb} = (V_{emb}, E_{emb}) also consists of a set of vertices V_{emb} and edges E_{emb} and shall be a square King's Graph, with vertices labeled from left to right and top to bottom, as illustrated in the figure below. The task is to find a map s which assigns each vertex i\in V to a subset of vertices s(i) ⊂ V_{emb} such that:
- For any vertex i \in V the subgraph induced by s(i) in G_{emb} is connected;
- The subsets s(i), s(j) ⊂ V_{emb} are mutually exclusive, i.e., for any i,j \in V with i\neq j we have s(i)∩ s(j)=Ø;
- For any vertex i \in V the subset s(i) must not be empty.
Score
For each run of your algorithm on a single input graph, the score obtained by the resulting map s is evaluated as follows:
- An initial score of 5000 points is assigned.
- We add 100 points to the initial score for each edge (i,j) \in E, if the corresponding vertex sets s(i), s(j) ⊂ V_{emb} are connected by at least one edge of the King's graph G_{emb}.
- We add a bonus of 100000 points, if the algorithm finds a map s such that for every edge (i,j)\in E, the corresponding vertex sets s(i), s(j) ⊂ V_{emb} are connected by at least one edge of the King's graph G_{emb}. Note that finding a map s which obtains the bonus score may not be possible on every input graph.
- Large clusters are penalized by subtracting ∑ _{u \in V} (|s(u)|-1) points from the score.
- The score becomes 0 in any of the following cases:
- If the subgraph induced by any of the vertex sets s(i) in G_{emb} is disconnected. See Example 1 in the figure below.
- If the vertex sets of s(i), s(j) are not mutually exclusive, i.e., if any of the vertex sets with (i \neq j) overlap on some element. See Example 2 in the figure below.
- If the subset s(i) is empty, i.e., |s(i)| = 0.
- Furthermore, any run of your algorithm which exceeds either the time or the memory limit will not contribute to your final score. The same is true for any output, which violates the output format specified below.
- For the period of the contest we will evaluate your score, by running your algorithm on 30 input graphs G and adding up the corresponding score. This will allow for a preliminary estimate of your rank.
- After the contest has finished your final score and rankings will be determined by running your final submission on 150 previously undisclosed input graphs.
Input
Inputs are given in the following format through the standard input. All the inputs have integer values.
|V| |E| u_1 v_1 u_2 v_2 : u_{|E|} v_{|E|} |V_{emb}| |E_{emb}| a_1 b_1 a_2 b_2 : a_{|E_{emb}|} b_{|E_{emb}|}
- |V| and |E| denote the total number of vertices and edges of the graph G, respectively.
- The line u_i, v_i means that the vertex u_i and the vertex v_i of the graph G are connected.
- |V_{emb}| and |E_{emb}| denote the total number of vertices and edges of the graph G_{emb}, respectively.
- The line a_i, b_i means that the vertex a_i and the vertex b_i of the graph G_{emb} are connected by an edge.
Constraints on the Graph G
- 2 \leq |V| \leq 5 \times 10^2
- 1 \leq |E| \leq min ( \frac{|V| \times (|V|-1)}{2}, 2 \times 10^4 )
- 1 \leq u_i \lt v_i \leq |V|
- For any pair i \neq j, we have that either u_i \neq u_j or v_i \neq v_j.
- The graph G is connected.
Constraints on the Graph G_{emb}
- G_{emb} is a square King's graph.
- 4 \leq |V_{emb}| \leq 3.6 \times 10^3 and |V_{emb}| is a square number.
- |V| \leq |V_{emb}|
- 1 \leq a_i \lt b_i \leq |V_{emb}|
Output
Output should be in the following format consisting of |V| lines and should be processed through the standard output.
n_1 x_{1,1} x_{1,2} ... x_{1,n_1} n_2 x_{2,1} x_{2,2} ... x_{2,n_2} : n_{|V|} x_{|V|,1} x_{|V|,2} ... x_{|V|,n_{|V|}}
- The index i in n_{i} denotes the i-th vertex of graph G.
- n_{i} denotes the total number of vertices in s(i)⊂ V_{emb}, assigned to the i-th vertex of graph G.
- x_{i,j} denotes the j-th element of subset s(i), which is assigned to the i-th vertex of graph G.
Constraints for the Output
- Output should consist of |V| lines.
- 1 \leq n_i
- 1 \leq x_{i,j} \leq |V_{emb}|
- i \neq j or k \neq l implies that x_{i,k} \neq x_{j,l}
How are the Input Graphs G Generated
For evaluating your final score, we will run your algorithm on random input graphs G. These graphs are generated as follows: First, a tree with |V| vertices is generated randomly. Subsequently, |E| − |V| + 1 edges are randomly added to the tree. For details see the sample code.
Input Example 1
7 14 1 2 1 3 1 6 1 7 2 4 2 5 2 6 2 7 3 5 3 7 4 5 4 6 4 7 5 7 25 72 1 2 1 6 1 7 2 6 2 3 2 7 2 8 3 7 3 4 3 8 3 9 4 8 4 5 4 9 4 10 5 9 6 7 6 11 6 12 7 11 7 8 7 12 7 13 8 12 8 9 8 13 8 14 9 13 9 10 9 14 9 15 10 14 11 12 11 16 11 17 12 16 12 13 12 17 12 18 13 17 13 14 13 18 13 19 14 18 14 15 14 19 14 20 15 19 16 17 16 21 16 22 17 21 17 18 17 22 17 23 18 22 18 19 18 23 18 24 19 23 19 20 19 24 19 25 20 24 5 10 10 15 15 20 20 25 21 22 22 23 23 24 24 25
Output Example 1
3 14 15 20 1 19 1 9 1 23 1 18 1 25 1 13
The input example 1 from above is visualized in the figure below. The left side shows the input graph with 7 vertices, labeled by indices V1 to V7. The right side shows a King graph of size 5\times5. The map s as specified by the output of example 1 is visualized by colored boxes. For example, the vertex V1 of the input graph is mapped to a set of three vertices on the kings graph.
We now discuss the score assigned to the map s as specified by output example 1:
- The initial score is 5000 points.
- We add 11 \times 100 = 1100 points to the initial score, i.e., 100 points for every edge of the input graph, if the corresponding vertex sets are connected by at least one edge of the King's graph. To this end consider for example the edge between the vertex pair (V1, V2). Clearly, the corresponding vertex sets on the King's graph are connected. Therefore, we add 100 points for this edge. On the other hand, consider the vertex pair (V3, V5). The corresponding vertex sets on the King's graph are not connected. Therefore, this edge does not contribute to the score and we mark it by a red cross. Repeating this procedure for every edge of the input graph, we find that 11 edges of this example score, while 3 edges (as marked by a red cross) do not score.
- The bonus points of output example 1 are 0 because the vertex sets corresponding to some edges of the input graph (as marked by a red cross), are not connected by a direct edge of the King's graph.
- We subtract (3-1) + (1-1) + (1-1) + (1-1) + (1-1) + (1-1) + (1-1)= 2 points, where the first number in each bracket corresponds to the number of elements in each vertex set on the right. Altogether we lose 2 points because the vertex set s(V1) contains three elements.
- Altogether output example 1 scores because the vertex sets s(i) are mutually exclusive and each vertex set s(i) induces a connected subgraph of the King's graph.
Input Example 2
10 30 3 10 3 6 5 10 5 8 2 6 2 7 1 5 1 9 4 10 5 7 4 6 2 8 1 2 7 10 2 4 1 3 7 8 1 8 6 9 2 9 1 4 2 10 2 3 6 10 8 10 6 8 5 6 3 8 7 9 4 9 16 42 1 2 1 5 1 6 2 5 2 3 2 6 2 7 3 6 3 4 3 7 3 8 4 7 5 6 5 9 5 10 6 9 6 7 6 10 6 11 7 10 7 8 7 11 7 12 8 11 9 10 9 13 9 14 10 13 10 11 10 14 10 15 11 14 11 12 11 15 11 16 12 15 4 8 8 12 12 16 13 14 14 15 15 16
Output Example 2
1 5 2 7 10 1 1 1 2 1 12 1 6 1 15 1 9 1 4 4 3 8 11 14
The input example 2 corresponds to the following schematic figure.
Sample Code and References
- Sample code including source code for generating random input graphs and evaluating the corresponding score of your algorithm can be downloaded through the following link.
- For a previous study of the graph embedding problem, see:
J. Cai, et al., "A practical heuristic for finding graph minors", arXiv:1406.2741 [quant-ph]