Author: | Roman Bilyi |
Prepared by: | Yarema Stiahar |
Solved by: | |
First to solve: | 2Popici1Arici |
Let’s assume some value there are at least 2 triplets with that value (a_1, b_1, v) and (a_2, b_2, v). If all values a_1, b_1, a_2, b_2 are distinct, the answer is 0. WLOG, a_1=b_2=x, then should hold p_x=v. So we can find positions of all values that appear more than once(or the answer is 0). After that, while we have triplets (i, j, v) such that either position or is used, we can set value to another one. After that we have left only triplets with unique values and no positions solved.
For each triplet (a, b, v) let’s create undirected edge between nodes and . We must assign each value to one of its possible nodes such that each node receives at most one value (some nodes may receive values that weren’t present in any triplet). Let’s say that we must direct edges such that for each node at most one edge points towards it. Note that actual values don’t matter.
We decompose the graph into connected components. Let a component have V_c vertices and E_c edges. Since each vertex can hold only one value, we must have E_c \le V_c. If E_c > V_c for any component, the answer is .
We have the following cases:
Tree (E_c = V_c - 1) We have V_c - 1 values to place in V_c spots. Exactly one spot will remain empty. Any of the V_c vertices can be the empty one. Once the empty vertex is chosen, the orientation of all edges is forced. Number of ways: V_c.
Unicyclic (E_c = V_c) We must fill all V_c spots with V_c edges. This is only possible by orienting the unique cycle in one of 2 directions (clockwise or counter-clockwise). The edges of trees attached to the cycle are forced to point away from the cycle. Number of ways: .
Let be the number of values that were completely unconstrained (not presented in any triplet). These values will fill the positions left empty by the tree components. The total number of good permutations is:
Complexity: O(n+m).