1364.md (9955B)
1 Source: https://codeforces.com/blog/entry/78781 2 3 ### [1364A - XXXXX](/contest/1364/problem/A "Codeforces Round 649 (Div. 2)") 4 5 Let's start with the whole array. If every element in it is divisible by $x$, the answer is $-1$; if its sum isn't divisible by $x$, the answer is $n$. Otherwise, we must remove some elements. The key idea is that removing an element that is divisible by $x$ doesn't do us any benefits, but once we remove an element that **isn't**, the sum won't be divisible by $x$. So let the first non-multiple of $x$ be at index $l$, and the last one be at index $r$. We must either remove the prefix all the way up to $l$ or the suffix all the way up to $r$, and we'll clearly remove whichever shorter. 6 7 Code link: <https://pastebin.com/j2Y8AJBA> 8 9 Alternatively, we can notice that this means the answer is either a prefix or a suffix, so we can simply bruteforce them all. 10 11 ### [1364B - Most socially-distanced subsequence](/contest/1364/problem/B "Codeforces Round 649 (Div. 2)") 12 13 TL;DR the answer contains the first element, last element, and all the local minima and maxima, where a local minimum is an element less than its 2 adjacents, and a local maximum is an element greater than it 2 adjacents. 14 15 Let's look at the expression in the problem for 3 numbers. If $a \gt b$ and $b \gt c$ or if $a \lt b$ and $b \lt c$, $|a-b|+|b-c|=|a-c|$, so it's never optimal to use $a$, $b$, and $c$ in a row because you can use just $a$ and $c$ and achieve a shorter subsequence. If you keep erasing your $b$'s from the original permutation, you'll end up with the first element, the last element, and the local minima and maxima. You can see that erasing any of them would decrease the expression, so this is the optimal answer. 16 17 Code link: <https://pastebin.com/e2HHuKFY> 18 19 ### [1364C - Ehab and Prefix MEXs](/contest/1364/problem/C "Codeforces Round 649 (Div. 2)") 20 21 The key observation is: if for some index $i$, $a_i \neq a_{i-1}$, then $b_i$ must be equal to $a_{i-1}$, since it's the only way to even change the prefix $MEX$. We can use this observation to fill some indices of $b$. Now, how do we fill the rest? Let's start by **avoiding** every element in $a$. Something special will happen if we avoid using any element from $a$ again. If we look at the first $i$ numbers in $b$, $a_i$ will indeed be excluded, so $MEX({b_1, b_2, \ldots, b_i}) \le a_i$. Now we need to make it as big as possible. How do we make it as big as possible? The logical thing to do is to fill the rest of $b$ with the numbers not in $a$ **in increasing order**. It turns out this construction always satisfies the conditions. Indeed, if we look at the first $i$ elements in $b$, every element less than $a_i$ will be present because $a_i \le i$ and we added the rest of the elements in increasing order. 22 23 Code link: <https://pastebin.com/x9VtuBym> 24 25 ### [1364D - Ehab's Last Corollary](/contest/1364/problem/D "Codeforces Round 649 (Div. 2)") 26 27 The common idea is: if the graph is a tree, you can easily find an independent set with size $\lceil\frac{n}{2}\rceil$ by bicoloring the vertices and taking the vertices from the more frequent color. Otherwise, the graph is cyclic. Let's get a cycle that doesn't have any edges "cutting through it." In other words, it doesn't have any pair of non-adjacent vertices connected by an edge. If its length is at most $k$, print it. Otherwise, take every other vertex (take a vertex and leave a vertex) and you'll end up with a big enough independent set. How to find such cycle? 28 29 ### First solution 30 31 Let's do a dfs in our graph. In the very first time we hit a node that has a back-edge, we take the back-edge that goes to the deepest possible node to close our cycle. This cycle can't have any edges crossing it because none of our node's ancestors has a back-edge (by definition.) 32 33 Code link: <https://pastebin.com/wsCXuzGy> 34 35 ### Second solution 36 37 Let's get any cycle in the graph. Now, let's iterate over the edges that don't belong to the cycle. Whenever we meet one that "crosses the cycle," we use it to cut the cycle into 2 cycles with smaller length and keep any of them. When we finish, we'd have our desired cycle. 38 39 Code link: <https://pastebin.com/ezwEURKW> 40 41 ### [1364E - X-OR](/contest/1364/problem/E "Codeforces Round 649 (Div. 2)") 42 43 The common idea is: if we find the index that contains $0$, we can query it with every element in $p$ and finish in $n$ queries (if you didn't do that, pleaaase share your solution.) How to get this index? 44 45 ### First solution 46 47 Let's try to make a magic function that takes an index $i$ and tells us $p_i$. Assume you have an array $z$ such that $z_j$ is some index in the permutation that has a $0$ in the $j^{th}$ bit. Building our magic function with it turns out to be very easy. We'll just return $query(i,z_0)$&$query(i,z_1)$&$\ldots$&$query(i,z_{10})$. Why does that work? If $p_i$ has a $1$ in the $j^{th}$ bit, this expression will also have a $1$ because $p_i$ will make every single clause have a $1$. If it has a $0$, $query(i,z_j)$ will also have a $0$, making the whole expression have a $0$! 48 49 But how do we find $z$? This turns out to be very easy. We'll query random pairs of indices, see where the result has a $0$, and update $z$. We stop once we fill every index in $z$. This works quickly because for any bit, at least half the numbers from $0$ to $n-1$ will have a $0$. 50 51 Now we already have an $nlog(n)$ solution (call our magic function with every index,) but how to make less calls? Let's carry an index $idx$ that's supposed to have the index of $0$ in the end, and let $p_{idx}$ be stored in $val$. Initially, $idx$ is $1$ and $val$ could be found with our magic function. Now, let's iterate over the permutation. We'll query the current index, $i$, with $idx$. If the result isn't a subset of $val$, $p_i$ can't be $0$, so let's throw it in the trash. Otherwise, we'll make $idx$ equal to $i$ and use our magic function to update $val$. 52 53 Code link: <https://pastebin.com/kBQGrEqP> 54 55 **analysis** 56 57 In my analysis, I'll use $c$ to denote something that's clearly small but needs big math to analyze it, so it's better to omit these analysis (or something that I can't analyze *nervous chuckles*.) 58 59 Since every time $val$ is replaced with a subset of it, we only call our magic function at most $log(n)$ times, so the number of queries is at most $2n+log^2(n)+c$. 60 61 The cool thing about this solution is that it barely relies on randomness, so even if you run it for a million test cases, it would still pass. In fact, try to make it deterministic with $\frac{n}{2}$ more queries. 62 63 There's a nice speed-up, but it relies much more on randomness: ask your indices in a random order, and make an itsy bitsy edit in the magic function: if $val$ has a $0$ in the $j^{th}$ bit, you don't really need to query $i$ with $z_j$. You can set the $j^{th}$ bit in the result to $0$ right away because $p_i$ is a subset of $val$. That way, it doesn't always do $log(n)$ queries; it does however many ones $val$ has queries. This actually improves the solution to $2n+2log(n)+c$ on average! The intuition is: you start with a random number that has $\frac{log(n)}{2}$ ones in it (on average,) and every time you face a subset of it, the number of ones is expected to be halved, so the number of queries is around $log(n)+\frac{log(n)}{2}+\frac{log(n)}{4}+\ldots \lt 2log(n)$. 64 65 Code link: <https://pastebin.com/HWA1HuyF> 66 67 ### Second solution 68 69 Thanks, [Utkarsh.25dec](/profile/Utkarsh.25dec "Master Utkarsh.25dec") for this solution. 70 71 I'll describe a way to start with $n$ candidates to be $0$ and end up with $\sqrt{n}$ candidates. Let's query random pairs until we find a pair whose bitwise-or has at most $\frac{log(n)}{2}$ bits. Take one of the 2 indices in the pair (let's call it $i$) and query it with every candidate you have, and take the bitwise-and of the results. That will give you $p_i$. Now, let's make the numbers whose query result with $i$ is $p_i$ (hence, a subset of $p_i$) our new candidates. Since $i$ has at most $\frac{log(n)}{2}$ ones, the number of its subsets is $\sqrt{n}$, and we have our desired result! 72 73 Now, to find the index of $0$, we'll just do this recursively until we have 2 candidates. We'll keep querying them with random indices until the results differ. The one giving a smaller result is our $0$. 74 75 Code link: <https://pastebin.com/zMV5CPAz> 76 77 **analysis** 78 79 This solution does $2n+\sqrt{n}+\sqrt{\sqrt{n}}+\ldots+c$ queries. 80 81 You may think this is much worse than the first solution, but apparently $\sqrt{n}$ is smaller than $log^2(n)$ for small $n$. And by small, I mean ~$10^5$. 82 83 ### Third solution 84 85 Thanks, [Mohammad_Yasser](/profile/Mohammad_Yasser "Master Mohammad_Yasser") for this solution. 86 87 Assume you have 2 candidates for $0$ called $a$ and $b$ such that one of them is the index of $0$ at the end of our algorithm, and we always know $(p_a|p_b)$. Let's iterate over our indices **in a random order** and try to update $a$ and $b$. Assume the current index is $c$. Let's query to get $(p_b|p_c)$. We have 3 cases: 88 89 * If $(p_a|p_b) \lt (p_b|p_c)$, $p_c$ can't be $0$, so we'll throw it away. 90 * If $(p_a|p_b) \gt (p_b|p_c)$, $p_a$ can't be $0$, so we'll throw it away and change $a$ to be $c$. 91 * Otherwise, $p_b$ can't be $0$ because that would imply $p_a=p_c$ (recall that $p$ is a permutation.) So we can throw it away and change $b$ to be $c$. But notice that we now don't know $(p_a|p_b)$, so we're gonna have to make one more query, since we need to keep track of it. 92 93 After we're done, we can narrow our 2 candidates down to 1 with the same way described in the previous solution. 94 95 Code link: <https://pastebin.com/Trifp8p3> 96 97 **analysis** 98 99 This solution does $2n+c$ queries, where $c$ mostly comes from however many times we fall into the third case. I have no idea how to prove it happens very few times (just intuitions,) but very surprisingly, it's 3.37 on average and only 11 when we maximize across 10000 cases.