MINGCTREE0 - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Medium

PREREQUISITES:

Sieve, DP

PROBLEM:

For a tree and an array A, f(A) is defined as follows:

  • Edge (u, v) is given the value A_u + A_v.
  • f(A) is the GCD of all edge values.

Given a tree and an array, compute the minimum possible f(A) across all rearrangements of A.

EXPLANATION:

Let’s try to decide when obtaining a GCD of g is possible for some rearrangement.

A necessary (but not sufficient) condition for this is that we must ensure A_u + A_v \equiv 0 \pmod g for each edge (u, v).
This condition is quite restrictive. In particular, observe that if A_1 is fixed,

  • All the neighbors of 1 must have values congruent to -A_1 \bmod g.
  • All the neighbors of the neighbors of 1 must have values congruent to A_1\bmod g.
  • In general: any vertex at an even distance from 1 must have its value be congruent to A_1\bmod g, while any vertex at an odd distance must have its value be -A_1\bmod g.

Let there be L vertices at an even distance from 1, and N-L vertices at an odd distance.
With the above observation in mind, suppose we knew, for each pair (g, r) with 0 \leq r \lt g, the value ct(g, r): the number of elements of A that are congruent to r\bmod g.

Then, observe that:

  • If there’s some r such that ct(g, r) = L and ct(g, g-r) = N-L, we’ll be able to place the corresponding L elements at even distances and everything else at odd distances, and achieve what we want.
  • If ct(g, r) = N for some r, then if r = 0 or 2r = g we have what we want irrespective of arrangement.
  • If both above cases fail, there’s no way to assign values to make all edge sums be 0 modulo g.

Even if we’re able to satisfy the condition for all the edges, this only guarantees that the gcd will be a multiple of g, and not necessarily g itself - we’ll take care of that later.

The very first roadblock seems to be even computing all the ct(g, r) values, since there are technically \mathcal{O}(M^2) such pairs (where M = 2\text{max}(A) is the maximum possible gcd we need to care about).
However, observe that if, for some g, there are \geq 3 distinct r for which ct(g, r) \gt 0, it’s definitely impossible for g to be valid.

This allows the following algorithm to be quite fast:

  • Iterate g from 1 to M.
  • Now, iterate over the distinct elements of A.
  • Suppose we’re looking at x. Then,
    • Increase ct(g, x\bmod g) by freq(x).
    • After this, if there are \geq 3 distinct remainders modulo g, stop immediately and ignore this g. Otherwise, continue on.

This early break heuristic might not seem like much, but it in fact ensures that the algorithm runs in \mathcal{O}(M\log M) time.
To see why, fix g and look at some interval [k\cdot g, (k+1)\cdot g).
In this interval, we’ll process at most two distinct elements: if we process a third, we break out immediately.
So, we do \mathcal{O}(1) work per interval of length g.
There are \frac{M}{g} such intervals, so the overall work, summed up across all g, is \mathcal{O}(M\log M).

Rather than directly compute the minimum, let’s try to count the number of arrangements corresponding to each GCD g.
If we’re able to do this, then the answer is just the minimum g with a non-zero count.
For simplicity, we’ll consider arrangements of indices rather than values, to avoid having to deal with duplicates and such ourselves: this is fine since we only care about whether it’s non-zero or not in the end.

So, define dp_g to be the number of arrangements with GCD equal to g.
With the precomputation done, let’s once again fix a value of g and see how to compute this.

Of course, if some g has \geq 3 distinct remainders we know for sure no valid arrangement exists, so dp_g = 0.

Next, suppose g has only one remainder r corresponding to it.
If r \neq 0 and r \neq \frac{g}{2}, again we have dp_g = 0.
Otherwise, any arrangement gives (a multiple of) g.
So, we can set dp_g = N! to begin with, and then subtract out dp_{k\cdot g} for each k \gt 1. This is a fairly standard Mobius-style DP.

Finally, suppose g has remainders r_1 and r_2.
If (r_1 + r_2) \not\equiv 0 \pmod g, dp_g = 0.
Similarly, if ct(g, r_1) \neq L and ct(g, r_1) \neq N-L, we’ll have dp_g = 0.
That leaves us with:

  • If ct(g, r_1) = L, there are L! \cdot (N-L)! arrangements giving a multiple of g.
  • Similarly, if ct(g, r_1) = N-L, there are another L! \cdot (N-L)! arrangements giving a multiple of g.
    Note that these two conditions are not either-or: both can trigger when L = N-L in which case you’ll need to add them.

Again, after initializing dp_g you can subtract out dp_{k\cdot g} for all k\gt 1 to obtain the true value of dp_g.

This takes \mathcal{O}(M\log M) time where M = 2\cdot\max(A).
Since \max(A) is bounded, this is fast enough.

One point of concern here is that the dp_g values can grow very large.
This means we must compute them modulo something - say, modulo a prime P.
But that brings in another issue: since we care about whether a value is zero or non-zero, what if we end up with the value being exactly P (so it’s positive), but under mod it becomes 0?

A reasonably safe way to get around this is to just use a random large prime P, since making an anti-test requires knowing the specific prime P.
For extra safety you can also compute using multiple different primes and test if the result is non-zero with respect to at least one of them.

TIME COMPLEXITY:

\mathcal{O}(N + M\log M) per testcase, where M = \max(A).

CODE:

Editorialist's code (C++)
2 Likes