Time Limit: 30 sec / Memory Limit: 1024 MB
注意
問題文中の数式が正しく表示されない場合は、新システム上のページにアクセスし直してご覧ください。
問題文
0, 1 の値のみを取る変数 X = \left[ x_1, \ldots, x_{N} \right] (x_i \in \left\{ 0, 1 \right\}) を入力とする、以下で示される多変数関数 f を「整数擬似ブール関数」と呼ぶ。
f(X) = f(x_1, \ldots, x_{N}) = H + \sum_{i=1}^{N} p_i x_i + \sum_{1 \leq i < j \leq N} q_{ij} x_i x_j + \sum_{1 \leq i < j < k \leq N} r_{ijk} x_i x_j x_k + \cdots
ここで H, p_i, q_{ij}, r_{ijk}, \cdots は係数であり、係数はすべて整数である。
例えば、f(x_1, x_2, x_3) = 10 + 3x_1 - 8 x_1x_2 + 2x_1x_2x_3 という整数擬似ブール関数の次数は 3 であり、項数は 4 であり、係数の絶対値の最大値 (係数幅)は 8 である (定数項は係数幅の計算時に考慮しないため 10 とはならないことに注意せよ)。係数幅の定義は問題文末尾を参照のこと。
入力として整数擬似ブール関数 f(X) が与えられる。x_1, \ldots, x_N の他に新たに変数 W = \left[ w_1, \ldots, w_{M} \right] (w_i \in \left\{ 0, 1 \right\}) を追加し、さらに以下のように変数 X および W に一対一対応する変数 Y = \left[ y_1, \ldots, y_{N+M} \right] を定義する。
このとき、高々 2 次の整数擬似ブール関数
g(X, W) = g(Y) = g(y_1, \ldots, y_{N+M}) = H' + \sum_{i=1}^{N+M} p_i' y_i + \sum_{1 \leq i < j \leq N+M} q_{ij}' y_i y_j
を生成し、それを出力するプログラムを作成せよ。
生成される関数は以下の条件を満たさなければならない。
- 係数 H', p_i', q_{ij}' はすべて整数である
また、以下の条件を満たすほど得点が高くなる。詳細は「採点方法」の項目を参照のこと。
- 全ての X \in \left\{0, 1\right\}^N に対して f(X) = \min_{W \in \left\{0, 1\right\}^M} g(X, W) を満たす
- しかし、実際にこれを厳密に評価することが困難であるため、このコンテストにおいては「f(X) \leq \min_{W \in \left\{0, 1\right\}^M} g(X, W) であって、f(X) と \min_{W \in \left\{0, 1\right\}^M} g(X, W) との誤差が小さい」アルゴリズムであるほど高く評価するものとする。
- 新しく追加する変数の数 M が少ない
- 関数 g の項の数が少ない
- 関数 g の係数の絶対値の最大値 (係数幅) が小さい
- ある関数 f の「係数幅」とは、f が持つ定数項以外の各項に対する係数の絶対値の最大値を指す。例えば f = 3x - 4xy + xyz + 10 である場合、係数幅は \max \left\{ |3|, |-4|, |1| \right\} = 4 である。もしも関数が定数項のみからなる場合、係数幅は 0 である。
問題 A, B, C 間の違い
問題 A, B, C において問われるアルゴリズムは基本的に同一のものであるため、3 つの問題についてまったく同じアルゴリズムを提出してもかまわないし、別のアルゴリズムを提出してもよい。問題 A, B, C 間の主な違いは、与えられる整数擬似ブール関数 f(X) の構造が異なることである。
どの問題においても、与えられる f(X) は上で述べた形式を満たし、非零の係数および定数 H, p_i, q_{ij}, r_{ijk}, \cdots \in \mathbb{Z} は後述の制約内から一様ランダムに決定されるが、次数や項数に以下の違いがある。
- 問題 A: この問題では、次数 d が最大で変数の数 N となるような整数擬似ブール関数が与えられる。しかしながら、変数の数に対して非零の係数を持つ項の数は少ないため、入力は疎であるとも言える。
- 問題 B: この問題では、整数擬似ブール関数の次数は小さい。具体的には、次数が 6 を超えるような入力は与えられない。さらに問題 A と同じく、変数の数に対して非零の係数を持つ項の数は少ないため、問題 A とは種類が異なるような疎な入力であるとも言える。
- 問題 C: この問題では、次数が 6 までとなる任意の項についてその係数が非零となる可能性があり、密な入力であるとも言える。
異なるタイプの入力に対して異なる戦略が生まれることを期待し、入力として 3 つの異なるクラスを用意している。ここで改めて、問題 A, B, C の違いを表にまとめると、以下のようになる。
関数の項が密 | 関数の項が疎 | |
---|---|---|
高次数 | 問題 A | |
低次数 | 問題 C | 問題 B |
入力
入力は以下の形式で標準入力から与えられる。
N K d_1 c_1 v_{1, 1} ... v_{1, d_1} d_2 c_2 v_{2, 1} ... v_{2, d_2} : d_K c_K v_{K, 1} ... v_{K, d_K}
- 入力はすべて整数である。
- 1 行目では 2 つの整数 N, K が与えられる。 N は変数の数を、 K は項の数を表す。
- 2 行目から K+1 行目までの各行では、それぞれの項の情報を表す整数が与えられる。 d_i は第 i 項の次数を、 c_i は第 i 項の係数を、 v_{i, 1} \ldots v_{i, d_i} はその項を構成する変数番号を表す。
- d_i = 0 であるときは定数項を表し、その行は d_i c_i のみからなる。
また、入力は以下の制約を満たす。
- 3 \leq N \leq 50
- 1 \leq K \leq 50
- 0 \leq d_i \leq N
- 1 \leq \left| c_i \right| \leq 100
- 1 \leq v_{i, j} \leq N
- 全ての j (1 \leq j \lt d_i) について、v_{i, j} < v_{i, j+1}
- i \neq j ならば \left[ v_{i, 1}, \dots , v_{i, d_i} \right] \neq \left[ v_{j, 1}, \dots, v_{j, d_j} \right]
- d_i = 0 となる行は高々 1 度しか登場しない
- 全ての k (1 \leq k \leq N) に対して、k = v_{i, j} を満たす (i, j) が少なくとも 1 つ存在する
出力
入力に対応する高々 2 次の整数擬似ブール関数 g を以下の形式で出力せよ。
S L d_1' c_1' v_{1, 1}' ... v_{1, d_1'}' d_2' c_2' v_{2, 1}' ... v_{2, d_2'}' : d_L' c_L' v_{L, 1}' ... v_{L, d_L'}'
- 出力はすべて整数でなければならない。
- 1 行目で 2 つの整数 S, L を出力する。 S は変数の数を、 L は項の数を表す。つまり新たに追加した変数の数が M 個であるとき、S = N + M が成り立つ。
- 2 行目から L+1 行目までの各行で、それぞれの項の情報を表す整数を出力する。 d_i' は第 i 項の次数を、 c_i' は第 i 項の係数を、 v_{i, 1}' \ldots v_{i, d_i'}' はその項を構成する変数番号を表す。
- 1 \leq i \leq N を満たす変数番号 i は、入力で与えられる関数 f の変数 X の番号 i と対応している必要がある。
- N+1 \leq i \leq S を満たす変数番号 i は、新たに追加した変数 W の番号 i - N を表す。
- d_i' = 0 であるときは定数項を表し、その行は d_i' c_i' のみからなるように出力する。
また、出力は下記の制約をすべて満たす必要がある。
- N \leq S \leq 3 \times10^3
- 1 \leq L
- 0 \leq d_i' \leq 2
- 1 \leq \left|c_i'\right| \leq 2^{31}-1
- 1 \leq v_{i, j}' \leq S
- 全ての j (1 \leq j \lt d_i') について、v_{i, j}' < v_{i, j+1}'
- i \neq j ならば \left[ v_{i, 1}', \dots , v_{i, d_i'}' \right] \neq \left[ v_{j, 1}', \dots, v_{j, d_j'}' \right]
- d_i' = 0 となる行は高々 1 度しか登場しない
- 全ての k (N+1 \leq k \leq S) について、k = v_{i, j}' を満たす (i, j) が少なくとも 1 つ存在する。つまり、新たに追加された変数は式の中で必ず使用されていなければならない。
採点方法
各テストケースの得点の合計がその解答の得点となる。コンテスト中には 15 個のテストケースが存在する。コンテスト終了後に 100 個のテストケースによってシステムテストを行い、システムテストの得点を最終得点とする。なお、システムテストのテストケースは現在配布しているコードと異なり、テストケース毎に異なる乱数のシードを用いて実施される。また、乱数シードの生成方法については非公開とする。
各テストケースについて、以下のように得点を計算する。
- A=10000, B=5, E = 10000とする。
- 変数の組 X = \left[ x_1, \ldots, x_N \right] \in \left\{ 0, 1 \right\}^N をある形に決定したときの得点は、以下のように決定される。
- X = \left[ x_1, \dots ,x_N \right] に対する関数 g の最小値の近似解は、W \in \left\{ 0, 1 \right\}^M から成る空間上を焼きなまし法で探索することによって得られ、その近似解を g_{\min, SA}(x_1, \dots ,x_N) と定義する。
- \left[x_1, \ldots, x_N\right] に対して焼きなまし法を 5 回計算し、その中での最小値が g_{\min, SA}(x_1, \dots, x_N) として採用される。
- 以下に示す、関数誤差に関する指標PX、関数の項や変数に関する指標 PY、係数幅に関する指標 PZ の積に A を掛けたもの、すなわち A \times PX \times PY \times PZ が、得点として得られる値となる。
- PX = E \left(1 - \frac{\min(e_{SA}, T)}{T} \right)
- PY = \frac{1000}{BM + L + 1000}
- PZ = \frac{1000}{\max_i |c_i'| + 1000}
- 各変数の意味は以下の通りである。
- e_{SA} = g_{\min, SA}(x_1, \dots ,x_N) - f(x_1, \dots ,x_N) とする。これは g における近似解と f における関数値の誤差である。
- T は、許容する関数誤差の閾値であり、T = 100 である。誤差が T を超えても得点は得られるが、得られる点数は少ないことに留意されたい。
- M は、関数 f に対して新たに追加した変数の数である。
- L は、関数 g の項数である。
- \max_{i} |c_i'| は g の係数幅、つまり関数 g の定数項以外の項に対する係数の絶対値の最大値である。
- 変数の組 X = \left[ x_1, \ldots, x_N \right] は以下のように 2 回決め、それぞれに対して上記の方法で得点を計算する。それぞれの得点を PA, PB とおくと、 \lfloor \frac{PA + PB}{2} \rfloor が各テストケースに対する得点となる。
- 一方は、変数の組をランダムに決定する。つまり、各 i (1 \leq i \leq N) について、x_i を 0 または 1 に一様ランダムで設定する。
- もう一方は、全ての変数に関して 1 を設定する。つまり、\left[ x_1, x_2, \ldots, x_N \right] = \left[ 1, 1, \ldots, 1 \right] となる。
- 以下の条件のいずれかに該当する場合は 0 点となる。
- g_{\min, SA}(x_1, \dots ,x_N) \lt f(x_1, \dots ,x_N) である。つまり、e_{SA} が負の値になる。
- 実行制限時間またはメモリを超過する、ないしは出力が正しい出力フォーマットに従っていない。フォーマットについては特に以下の点に注意すること。
- 出力における変数の数 S は N 以上でなければならない。N 未満とした場合は
WA
となる。 - 項数は必ず正の値でなければならない。項数が 0 の場合は
WA
となる。 - 係数および定数に 0 を設定することは許されない。0 を設定した場合は
WA
となる。 - 新しく追加された変数は少なくとも一度は必ず使用されていなければならない。一度も使用されなかった場合は
WA
となる。 - あるテストケースに対して上記のような制約違反が起こった場合、この問題全体に対する得点が 0 点となる。
e_{SA} の計算には焼きなまし法を使用する。ジャッジ側が焼きなまし法に用いるシードは固定であるが非公開である。採点用のプログラムはツールキットに含まれるので詳細はそちらを参照のこと。
入力例 1
3 1 3 1 1 2 3
この入力例は f(x_1, x_2, x_3) = x_{1}x_{2}x_{3} を表す。
出力例 1
4 5 2 1 1 2 1 1 4 2 -1 1 4 2 -1 2 4 2 1 3 4
新たに変数 W = \left[ w_1 \right] を追加することで、高々 2 次の整数擬似ブール関数 g を生成することを考える。元の関数において変数が 3 つ存在するため、実際に出力する際には w_1 は 4 番目の変数として扱われる。
この出力は g(x_1, x_2, x_3, w_1) = x_{1}x_{2} +w_1 -x_{1}w_1 -x_{2}w_1 +x_{3}w_1 = x_{1}x_{2} +w_1(1 -x_1 -x_2 +x_3) を表す。 どのように x_1, x_2, x_3 を選んでも f(x_1, x_2, x_3) = \min_{W} g(x_1, x_2, x_3, W) を満たすことが確認できる。
変数の組を 2 回決め、その両方においてe_{SA} = 0 であったと仮定して得点を計算することを考える。新しく追加した変数の数は 1、項の数は 5、係数幅は 1 であるため、PA, PB はともに以下の値を取る。
PA = PB = A \times E (1 - 0) \times \frac{1000}{B \times 1 + 5 + 1000} \times \frac{1000}{1 + 1000} = 98910990.00009891
よってこのテストケースに対する得点は、98910990 点となる。
入力例 2
6 7 3 69 3 5 6 3 -93 2 3 4 3 -63 2 5 6 4 -95 1 2 5 6 3 24 1 4 5 2 75 1 6 2 49 3 6
出力例 2
11 28 2 24 1 4 2 24 1 5 2 75 1 6 2 -95 1 7 2 -24 1 8 2 -95 2 7 2 -93 2 9 2 -63 2 10 2 69 3 5 2 118 3 6 2 -93 3 9 2 -69 3 11 2 24 4 5 2 -24 4 8 2 -93 4 9 2 69 5 6 2 -95 5 7 2 -24 5 8 2 -63 5 10 2 -69 5 11 2 -95 6 7 2 -63 6 10 2 -69 6 11 1 285 7 1 24 8 1 186 9 1 126 10 1 69 11
ジェネレータとテスターおよび参考文献
- この問題のジェネレータおよびテスターはここからダウンロードできる。
- この問題を解くにあたって、以下の文献を参考にしながら解答を作成しても良い。
Review
擬似ブール関数を高々 2 次の擬似ブール関数になるように変換することに関する概説が記載されている。
- [Review] Endre Boros and Aritanan Gruber, "On Quadratization of Pseudo-Boolean Functions" [arxiv]
Fix, Gruber, Boros, Zabih
以下の 2 つの論文では、擬似ブール関数を高々 2 次の形式に変換する最新鋭のアルゴリズムに関して記載されており、実装も公開されている。
- [Paper] Alexander Fix et al., "A graph cut algorithm for higher-order Markov Random Fields" [ieee] [pdf]
- [Paper] Alexander Fix et al., "A Hypergraph-Based Reduction for Higher-Order Binary Markov Random Fields" [ieee]
- [Code] Alexander Fix
Ishikawa
以下の 2 つの論文も、擬似ブール関数を高々 2 次の形式に変換する最新鋭のアルゴリズムに関して記載されており、実装も公開されている。
- [Paper] Hiroshi Ishikawa, "Higher-order clique reduction in binary graph cut" [ieee] [pdf]
- [Paper] Hiroshi Ishikawa, "Transformation of General Binary MRF Minimization to the First-Order Case" [ieee] [pdf]
- [Code] Hiroshi Ishikawa
Notification
In case equations are not displayed properly, we recommend taking a look at the new AtCoder system.
Problem Setting
Create an algorithm which provides quadratizations for higher order pseudo-Boolean functions.
Definitions: Higher order and quadratic pseudo-Boolean function
Let f(X) be a pseudo-Boolean function of N binary variables X = \left[ x_1, \ldots, x_{N} \right] (x_i \in \left\{ 0, 1 \right\}) and g(Y) be a pseudo-Boolean function of S binary variables Y = \left[ y_1, \ldots, y_{S} \right] (y_i \in \left\{ 0, 1 \right\}). For the scope of this contest let f(X) and g(Y) be polynomials
- f(X) = f(x_1, \ldots, x_{N}) = H + \sum_{i=1}^{N} p_i x_i + \sum_{1 \leq i < j \leq N} q_{ij} x_i x_j + \sum_{1 \leq i < j < k \leq N} r_{ijk} x_i x_j x_k + \cdots,
- g(Y) = g(y_1, \ldots, y_{S}) = H' + \sum_{i=1}^{S} p_i' y_i + \sum_{1 \leq i < j \leq N+M} q_{ij}' y_i y_j,
Example: Higher order and quadratic pseudo-Boolean function
f(x_1, x_2, x_3)= - x_1 x_2 x_3 is a higher order pseudo-Boolean function of degree 3 with a total of 1 terms and 3 binary variables. On the other hand, g(y_1, y_2, y_3, y_4) = y_4 \times (2-y_1-y_2-y_3) is a quadratic pseudo-Boolean function of degree 2 with a total of 4 terms and 4 binary variables.
Task: Algorithm for quadratization of higher order Boolean functions
Given a higher order pseudo-Boolean function f(X) as an input, create an algorithm which provides a quadratic pseudo-Boolean function g(Y)=g(X,W) of degree at most 2, such that:
f(X) = \min_{W \in \left\{0, 1\right\}^M} g(X, W) for all X \in \left\{0, 1\right\}^N.
A function g(Y)=g(X,W) which fulfills the above condition is referred to as a quadratization of f(X). A quadratization g(Y)=g(X,W) shares a common set of variables \left[ y_1, \ldots, y_{N} \right]=\left[ x_1, \ldots, x_{N} \right]=X \in \left\{0, 1\right\}^N with f(X), while maintaining a set of additional ancillary variables \left[ y_{N+1}, \ldots, y_{N+M} \right]=\left[ w_1, \ldots, w_{M} \right]=W \in \left\{0, 1\right\}^M.
Example: Quadratization
The function g(x_1, x_2, x_3, w) = w (2-x_1-x_2-x_3) is a quadratization of f(x_1, x_2, x_3)= -x_1 x_2 x_3. To see this, we consider two cases:
If at least one of the variables x_1, x_2, x_3 is 0, f(x_1,x_2,x_3)=0. On the other hand, considering the function g we have that (2-x_1-x_2-x_3)≥0. Thus, minimizing g with respect to w\in[0,1] we find that min_w{ g(x_1,x_2,x_3,w)}=0.
Side Remark:
Checking whether a submitted algorithm provides an appropriate quadratization according to the aforementioned definition is impossible within the given limits of computing time. For this reason we accept algorithms which provide a quadratic pseudo-Boolean function that provides an upper bound on the true quadratization according to:
f(X) \le \min_{W \in \left\{0, 1\right\}^M} g(X, W) for all X \in \left\{0, 1\right\}^N.
This being said, it is worth to keep in mind that successful submissions will provide a quadratic pseudo-Boolean function which keeps the gap
e(X):= \min_{W \in \left\{0, 1\right\}^M} g(X, W)-f(X)\ge 0
as small as possible for all X \in \left\{0, 1\right\}^N.Scoring:
The award-winning algorithm will provide quadratizations g(X,W) of pseudo-Boolean functions f(X) such that
- g(X,W) has as few ancillary variables W=[w_1, \ldots, w_M] as possible,
- g(X,W) has as few terms as possible,
- the coefficients of g(X,W) are as small as possible.
- Additional score is awarded, if the algorithm provides quadratizations g(X,W), which can be easily minimized with respect to the ancillary variables W by means of simulated annealing.
Example: Scoring points
The function g(x_1, x_2, x_3, w) = (2w - x_1 w - x_2 w - x_3 w) is a quadratization of f(x_1, x_2, x_3)= -x_1 x_2 x_3. It contains one ancillary variable w, a total of four terms and its maximal coefficient is 2.
On the Differences of Problem Setting A, B, and C
Note that the thought after algorithms in problem statement A, B, and C are basically identical. In particular, it is admissible to submit the identical algorithm to all three problems and obtain score for it. On the other hand, the main difference between Problem settings A, B, and C is the structure of the higher order pseudo-Boolean f(X) which will be provided to your algorithm as an input.
All input problems will take the structure of a higher order pseudo-Boolean polynomial f(X) as specified by the equation above. For all input cases we will chose random coefficients H, p_i, q_{ij}, r_{ijk}, \cdots \in \mathbb{Z} uniformly sampled in a range to be specified below. The input samples will vary with respect to the structure of the non-zero coefficients.
- Problem A: In problem A we consider higher-order pseudo-Boolean input functions with large degrees d, i.e., degree's up to the full size of available variables d\le N. The number of terms with non-zero coefficients will however be very low, such that the input becomes "sparse".
- Problem B: In problem B we consider higher-order pseudo-Boolean input functions with low degree. In particular, no input function will have degree larger than 6 (d\le 6). Furthermore, only some of the potential polynomial terms will have non-zero coefficients, thus, resulting in another sparse input.
- Problem C: In problem C we will provide input problems of degree 6 with coefficients of all available terms chosen as random inputs, thus, resulting in a "dense" input problem.
The purpose of providing three different classes of input problems lies in giving the algorithms the chance to allow for different tuning strategies with respect to different input targets. A comprehensive summary of the input problems in problem statements A, B, and C is given in the table below.
dense (all terms) | sparse (few terms) | |
---|---|---|
high degree | Problem A | |
low degree | Problem C | Problem B |
Input Format
The higher order pseudo-Boolean function f(X) will be provided through the following input format
N K d_1 c_1 v_{1, 1} ... v_{1, d_1} d_2 c_2 v_{2, 1} ... v_{2, d_2} : d_K c_K v_{K, 1} ... v_{K, d_K}
- All input values are of integer type.
- N denotes the number of binary variables X = \left[ x_1, \ldots, x_{N} \right].
- K denotes the number of terms in the higher order pseudo-Boolean polynomial f(X).
- Each of the lines 2, \ldots, K+1 encodes the information on one of the K terms of f(X).
In particular, the ith term is decoded as follows: d_i denotes the degree of the ith term, c_i denotes the coefficient of the ith term, and thenumbers v_{i, 1} \ldots v_{i, d_i} denote the indices of the binary variables x_{v_{i, 1}} \ldots x_{v_{i, d_i}} which form the ith term (monomial). - In the special case d_i = 0 we only provide the constant offset c_i and no further variables v_{i, 1} \ldots v_{i, d_i}.
The higher order Boolean monomial f(x_1, x_2, x_3, x_4, x_5) = - x_{1}x_{2}x_{3} + 4 x_{4}x_{5} is encoded as follows.
Line one: f(X) contains 5 binary variables and two terms.Input Example
5 2
3 -1 1 2 3
2 4 4 5
Line two: The first term has degree 3, i.e., it is a product of three variables. Its prefactor/coefficient is -1. The term contains the variables x_{1}, x_{2}, x_{3}.
Line three: The second term has degree 2, i.e., it is a product of two variables. Its prefactor/coefficient is 4. The term contains the variables x_{4}, x_{5}.
The following additional requirements shall be imposed on the input problem.
- 3 \leq N \leq 50
- 1 \leq K \leq 50
- 0 \leq d_i \leq N
- 1 \leq \left|c_i \right| \leq 100
- 1 \leq v_{i, j} \leq N
- For all j (1 \leq j \lt d_i) we require v_{i, j} < v_{i, j+1}
- For two lines i,j with i \neq j we require \left[ v_{i, 1}, \dots , v_{i, d_i} \right] \neq \left[ v_{j, 1}, \dots, v_{j, d_j} \right], i.e., two separate lines shall not encode the same type of monomial.
- The line d_i = 0 should not exceed beyond the coefficient.
- All of the variables k (1 \leq k \leq N) should appear in at least one of the term, i.e., there exists at least one v_{i,j} such that k = v_{i, j}.
Output Format
The submitted algorithm shall provide the obtained quadratization g(Y)=g(X,W) using the following output format.
S L d_1' c_1' v_{1, 1}' ... v_{1, d_1'}' d_2' c_2' v_{2, 1}' ... v_{2, d_2'}' : d_L' c_L' v_{L, 1}' ... v_{L, d_L'}'
- All values in the output file shall be of integer type
- S shall denote the number of binary variables used by the quadratization g(X,W), where S shall be the sum of "old" and "new" variables S=N+M.
- L shall denote the number of terms (monomials) of g(X,W).
- Each of the lines 2, \ldots, L+1 encodes the information on one of the L terms of g(Y)=g(X,W).
In particular, d_i' denotes the degree of the ith term, c_i' denotes the coefficient of the ith term, and thevariables v_{i, 1}' \ldots v_{i, d_i}' denote the indices of the binary variables y_{v_{i, 1}'} \ldots y_{v_{i, d_i}'} forming the ith term (monomial). - The indices v_{i,l}' must be chosen such that binary variable y_{r} with r=1,...,N of g(Y) can be safely identified with the binary variables x_{r} with r=1,...,N of f(X) as y_{r}=x_{r} for all r=1,...,N.
- In the special case d_i' = 0 only the constant offset c_i' appears and no further variables v_{i, 1}' \ldots v_{i, d_i}' shall be provided.
The following additional requirements shall be imposed on the output format.
- N \leq S \leq 3 \times10^3
- 1 \leq L
- 0 \leq d_i' \leq 2
- 1 \leq \left|c_i'\right| \leq 2^{31}-1
- 1 \leq v_{i, j}' \leq S
- For all j (1 \leq j \lt d_i') we require that v_{i, j}' < v_{i, j+1}'.
- For two lines i, j with i \neq j we require \left[ v_{i, 1}', \dots , v_{i, d_i'}' \right] \neq \left[ v_{j, 1}', \dots, v_{j, d_j'}' \right], i.e., two separate lines shall not contain information on identical monomials.
- The line d_i' = 0 shall not exceed beyond the coefficient.
Scoring
Your algorithm will be scored by running it on several input problems f(X). For each input problem the resulting quadratization g(X,W) will be scored as described below. Your total score will be the sum of the score obtained for each input problem.
Number of input problems during and after the contest:
During the contest we will estimate your score by running your algorithm on a preliminary set of 15 input problems for each of the sub-problems A, B, and C. This will allow for estimating your rank. After the contest finishes we will evaluate your final score by running your algorithm on a set of 100 previously undisclosed input problems (created with the exact same statistical properties) for each of the sub-problems A, B, and C. This measure is taken to avoid tuning of algorithms to a particular statistical fluctuations on the set of input problems.
Scoring of input problems:
For each input problem your algorithm will be awarded the following score:
A \times PX \times PY \times PZ,
where A=10000 is a constant and factors are defined as follows
- PX = E \left(1 - \frac{\min(e_{SA}, T)}{T} \right),
- PY = \frac{1000}{BM + L + 1000},
- PZ = \frac{1000}{\max_i |c_i'| + 1000},
The scoring is based on the following logic:
- PX measures the ability of your algorithm to provide quadratizations from which the true value of the original function f(X) can approximately be recovered based on simulated annealing. In particular, if your algorithm provides quadratizations for which e_{SA} is zero, the first factor will take its maximal value E. In addition, a partial score is awarded, if e_{SA} < T=100, i.e., if your algorithm at least allows to approximate the original value of f(X) with some accuracy. Finally, should e_{SA} < 0 your algorithm provides a wrong submission and your total score becomes zero. For further details on e_{SA}, see the section below.
- PY introduces a fine for quadratizations which use too many ancillary variables M or else produce quadratizations with many terms L. It shall encourage algorithms which create quadratizations with as few ancillary variables and few terms.
- PY introduces a fine for algorithms which produce coefficients with large modulus \max_{i}|c_i'|. This shall encourage algorithms for which the bit width of the required coefficients shall not grow too severely.
SCORE = \lfloor \frac{PA + PB}{2} \rfloor.
Determination of e_{SA}
In order to determine e_{SA} we proceed using the following steps:
- We fix the set of input variables x_1, \dots ,x_N either in a random configuration X \in \left\{ 0, 1 \right\}^N or in the configuration where all bits are selected, i.e., [x_1, x_2, ..., x_N]=[1, 1, ..., 1] .
- For this set of variables X we minimize g(X,W) with respect to the remaining new variables W \in \left\{ 0, 1 \right\}^M by running a version of simulated annealing (SA) with five repetitions. [See provided software toolkit for details.] The five repititions of SA will result in a configuration of variables w_{1,SA}, \dots ,w_{M,SA} for which we obtain the minimal gap
e_{SA} :=g(x_1, \dots ,x_N, w_{1,SA}, \dots ,w_{M,SA})-f(x_1, \dots ,x_N).
- e_{SA} will be zero, if simulated annealing finds the true minimum with respect to W. If simulated annealing finds an approximate local minimum, e_{SA} will be larger than zero. If e_{SA} is smaller than zero, the submitted algorithm has a bug and the total score will be set to zero.
Please note that the seed for choosing the random configuration x_1, \dots ,x_N as well as the random elements of the simulated annealing procedure cannot be disclosed. In contrast to the contest ranking, where x_1, \dots ,x_N was identical for each of the 15 cases, the final test will use distinct configurations x_1, \dots ,x_N for all 100 cases.
Invalid submissions
Note that a submitted algorithm might be invalid for several reasons, e.g., if the gap between the true function value and the minimum of the quadratization with respect to the true minimum becomes smaller than zero. Another case in which a given submission gets zero score occurs, if the output violates the output format described above. In all these cases the given submission will be marked with the signal WA
in the AtCoder standings section.
Input Format Example 1
3 1 3 1 1 2 3
This input file represents the function f(x_1, x_2, x_3) = x_{1}x_{2}x_{3}.
Output Format Example 1
4 5 2 1 1 2 1 1 4 2 -1 1 4 2 -1 2 4 2 1 3 4
This output example provides a quadratization of the input example with a total of S=4 binary variables and L=5 terms, i.e., the quadratization uses a single ancillary variable W = \left[ w_1 \right] and M=1. Alltogether the output format example decodes the following cost function g(x_1, x_2, x_3, w_1) = x_{1}x_{2} +w_1 -x_{1}w_1 -x_{2}w_1 +x_{3}w_1 = x_{1}x_{2} +w_1(1 -x_1 -x_2 +x_3).
The output provides a valid quadratization of the input problem, because for any combination x_1, x_2, x_3 it can be shown that f(x_1, x_2, x_3) = \min_{W} g(x_1, x_2, x_3, W). The maximal coefficient of the quadratization is \max|c_i'|=1.
Finally, assuming that e_{SA} = 0 becomes zero both for a random configuration of [x_1, x_2, x_3] as well as the configuration [x_1, x_2, x_3]=[1,1,1] the above output has
- M=1 ancillary variables,
- L=5 terms,
- the maximal coefficient \max_i |c_i'|=1,
PA = PB = A\times E(1-0)\times\frac{1000}{B\times1 +5 + 1000} \times \frac{1000}{1+1000}=98910990.00009891.
and the total scoreSCORE = \lfloor \frac{2\times 98910990.00009891}{2}\rfloor =98910990.
Input Format Example 2
6 7 3 69 3 5 6 3 -93 2 3 4 3 -63 2 5 6 4 -95 1 2 5 6 3 24 1 4 5 2 75 1 6 2 49 3 6
Output Format Example 2
11 28 2 24 1 4 2 24 1 5 2 75 1 6 2 -95 1 7 2 -24 1 8 2 -95 2 7 2 -93 2 9 2 -63 2 10 2 69 3 5 2 118 3 6 2 -93 3 9 2 -69 3 11 2 24 4 5 2 -24 4 8 2 -93 4 9 2 69 5 6 2 -95 5 7 2 -24 5 8 2 -63 5 10 2 -69 5 11 2 -95 6 7 2 -63 6 10 2 -69 6 11 1 285 7 1 24 8 1 186 9 1 126 10 1 69 11
Sample Code and Literature Hints
- Sample code for generating input formats and score evaluation can be downloaded from here.
- In order to get started on quadratization, we encourage the use of the literature and open source software listed below.
Review
A brief review giving an introduction to the main ideas of reducing higher-order Boolean polynomials into quadratic pseudo-Boolean polynomials.
- [Review] Endre Boros and Aritanan Gruber, "On Quadratization of Pseudo-Boolean Functions" [arxiv]
Fix, Gruber, Boros, Zabih
Two papers on a state of the art algorithm for quadratizing higher-order pseudo-Boolean cost functions and an open source software implementation are available from the following links.
- [Paper] Alexander Fix et al., "A graph cut algorithm for higher-order Markov Random Fields" [ieee] [pdf]
- [Paper] Alexander Fix et al., "A Hypergraph-Based Reduction for Higher-Order Binary Markov Random Fields" [ieee]
- [Code] Alexander Fix
Ishikawa
Two further papers on a state of the art algorithm for quadratizing higher-order pseudo-Boolean cost functions.- [Paper] Hiroshi Ishikawa, "Higher-order clique reduction in binary graph cut" [ieee] [pdf]
- [Paper] Hiroshi Ishikawa, "Transformation of General Binary MRF Minimization to the First-Order Case" [ieee] [pdf]
- [Code] Hiroshi Ishikawa
Time Limit: 30 sec / Memory Limit: 1024 MB
注意
問題文中の数式が正しく表示されない場合は、新システム上のページにアクセスし直してご覧ください。
問題文
この問題は「問題 A」と同一の問題であるが、制約が異なる。問題文本文は問題 A のページを、制約は以下を参照のこと。
入力
入力は以下の制約を満たす。
- 3 \leq N \leq 300
- 1 \leq K \leq 1000
- 0 \leq d_i \leq \min(N, 6)
- 1 \leq \left|c_i \right| \leq 100
- 1 \leq v_{i, j} \leq N
- 全ての j (1 \leq j \lt d_i) について、v_{i, j} < v_{i, j+1}
- i \neq j ならば \left[ v_{i, 1}, \dots , v_{i, d_i} \right] \neq \left[ v_{j, 1}, \dots, v_{j, d_j} \right]
- d_i = 0 となる行は高々 1 度しか登場しない
- 全ての k (1 \leq k \leq N) に対して、k = v_{i, j} を満たす (i, j) が少なくとも 1 つ存在する
Notification
In case equations are not displayed properly, we recommend taking a look at the new AtCoder system.
Problem Setting
The task in problem setting B is almost equivalent to problem setting A. Hence, for details on the task the contestant is refered to problem setting A. The only difference in Problem B is the shape of the higher order pseudo-Boolean function which serves as an input. This input will now have degree at most 6 (d=6), while still maintaining a sparse structure. For details of the input problem contestants are referred to the section below.
Input Format
The following requirements shall be imposed on the input problem.
- 3 \leq N \leq 300
- 1 \leq K \leq 1000
- 0 \leq d_i \leq min(N,6)
- 1 \leq \left|c_i \right| \leq 100
- 1 \leq v_{i, j} \leq N
- For all j (1 \leq j \lt d_i) we require v_{i, j} < v_{i, j+1}
- For two lines i,j with i \neq j we require \left[ v_{i, 1}, \dots , v_{i, d_i} \right] \neq \left[ v_{j, 1}, \dots, v_{j, d_j} \right], i.e., two separate lines shall not encode the same type of monomial.
- The line d_i = 0 should not exceed beyond the coefficient.
- All of the variables k (1 \leq k \leq N) should appear in at least one of the term, i.e., there exists at least one v_{i,j} such that k = v_{i, j}.
Time Limit: 30 sec / Memory Limit: 1024 MB
注意
問題文中の数式が正しく表示されない場合は、新システム上のページにアクセスし直してご覧ください。
問題文
この問題は「問題 A」と同一の問題であるが、制約が異なる。問題文本文は問題 A のページを、制約は以下を参照のこと。
入力
入力は以下の制約を満たす。
- 3 \leq N \leq 10
- 1 \leq K \leq 2^N
- 0 \leq d_i \leq 6
- 1 \leq \left|c_i \right| \leq 100
- 1 \leq v_{i, j} \leq N
- 全ての j (1 \leq j \lt d_i) について、v_{i, j} < v_{i, j+1}
- i \neq j ならば \left[ v_{i, 1}, \dots , v_{i, d_i} \right] \neq \left[ v_{j, 1}, \dots, v_{j, d_j} \right]
- d_i = 0 となる行は高々 1 度しか登場しない
- 全ての k (1 \leq k \leq N) に対して、k = v_{i, j} を満たす (i, j) が少なくとも 1 つ存在する
Notification
In case equations are not displayed properly, we recommend taking a look at the new AtCoder system.
Problem Setting
The task in problem setting C is almost equivalent to problem setting A. Hence, for details on the task the contestant is refered to problem setting A. The only difference in Problem C is the shape of the higher order pseudo-Boolean function which serves as an input. This input will now have degree at most 6 (d=6), while coefficients are provided for all possible terms of the function. For details of the input problem contestants are referred to the section below.
Input Format
The following requirements shall be imposed on the input problem.
- 3 \leq N \leq 10
- 1 \leq K \leq 2^N
- 0 \leq d_i \leq 6
- 1 \leq \left|c_i \right| \leq 100
- 1 \leq v_{i, j} \leq N
- For all j (1 \leq j \lt d_i) we require v_{i, j} < v_{i, j+1}
- For two lines i,j with i \neq j we require \left[ v_{i, 1}, \dots , v_{i, d_i} \right] \neq \left[ v_{j, 1}, \dots, v_{j, d_j} \right], i.e., two separate lines shall not encode the same type of monomial.
- The line d_i = 0 should not exceed beyond the coefficient.
- All of the variables k (1 \leq k \leq N) should appear in at least one of the term, i.e., there exists at least one v_{i,j} such that k = v_{i, j}.