A - Problem Setting A

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 は係数であり、係数はすべて整数である。

このとき、高々 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 間の違い

どの問題においても、与えられる f(X) は上で述べた形式を満たし、非零の係数および定数 H, p_i, q_{ij}, r_{ijk}, \cdots \in \mathbb{Z} は後述の制約内から一様ランダムに決定されるが、次数や項数に以下の違いがある。

• 問題 A: この問題では、次数 d が最大で変数の数 N となるような整数擬似ブール関数が与えられる。しかしながら、変数の数に対して非零の係数を持つ項の数は少ないため、入力は疎であるとも言える。
• 問題 B: この問題では、整数擬似ブール関数の次数は小さい。具体的には、次数が 6 を超えるような入力は与えられない。さらに問題 A と同じく、変数の数に対して非零の係数を持つ項の数は少ないため、問題 A とは種類が異なるような疎な入力であるとも言える。
• 問題 C: この問題では、次数が 6 までとなる任意の項についてその係数が非零となる可能性があり、密な入力であるとも言える。

### 入力

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 つ存在する

### 出力

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. 1 \leq i \leq N を満たす変数番号 i は、入力で与えられる関数 f の変数 X の番号 i と対応している必要がある。
2. 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 つ存在する。つまり、新たに追加された変数は式の中で必ず使用されていなければならない。

### 採点方法

• 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_i0 または 1 に一様ランダムで設定する。
• もう一方は、全ての変数に関して 1 を設定する。つまり、\left[ x_1, x_2, \ldots, x_N \right] = \left[ 1, 1, \ldots, 1 \right] となる。
• 以下の条件のいずれかに該当する場合は 0 点となる。
1. g_{\min, SA}(x_1, \dots ,x_N) \lt f(x_1, \dots ,x_N) である。つまり、e_{SA} が負の値になる。
2. 実行制限時間またはメモリを超過する、ないしは出力が正しい出力フォーマットに従っていない。フォーマットについては特に以下の点に注意すること。
• 出力における変数の数 SN 以上でなければならない。N 未満とした場合は WA となる。
• 項数は必ず正の値でなければならない。項数が 0 の場合は WA となる。
• 係数および定数に 0 を設定することは許されない。0 を設定した場合は WA となる。
• 新しく追加された変数は少なくとも一度は必ず使用されていなければならない。一度も使用されなかった場合は WA となる。
3. あるテストケースに対して上記のような制約違反が起こった場合、この問題全体に対する得点が 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


この出力は 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) を満たすことが確認できる。

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

• [Review] Endre Boros and Aritanan Gruber, "On Quadratization of Pseudo-Boolean Functions" [arxiv]
##### Fix, Gruber, Boros, Zabih

• [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

• [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

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,
with integer coefficients H, p_i, q_{ij}, r_{ijk}, \cdots\inℤ and H', p_i', q_{ij}'\inℤ. Furthermore, let f be a higher order pseudo-Boolean function with degree d larger two (d>2), while g shall denote a quadratic pseudo-Boolean polynomial of degree at most two.

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.

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:
• Case1: All variables x_1=x_2=x_3=1:
In this case f(x_1, x_2, x_3)=-1. On the other hand, g(x_1, x_2, x_3, w)=-w and its minimum with respect to w gives min_w g(x_1, x_2, x_3, w) = -1.
• Case2: At least one of the variables x_1, x_2, x_3 is 0
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.
For further details consult the scoring section below.

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 the numbers 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}.

Input Example

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.

5 2
3 -1 1 2 3
2 4 4 5


Line one: f(X) contains 5 binary variables and two terms.
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 the variables 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},
with constants E=10000, B=5, T=100 and e_{SA}=e_{SA}(X) being a quantity which measures the gap between the original input f(X) and its approximate value, obtained when minimizing g(X,W) with respect to the ancillary variables W for a configuration X, based on simulated annealing (SA) as described in more detail further below.

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.
Finally, for each input case we will score your algorithm using the above rules twice. In one case, we will evaluate the gap e_{SA}(X) for a totally random configuration X \in \left\{ 0, 1 \right\}^N. This will give the score PA. In the second case, we will evaluate the gap e_{SA}(X) for the configuration where all bits are in the up position, i.e., [x_1, x_2, ..., x_N]=[1, 1, ..., 1]. This will give the score PB. Your total score per input problem will then be the average, defined as

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,
resulting in

PA = PB = A\times E(1-0)\times\frac{1000}{B\times1 +5 + 1000} \times \frac{1000}{1+1000}=98910990.00009891.

and the total score

SCORE = \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
B - Problem Setting B

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 つ存在する

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}.
C - Problem Setting C

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 つ存在する

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}.