1514.md (7753B)
1 Source: https://codeforces.com/blog/entry/89810 2 3 ### [1514A - Perfectly Imperfect Array](/contest/1514/problem/A "Codeforces Round 716 (Div. 2)") 4 5 If any element is not a perfect square, the answer is yes. Otherwise, the answer is no, because $a^2*b^2*...=(a*b*...)^2$. 6 7 Code link: <https://pastebin.com/s83sFt3G> 8 9 ### [1514B - AND 0, Sum Big](/contest/1514/problem/B "Codeforces Round 716 (Div. 2)") 10 11 Let's start with an array where every single bit in every single element is $1$. It clearly doesn't have bitwise-and equal to $0$, so for each bit, we need to turn it off (make it $0$) in at least one of the elements. However, we can't turn it off in more than one element, since the sum would then decrease for no reason. So for every bit, we should choose exactly one element and turn it off there. Since there are $k$ bits and $n$ elements, the answer is just $n^k$. 12 13 Code link: <https://pastebin.com/0D8yL5WW> 14 15 ### [1514C - Product 1 Modulo N](/contest/1514/problem/C "Codeforces Round 716 (Div. 2)") 16 17 So first observe that the subsequence can't contain any element that **isn't** coprime with $n$. Why? Because then its product won't be coprime with $n$, so when you take it modulo $n$, it can't be $1$. In mathier words, $gcd(prod \space mod \space n,n)=gcd(prod,n) \neq 1$. Now, let's take all elements less than $n$ and coprime with it, and let's look at their product modulo $n$; call it $p$. If $p$ is $1$, you can take all these elements. Otherwise, you should take them all except for $p$. It belongs to them because $p$ is coprime with $n$, since $gcd(p \space mod \space n,n)=gcd(p,n)=1$ since all the elements in $p$ are coprime with $n$. 18 19 Code link: <https://pastebin.com/JnjZ3SQm> 20 21 **Bonus task:** solve it for $n \le 10^{12}$. 22 23 ### [1514D - Cut and Stick](/contest/1514/problem/D "Codeforces Round 716 (Div. 2)") 24 25 Suppose the query-interval has length $m$. Let's call an element super-frequent if it occurs more than $\lceil\frac{m}{2}\rceil$ times in it, with frequency $f$. If there's no super-frequent element, then we can just put all the elements in $1$ subsequence. Otherwise, we need the partitioning. Let's call the rest of the elements (other than the super-frequent one) good elements. One way to partition is to put all the $m-f$ good elements with $m-f+1$ super-frequent elements; then, put every remaining occurrence of the super-frequent element in a subsequence on its own. The number of subsequences we need here is then $1+f-(m-f+1)=2*f-m$. There's no way to improve this, because: for every subsequence we add, the number of occurrences of the super-frequent element minus the number of good elements is at most $1$, so by making it exactly $1$ in each subsequence, we get an optimal construction. Now, the problem boils down to calculating $f$. Note that calculating the most frequent element in general is a well-known slow problem. It's usually solved with MO's algorithm in $O(n\sqrt{n}log(n))$, maybe with a tricky optimization to $O(n\sqrt{n})$. However, notice that we only need the most frequent element if it occurs more than $\lceil\frac{m}{2}\rceil$ times. How can we use this fact? 26 27 #### Randomized solution 28 29 We can pick ~$40$ random elements from our range to be candidates for the super-frequent element, then count their occurrences and maximize. If there's a super-frequent element, the probability it's not picked is at most $2^{-40}$, which is incredibly small. 30 31 To count the number of occurrences of an element in a range, we can carry for each element a vector containing all the positions it occurs in increasing order. Then, `upper_bound(r)-lower_bound(l)` gives us the number of occurrences in $O(log(n))$. 32 33 Code link: <https://pastebin.com/APHEtfge> 34 35 #### Deterministic solution 36 37 Observe that if a range has a super-frequent element, and we split it into $2$ ranges, then this element must be super-frequent in one of them. Now suppose we create a segment tree where every node $[l;r]$ returns an element in the range, and suppose every node merges the $2$ elements returned by its children as follows: count their occurrences in $[l;r]$ and pick whichever occurs more. In general, that doesn't return the most frequent element. However, if there's a super-frequent element, it must return it! That's because if there's a super-frequent element in $[l;r]$, it must be super-frequent in one of its children, so by induction the segment tree works. The time complexity is $O(nlog^2(n))$. 38 39 Code link: <https://pastebin.com/qeGxT0W2> 40 41 There are also tons of $O(n\sqrt{n})$ solutions that should pass if the operations are simple enough. 42 43 **Bonus task:** solve it in $O(nlog(n))$. 44 45 ### [1514E - Baby Ehab's Hyper Apartment](/contest/1514/problem/E "Codeforces Round 716 (Div. 2)") 46 47 Throughout the editorial, I'll call the first type of queries OneEdge and the second type ManyEdges. 48 49 The basic idea behind this problem is to find a few edges such that every path that could be traversed in your graph could be traversed using only these edges. With that motivation in mind, let's get started. 50 51 The first observation is: the graph has a hamiltonian path. To prove this, suppose you split the graph into $2$ halves, each containing some of the nodes. Then, we'll proceed by induction. Suppose each half has a hamiltonian path. I'll describe a way to merge them into one path. First, let's look at the first node in each path and ask about the edge between them. Suppose it's directed from the first to the second one. Then, I'll start my new merged path with the first node, remove it, and repeat. This works because no matter which node follows it, it sends an edge out to it. This is best described by the following picture: 52 53  54 55 We start with the $2$ hamiltonian paths we got by induction, then we query that red edge. We find that it's from the grey node to the white node. We then put our grey node as the start of the path and continue doing that with the rest of the nodes, and we don't care which node will follow it, because the edge is out from the black node either way! 56 57 If everything falls into place in your mind, you should recognize that this algorithm is merge sort. We just run merge sort on the nodes of the graph, using the comparator OneEdge. That gives you a hamiltonian path in $nlog(n)$ queries. 58 59 Now that we have a hamiltonian path, every edge that goes forward in it is useless, since you can just walk down the path itself: 60 61  62 63 So let's focus on the edges going backwards. Suppose we iterate through the hamiltonian path from its end to its beginning, looking at the edges going back from the nodes we met. An edge going backwards from the current node is important only if it goes back further than any of the edges we've met so far. That's because we can take a (much less direct) route instead of this edge if it doesn't go so far back: 64 65  66 67 Now with a few more edges we can form all the paths! How do we get these edges? We can use $2$ pointers. Let's iterate through the hamiltonian path from its end to its beginning, carrying a pointer $p$ that tells us how far back the edges we met so far can go. To update $p$, let's ask ManyEdges from the node we're currently at, to the first $p$ nodes in the hamiltonian path. While the answer is $1$, we'll keep decreasing $p$. This algorithm calls ManyEdges $2n$ times, since every time we call it, it either returns $0$ and the node we're at decreases, or it returns $1$ and $p$ decreases. 68 69 Code link: <https://pastebin.com/RU1yA697> 70 71 **Bonus task:** can you get the hamiltonian path using insertion sort instead?