Author: Noureldin
Editorialist: Noureldin
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Meet in the middle, subset-sum (SOS), vertex-cover
PROBLEM:
You are given M triplets (X_1, Y_1, B_1), (X_2, Y_2, B_2), \ldots, (X_M, Y_M, B_M). Find the number of sequences of positive integers A_1, A_2, \ldots, A_N such that for each valid i, \mathrm{lcm}(A_{X_i},A_{Y_i}) = B_i, or determine that there is an infinite number of such sequences.
QUICK EXPLANATION:
The problem can be solved independently for each prime p, we want to determine e_1, ..., e_n where p^{e_i} divides the ith value, but p^{e_i+1} doesnât and the choices donât contradict any constraint.
The solution can be split in two stages. In the first stage we do logical deductions which determine the upper bound of some of the exponents, the exact values for others and may detect contradictions. In the second stage, we reduce the problem the vertex cover problem with can be solved in O(m*2^{n/2}).
EXPLANATION:
Let f(x, p) denote the largest e such that p^e divides x. Each constraint lcm(a, b) = x means that for each prime p, f(a, p) \leq f(x, p) and f(b, p) \leq f(x, p) and at least one of f(a, p) and f(b, p) equals f(x, p).
Letâs iterate over each prime p that divides any number in the input (other primes donât affect the answer) and do the following:
For each triplet (X_i, Y_i, B_i) let T_i = f(B_i, p) and E_x = \min(T_i) for each constrain i where x = X_i or x = Y_i) meaning that the largest power of p that can divide the x-th element of the possible arrays is at most p^{E_x}
First Stage (logical deductions)
Let cnt_i = [E_{X_i} = T_i] + [E_{Y_i} = T_i] so cnt_i \in \{0, 1, 2\}
If at any moment we detect a triplet with cnt_i = 0 then there is a contradiction and the answer is zero.
If cnt_i = 1 then let k be the one from \{X_i, Y_i\} with E_k = T_i then we know that f(A_t, p) must be equal to T_i in any valid assignment because thatâs the only way to satisfy the triplet, now lets iterate over all the triplets that k is a member of and update their cnts
If no contradiction is detected, then all triplets that have not been visited in the last stage have cnt_i = 2 which we deal with in the second stage.
Second Stage (meet-in-the-middle, SOS)
Letâs build a graph where the vertices are the variables for which we have not assigned any values yet, and the edges are whether there a triplet with cnt_i = 2 between them
Lemma: for each connected component in this graph the value E_v of its nodes is the same.
Proof: assume that itâs wrong then there exists at least two nodes u, v with an edge between them for which E_u \neq E_v WLOG assume E_u < E_v if the triplet between them is c then by definition cnt_c \leq 1 but this canât happen since the first stage doesnât terminate until it deals with all constraints with cnt_c \leq 1
Observations:
- Each connected component is independent from other components
- If v is the value on the edges of a connected component then an assignment in which we choose a subset S of its vertices, set their value v and set the values of other vertices to values in the half-open range [0, v) is valid if and only if S is a vertex cover of the connected component
Let V be the set of vertices of one maximal connected component and E be its edges, then if S is a vertex cover of the component then its contribution to the answer would be v^{|V| - |S|} in other words the number of valid assignments for this components is \sum_{k = 1}^{|V|} g(k, V, S) v^{|V| - |S|} where g(k, V, S) counts the number of vertex covers of size k of the component
Lemma: g(k, V, S) canât be computed in polynomial time unless \mathcal{P} = \mathcal{NP}
Proof: assume that can be computed in polynomial time then for any graph we can use it to binary search for smallest k for which g is non zero to get the minimum vertex cover (MVC) but MVC is a known \mathcal{NP}-hard problem and solving it polynomial time imply that \mathcal{P} = \mathcal{NP} a contradiction (unless indeed \mathcal{P} = \mathcal{NP} which is not know until now)
When dealing with \mathcal{NP} problem meet-in-the-middle technique is often helpful, letâs forget about g as we will compute that summation without computing its terms, lets first solve the problem of counting the number of vertex covers of a graph (V, E) then extend our solution to solve our problem, letâs split the vertices in half V_1 = 1..\lfloor\frac{|V|}{2}\rfloor and V_2 = V - V_1
Lets try all subsets of vertices of V_1 and check if they could be part of a vertex cover by iterating over all edges, let an edge be u, v then there are 3 cases
- u, v \in V_1 \implies at least one of u or v must be in the subset
- u, v \notin V_1 \implies do nothing
- WLOG u \in V_1, v \notin V_1 \implies v must be in whatever subset we choose from V_2
Let V' be the vertices from the third case then we want to count the number of subsets S_2 of V_2 such that V' \subseteq S_2 and it covers all edges contained inside it, this can be implemented in O(m 3^{|V|/2}) which is too slow or in O(m 2^{|V|/2}) using SOS (sum over subsets) technique
To extend this solution to our problem notice that in SOS dp_{subset} initially is whether the subset covers the edges contained inside V_2 or not, if that boolean value is multiplied by \prod_{v \in V_2 - subset} E_v then the answer to our original problem can be computed in O(m 2^{|V|/2})
SOLUTIONS:
Setter's Solution
const int MAX = 40, hMAX = (MAX + 1)/2, MAXE = MAX*MAX, MAXM = MAX*MAX;
int f[1 << hMAX];
int fr[MAXE], to[MAXE];
bool in_range(int s, int e, int x){
return s <= x && x <= e;
}
void build(int L, int R, int *f, int *fr, int *to, int m, int *powers){
int N = R-L+1;
for(int msk = 0; msk < (1 << N); msk++) {
f[msk] = 0;
bool is_cover = 1;
loop(e, m) if(in_range(L, R, fr[e]) && in_range(L, R, to[e])){
int a = fr[e] - L;
int b = to[e] - L;
int ia = (msk >> a) & 1;
int ib = (msk >> b) & 1;
is_cover &= ia || ib;
if(!is_cover) break;
}
int cnt = N;
loop(i, N) if((msk >> i) & 1) {
cnt--;
}
// f[msk] = powers[cnt] * is_cover;
f[msk] = powers[cnt] * is_cover;
}
// prArr(f, (1 << N), int);
for(int b = 0;b < N;b ++) {
loop(msk, (1 << N)) if(!(msk & (1 << b))) f[msk] = add(f[msk], f[msk ^ (1 << b)]);
}
// prArr(f, (1 << N), int);
}
int solve(int N, int k, int *fr, int *to, int m) {
static int powers[2*MAX];
powers[0] = 1;
loop(i, N) powers[i+1] = mul(powers[i], k);
build(N/2, N-1, f, fr, to, m, powers);
int n = N/2, res = 0;
loop(msk, (1 << n)) {
int other_msk = 0;
int cnt = n;
loop(i, n) if((msk >> i)&1){
cnt--;
}
bool is_cover = 1;
loop(e, m) {
int a = fr[e], b = to[e];
if(a >= n && b >= n) continue;
if(a < n && b < n) {
int ia = (msk >> a) & 1;
int ib = (msk >> b) & 1;
is_cover &= ia || ib;
continue;
}
if(a > b) swap(a, b);
assert(a < n);
if(msk & (1 << a)) continue;
other_msk |= 1 << (b - n);
}
if(!is_cover) continue;
res = add(res, mul(f[other_msk], powers[cnt]));
}
return res;
}
int N, M;
bool has_contradiction = 0;
bool is_infinite = 0;
map<int, int> Z[MAXM];
int A[MAXM], B[MAXM], target[MAXM];
int lim[MAX], val[MAX];
bool done[MAXM];
queue<int> q;
vi V;
int solve(int p) {
//cerr << "solve " << p << endl;
loop(i, N) lim[i] = INT_MAX, val[i] = -1;
loop(i, M){
target[i] = 0;
if(Z[i].count(p)) target[i] = Z[i][p];
lim[A[i]] = min(lim[A[i]], target[i]);
lim[B[i]] = min(lim[B[i]], target[i]);
done[i] = 0;
}
while(!q.empty()) q.pop();
//cerr << "make q" << endl;
loop(i, M){
int a = A[i], b = B[i];
if(lim[a] > lim[b]) swap(a, b);
int ways = 0;
int fa = lim[a] == target[i];
int fb = lim[b] == target[i];
ways = fa + fb - fa*(a == b);
if(ways == 0) {
//cerr << "contradiction" << endl;
has_contradiction = 1;
return 0;
}
if(ways == 1) q.push(i), done[i] = 1;
}
//cerr << "deduct" << endl;
vi usable;
while(!q.empty()){
int i = q.front(); q.pop();
int a = A[i], b = B[i];
if(lim[a] > lim[b]) swap(a, b);
if(val[a] == target[i] || val[b] == target[i]) continue;
usable.clear();
if(val[a] == -1 && lim[a] == target[i]) usable.pb(a);
if(val[b] == -1 && lim[b] == target[i] && a != b) usable.pb(b);
//cerr << "@" << i << " ";
if(usable.empty()){
//cerr << "contradiction" << endl;
has_contradiction = 1;
return 0;
}
assert(usable.size() == 1);
a = usable[0];
val[a] = target[i];
//cerr << "set " << a << " to " << target[i] << endl;
loop(j, M) if(!done[j] && (a == A[j] || a == B[j])) {
done[j] = 1;
q.push(j);
}
}
loop(i, N) if(lim[i] == INT_MAX) {
is_infinite = 1;
return 0;
}
//cerr << "VC" << endl;
set<int> freeVals;
loop(i, N) if(val[i] == -1) freeVals.insert(lim[i]);
int ret = 1;
for(int v : freeVals) {
V.clear();
loop(i, N) if(val[i] == -1 && lim[i] == v) V.pb(i);
int m = 0;
loop(c, M) if(binary_search(all(V), A[c]) && binary_search(all(V), B[c])){
int a = lower_bound(all(V), A[c]) - V.begin();
int b = lower_bound(all(V), B[c]) - V.begin();
if(a > b) swap(a, b);
fr[m] = a;
to[m] = b;
m++;
}
ret = mul(ret, solve(sz(V), v, fr, to, m));
}
return ret;
}
void test_case(){
set<int> P;
scanf("%d %d", &N, &M);
// cerr << "\t" << N << " " << M << endl;
map<pi, map<int, int> > mem;
int i = 0;
bool return_zero = 0;
loop(j, M){
scanf("%d %d ", A + i, B + i);
A[i]--, B[i]--;
int k; scanf("%d", &k);
Z[i].clear();
for(;k;k--) {
int p, e; scanf("%d %d", &p, &e);
assert(p);
Z[i][p] += e;
P.insert(p);
}
int a = A[i], b = B[i];
if(a > b) swap(a, b);
pi p(a, b);
if(mem.count(p)) {
if(mem[p] != Z[i]) {
return_zero = 1;
}
continue;
}
mem[p] = Z[i];
i++;
}
if(return_zero) {
puts("0");
return;
}
// cerr << "M was " << M << " will become " << i << endl;
M = i;
set<int> constrained;
loop(i, M) constrained.insert(A[i]), constrained.insert(B[i]);
// cerr << constrained.size() << " vs " << N << endl;
is_infinite = sz(constrained) != N;
has_contradiction = 0;
int res = 1;
for(int p : P) {
res = mul(res, solve(p));
// //cerr << has_contradiction << endl;
if(has_contradiction) {
puts("0");
return ;
}
}
if(is_infinite) {
puts("-1");
return ;
}
printf("%d\n", res);
}
int main(){
#ifdef HOME
freopen("in.in", "r", stdin);
#endif
int T; scanf("%d", &T);
while(T--) test_case();
return 0;
}
