Codeforces Round #400

February 26, 2017, 6:40 am

Thursday morning, Codeforces hosted the ICM Technex 2017 round. Unfortunately, I wasn't able to compete, but I thought two of the problems were interesting.

This was a nice 2-SAT style problem. We have a set of \(M\) doors, each of which is locked or unlocked. We also have \(N\) switches (toggling a switch toggles the state of all doors connected to that switch). Furthermore, each door is connected to exactly two switches. We want to know if it is possible to unlock all the doors by toggling some subset of the switches.

So we create a graph with \(2N\) nodes and \(2M\) edges. Each switch \(i\) is associated with two nodes: one of these represents toggling switch \(i\) (denoted by \(u_i\)) and the other represents not toggling switch \(i\) (denoted by \(v_i\)). Each door is represented by two edges. If the door is initially unlocked, then we must either toggle both its switches, or toggle neither. Thus, if the door is connected to switches \(i\) and \(j\), we add undirected edges \((u_i, u_j)\) and \((v_i, v_j)\). On the other hand, if the door is initially locked, we must toggle one of its switches but not the other, so we add edges \((u_i, v_j)\) and \((v_i, u_j)\). Now the nodes of our graph are partitioned into connected components that must be assigned the same truth value: if a node \(u_i\) belongs to a component assigned "true", then we must toggle switch \(i\); if \(u_i\) belongs to a component assigned "false", then we must not toggle switch \(i\). Similarly, if \(v_i\) belongs to a "true" component, then we must not toggle switch \(i\); if \(v_i\) belongs to a "false" component, then we must toggle switch \(i\).

All that remains is to determine whether there is a truth assignment for our components that is consistent: that is, there does not exist an \(i\) with \(u_i\) and \(v_i\) receiving the same truth value. This is the case exactly when, for all \(i\), \(u_i\) and \(v_i\) belong to different components.

This can be implemented by explicitly building the graph and finding the connected components, or by using a union-find data structure.

In this problem, we are asked to evaluate a function \(F_k(n)\), where \(F_k\) is defined as a composition of \(k + 1\) functions, alternating between \(f\) and \(g\). \(f(n)\) is defined to be the number of ordered coprime pairs \((x, y)\) where \(x + y = n\), and \(g(n)\) is the summatory function of this function: \(g(n) = \sum_{d|n} f(d)\).

First, it is not hard to see that \(f\) is Euler's \(\phi\)-function: \(f(n)\) is the number of positive integers at most \(n\) that are coprime to \(n\). This is because \(\gcd(x, y) = \gcd(x, x + y) = \gcd(x, n)\), and after fixing \(x\), \(y\) is already determined.

Now, it turns out that \(g\) is actually the identity function (\(g(n) = n\) for all positive integers \(n\)). To prove this, recall that \(f\) is multiplicative: that is, for coprime positive integers \(a\) and \(b\), \(f(ab) = f(a)f(b)\), and that the summatory function of a multiplicative function is also multiplicative. Thus, \(g\) is multiplicative, and it will suffice to show that \(g(p^k) = p^k\) for primes \(p\) and nonnegative integers \(k\). To do this, note that the divisors of \(p^k\) are \(1, p, p^2, \dots, p^k\), and that \(f(p^i) = p^i - p^{i-1}\). Then \(g(p^k) = 1 + \sum_{i=1}^{k} p^{i} - p^{i-1} = p^k\) (this is a telescoping sum). Since \(g(p^k) = p^k\) and \(g\) is multiplicative, \(g(n) = n\) for all positive integers \(n\). (This is because we can decompose any \(n\) into prime powers, all of which are clearly coprime.)

So all that's left is applying \(f\) to \(n\) \(10^{12}\) times. First, to apply \(f\) once, we just have to find the prime factorization of \(n\) (recall that \(f\) is multiplicative); this takes \(O(\sqrt{n})\) time. Since \(n\) can be up to \(10^{12}\), it seems as if we have to do \(10^{18}\) operations.

However, repeated application of \(f\) decreases \(n\) very rapidly. To formalize this, we make two observations: first, if \(n\) is even, then \(f(n) \leq n/2\). This follows from the fact that if \(n\) is even, every even integer up to \(n\) is not coprime with \(n\). Second, if \(n \geq 3\), \(f(n)\) is even. This is not too hard to prove: \(f(p^k) = p^k - p^{k-1}\), which is even if \(k \geq 2\) or \(p\) is odd. Since \(f\) is multiplicative, if \(n\) is not \(1\) or \(2\), then \(f(n)\) is even.

So if \(n\) is initially odd, a single application of \(f\) will make it even. Then we need only \(O(\log n)\) iterations to reduce \(n\) to \(1\). Thus, even though the given bound for \(k\) is \(10^{12}\), the answer won't change for \(k \geq 40\) or so, and we can stop early if \(n\) ever becomes \(1\), so our solution will easily run in time.