H. New Year and Boolean Bridges

Codeforces

IDCF908H

Time5000ms

Memory512MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

Your friend has a hidden directed graph with _n_ nodes. Let _f_(_u_, _v_) be true if there is a directed path from node _u_ to node _v_, and false otherwise. For each pair of distinct nodes, _u_, _v_, you know at least one of the three statements is true: Here AND, OR and XOR mean AND, OR and exclusive OR operations, respectively. You are given an _n_ by _n_ matrix saying which one of the three statements holds for each pair of vertices. The entry in the _u_\-th row and _v_\-th column has a single character. 1. If the first statement holds, this is represented by the character '_A_'. 2. If the second holds, this is represented by the character '_O_'. 3. If the third holds, this is represented by the character '_X_'. 4. The diagonal of this matrix will only contain the character '_\-_'. Note that it is possible that a pair of nodes may satisfy multiple statements, in which case, the character given will represent one of the true statements for that pair. This matrix is also guaranteed to be symmetric. You would like to know if there is a directed graph that is consistent with this matrix. If it is impossible, print the integer _\-1_. Otherwise, print the minimum number of edges that could be consistent with this information. ## Input The first line will contain an integer _n_ (1 ≤ _n_ ≤ 47), the number of nodes. The next _n_ lines will contain _n_ characters each: the matrix of what you know about the graph connectivity in the format described in the statement. ## Output Print the minimum number of edges that is consistent with the given information, or _\-1_ if it is impossible. [samples] ## Note Sample 1: The hidden graph is a strongly connected graph. We can put all four nodes in a cycle. Sample 2: One valid graph is 3 → 1 → 2. For each distinct pair, exactly one of _f_(_u_, _v_), _f_(_v_, _u_) holds.

你的朋友有一个包含 #cf_span[n] 个节点的有向图。令 #cf_span[f(u, v)] 为真，当且仅当存在从节点 #cf_span[u] 到节点 #cf_span[v] 的有向路径；否则为假。对于每一对不同的节点 #cf_span[u, v]，你已知以下三个陈述中至少有一个为真：其中 AND、OR 和 XOR 分别表示与、或和异或运算。你得到了一个 #cf_span[n] × #cf_span[n] 的矩阵，其中每个元素是一个字符，表示每对顶点对应的三个陈述中哪一个成立。注意，一对节点可能满足多个陈述，此时给出的字符代表其中任意一个成立的陈述。该矩阵保证是对称的。你需要判断是否存在一个有向图与该矩阵一致。如果不可能，输出整数 _-1_；否则，输出与该信息一致的最少边数。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 47])，表示节点数量。接下来的 #cf_span[n] 行每行包含 #cf_span[n] 个字符：按题目描述格式给出的关于图连通性的矩阵。请输出与给定信息一致的最少边数，或 _-1_（如果不可能）。样例 1：隐藏图是一个强连通图。我们可以将四个节点排成一个环。样例 2：一个合法的图是 #cf_span[3 → 1 → 2]。对于每一对不同的节点，#cf_span[f(u, v)] 和 #cf_span[f(v, u)] 恰好有一个为真。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 47])，表示节点数量。接下来的 #cf_span[n] 行每行包含 #cf_span[n] 个字符：按题目描述格式给出的关于图连通性的矩阵。 ## Output 请输出与给定信息一致的最少边数，或 _-1_（如果不可能）。 [samples] ## Note 样例 1：隐藏图是一个强连通图。我们可以将四个节点排成一个环。样例 2：一个合法的图是 #cf_span[3 → 1 → 2]。对于每一对不同的节点，#cf_span[f(u, v)] 和 #cf_span[f(v, u)] 恰好有一个为真。

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 47 $, be the number of nodes. Let $ M \in \{A, O, X\}^{n \times n} $ be a symmetric matrix where $ M[u][v] \in \{A, O, X\} $ for $ u \neq v $, and $ M[u][u] $ is undefined (diagonal ignored). For each unordered pair $ \{u, v\} $, $ u \neq v $, define: - $ f(u,v) $: boolean indicating existence of a directed path from $ u $ to $ v $ in the hidden graph. - The entry $ M[u][v] $ encodes one of the following true logical conditions: - **A** (AND): $ f(u,v) \land f(v,u) $ - **O** (OR): $ f(u,v) \lor f(v,u) $ - **X** (XOR): $ f(u,v) \oplus f(v,u) $ **Constraints** 1. $ M $ is symmetric: $ M[u][v] = M[v][u] $ for all $ u \neq v $. 2. For each $ u \neq v $, the value $ M[u][v] $ must be consistent with at least one of the three logical conditions on $ (f(u,v), f(v,u)) $. 3. The function $ f $ must correspond to the transitive closure of some directed graph $ G = (V, E) $ with $ V = \{1, \dots, n\} $. 4. $ f(u,v) = \text{true} $ iff there exists a directed path from $ u $ to $ v $ in $ G $. 5. $ f(u,u) = \text{true} $ for all $ u $ (reflexive closure implied by path definition). **Objective** Find the minimum number of edges in a directed graph $ G $ such that its transitive closure $ f $ satisfies all constraints imposed by $ M $, or return $ -1 $ if no such graph exists.

Samples

Input #1

4
-AAA
A-AA
AA-A
AAA-

Output #1

Input #2

3
-XX
X-X
XX-

Output #2

API Response (JSON)

{
  "problem": {
    "name": "H. New Year and Boolean Bridges",
    "description": {
      "content": "Your friend has a hidden directed graph with _n_ nodes. Let _f_(_u_, _v_) be true if there is a directed path from node _u_ to node _v_, and false otherwise. For each pair of distinct nodes, _u_, _v_",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF908H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Your friend has a hidden directed graph with _n_ nodes.\n\nLet _f_(_u_, _v_) be true if there is a directed path from node _u_ to node _v_, and false otherwise. For each pair of distinct nodes, _u_, _v_...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你的朋友有一个包含 #cf_span[n] 个节点的有向图。\n\n令 #cf_span[f(u, v)] 为真，当且仅当存在从节点 #cf_span[u] 到节点 #cf_span[v] 的有向路径；否则为假。对于每一对不同的节点 #cf_span[u, v]，你已知以下三个陈述中至少有一个为真：\n\n其中 AND、OR 和 XOR 分别表示与、或和异或运算。\n\n你得到了一个 #cf_span[n] ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 47 $, be the number of nodes.  \nLet $ M \\in \\{A, O, X\\}^{n \\times n} $ be a symmetric matrix where $ M[u][v] \\in \\{A, O, X\\} $ for $ u \\neq ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments