Codeforces Round #1062

1062 is a div 4 contest, so it was a bit easier. the hardest problems were about 1600

Problem A

Simply checking a=b and b=c and c=d is sufficient (transitivity of equivalence relationships)

Problem B

We need to check if a string is a permutation of another string. This can be achieved by checking that the frequency of each character is the same in both strings. Since strings only comprise of 26 characters, we can use a simple array of size 26 to count the frequency of each character in both strings and compare them.

Problem C

The key to this problem is that the only way there can be no movement is if all are even or all odd.

Suppose WLOG (with respect to the parity of the majority of elements) that all are even, and there exists some element which is odd. (in particular not all even) Suppose we want to swap arbitrary even elements at positions a, b, with the odd element at c, with a != b != c. Then we can swap a and c, then b and c, then a and c again, which is equivalent to swapping a and b

Thus, the answer is the sorted list if there are both odds and evens, otherwise don't touch the list

Problem D

We know that $gcd(a,b)=1\iff a, b$ are coprime. The problem can be stated as $$\min_x \exists a_i\in A, gcd(x, a_i)=1$$ Let $F(x)$ map $x$ to a set of it's prime factors. The problem can be rephrased through set theory as $$\min_x \exists a_i\in A, F(x) \cap F(a_i) = \emptyset$$

It is relatively obvious that the $x$ that we are looking for is prime. If $x$ was not prime, then it would have a prime factor $p$ such that $p \in F(x)$. Then, if $p \in F(a_i)$ for some $a_i$, then $F(x) \cap F(a_i) \neq \emptyset$, and if $p \notin F(a_i)$ for some $a_i$, then we can replace $x$ with $p$ and get a smaller number that satisfies the condition.

This problem can be solved by recognizing the the answer has to be one of the first 16 primes. We first observe that $a_i\le10^{18}$. Suppose for contradiction that the first 16 primes all fail the condition, namely $$\forall x\in \{p_1, p_2, \ldots, p_{16}\}, \forall a_i\in A, F(x) \cap F(a_i) \ne \emptyset$$ In particular, we know that $F(x)=x$, hence $$\forall x\in \{p_1, p_2, \ldots, p_{16}\}, \forall a_i\in A, x\in F(a_i)$$ This is clearly a contradiction, since the product of the first 16 primes is $32589158477190044730>10^{18}$, and thus $\exists a_i$ such that $F(a_i)$ does not contain one of the first 16 primes.

The threshold for the number of primes required was checked using the primordial numbers (found here).

Hence, we can check for the presence of each of the first 16 primes in the prime factorization of each number in the list, and return the smallest prime that is not present in any of the numbers. This is O(n).

Problem E

Binary search can be used to find the shortest time taken for the friend to get to a teleporter. For this to be true, it must be shown that the maximum number of teleporters placed is monotonic with respect to the time. In particular, by reducing the shortest time taken for a friend to get to a teleporter, the maximum number of teleporters that can be placed can be increased. This is intuiatively true because by reducing the time, you can place more teleporters closer to the friends, and thus more teleporters can be placed.

Hence, binary search can be used to find the shortest time for which the number of teleporters placed is at least $k$.

It is possible in $O(n)$ time to determine if $t$ is a possible solution. We check each gap between friends, and place teleporters at least $t$ away from the endpoints of the gap. In particular, for a gap between friends at $a_i$ and $a_{i+1}$, we can place $max(0, (a_{i+1}-t) - (a_i+t) + 1)$ teleporters in the gap. We can then check if the total number of teleporters placed is at least $k$.

One note is that it is also important to check the edge cases where the first and last friends are at the edges of the line, and we can place teleporters before the first friend and after the last friend.

The final step is to reconstruct the solution. The reconstruction follows the same logic as the check, and we can place the teleporters greedily.

Problem F

I think the best way to have an intuiative understanding of the solution to this problem is to ensure you have an intuiative understanding of LCA. In particular, the most important property to know is that, given $K$ is a set of nodes, and $n$ is a node, then $$LCA(K) = n \iff \lnot (\exists n_0\text{ which is a child of }n, \forall k\in K, k\text{ is a ancestor of } n_0)$$

Specifically, we are asking for the elements of $K$ to be in at least two different subtrees of $n$. Both directions are relatively easy to prove. The forward direction is true because if all elements of $K$ are in the same subtree of $n$, then the LCA of $K$ is in that subtree, and thus cannot be $n$. The reverse direction is true because if there exists a child $n_0$ of $n$ such that all elements of $K$ are in the subtree of $n_0$, then the LCA of $K$ is in the subtree of $n_0$, and thus cannot be $n$.

Using a DFS, we can keep track of how many children are in each subtree of a given node The final "subtree" is the subtree containing the parent of the node (trees are reversible in this way, we can think of it as a rerooting). The number of nodes in this final "subtree" is determinable by the number of nodes in the tree minus the number of nodes in the subtrees of the node.

Consider the contribution of a single node $n$ to the final result. We can consider rerooting this tree at some node $n_1$ in some subtree $S$ of $n$. By rerooting at $n_1$, the subtree $S$ cannot supply nodes towards $K$, as they would be ancestors (and not descendants) of $n$. However, all other subtrees area still in contention. Hence, as long as the other subtrees (at least two of them) provide enough nodes (at least $k$), then the LCA of $K$ is still $n$. Note that if the above works for $n_1$, then it works for all nodes in $S$. In particular, this means that node $n$ is in all $S_{n_i}\forall n_i\in S$, which contributes 1 to $|S_{n_i}|\forall n_i\in S$, which contributes $|S|$ to the final answer.

As a minor edge case, we also need to consider if the tree is rooted at $n$. In this case, the subtree containing the parent of $n$ does not exist, and thus we need to check if there are at least two subtrees of $n$ which have at least $k$ nodes.

Hence, the final algorithm is as follows:

1. Run a DFS to find the size of each subtree, including the "subtree" containing the parent
2. For each node, remove each subtree, and check if within the remaining subtrees if there are at least two subtrees which combined have at least k nodes.
3. If so, add the size of the removed subtree to the final answer
4. Remember to also consider the edge case where the tree is rooted at the node in question

Problem G

Problem G is a typical DP problem. The first important observation is that $$\sum_{replaced} c_i = \sum c_i - \sum_{kept} c_i$$

Hence, instead of minimimzing the cost of the items which are replaced, we can maximize the cost of the items which are kept.

The second important observation is that the kept elements must form a increasing subsequence. Hence, we can use a DP to find the maximum cost of an increasing subsequence. This number can then be subtracted from the total cost to find the minimum cost of the replaced elements.