1322C - Instant Noodles Writeup

1332c.md

Task

Type: Div1C https://codeforces.com/contest/1322/problem/C

Problem

Given a bipartite graph of n vertices (labelled 1 to N) and m edges. Let L and R be the disjoint set of vertices. Formally, "disjoint" means that there exists no x and y such that x ∈ L and y ∈ R and edge (x, y) exists. Each vertex i has a value c[i].

For all S ∈ L, N(S) is the set of vertices in R adjacent to any vertex in S.

For all S ∈ L, f(S) is the sum of all c[i] for all vertex in N(S).

The task is to compute the gcd of f(S) over all S ∈ L.

gcd is the greatest common divisor and the gcd of an empty set is 0.

Constraints

$$1 <= n, m <= 5 x 10^5 1 <= c[i] <= 10^12$$

Initial Intuitions

1. We only need to consider unique sets of values of f(S). Repeated values will not affect the gcd.

2. We need to somehow enumerate the possible sums that can occur.

3. Some sums of vertices in R cannot occur.

4. Enumeration of sums can be done in an incremental manner. That is, to add and not to add some vertex. But this could be subject to some constraints.

Main observations

Reduced Set

1. Some pair of vertices can be tied together. Meaning, that if vertex x is in some N(S), then vertex y must be in it as well. The necessary condition for this to happen is that vertex x and vertex y must have the exactly same neighbouring set in L. The neighboring set of some a vertex in R is the set of all vertices in L that it's adjacent to.

   If x and y have different neighbouring sets, then you can choose to include only one of them in some partial set of vertices.

2. If some vertices are tied together, then we can treat them as a single vertex. Hence, we group all vertices of the same neighboring set and turn them into a single vertex with its value being the sum of c[i]'s.

Subset sums

1. Now that we have built a reduced set of vertices in R, we can incrementally build sums without constraints. That is, all possible combinations of add and not add can happen. This is just the subset sum of the values.

GCD of Subset Sum

2. What is the gcd of all subset sums of a given set of values? Well, it has to be at least the gcd of single-element subsets - let this value of be G. We know that when we start to enumerate subsets of size 2, 3, 4, these sums are divisible by G. Why? Because they are sums of numbers that are divisible by G. Now, can it be higher than G? No, because gcd cannot increase when you consider more numbers.

Implementation

ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
  int n, m;
  cin >> n >> m;
  vector< vector<int> > adj(n);
  vector<long long> c(n);
  for (int i = 0; i < n; i++) cin >> c[i];
  for (int i = 0, x, y; i < m; i++) {
    cin >> x >> y;
    adj[--y].push_back(--x);
  }
  map<vector<int>, long long> group;
  for (int i = 0; i < n; i++) {
    if (adj[i].empty()) continue;
    sort(adj[i].begin(), adj[i].end());
    group[adj[i]] += c[i];
  }
  long long g = 0;
  for (auto e : group) g = gcd(g, e.second);
  cout << g << '\n';
}