B - Problem Setting B Editorial /

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