2118.md (8789B)
1 Source: https://codeforces.com/blog/entry/143702 2 3 [2118A - Equal Subsequences](/contest/2118/problem/A "Codeforces Round 1030 (Div. 2)") 4 5 **Hint 1** 6 7 It is somehow difficult to count the number of such subsequences in an arbitrary string. Can you think of strings where it is trivial? 8 9 **Hint 2** 10 11 The number of such subsequences can be $0$. 12 13 **Tutorial** 14 15 **Key observation:** A bitstring where all $\mathtt{1}$ bits come before all $\mathtt{0}$ bits is perfect as it has no $\mathtt{101}$ or $\mathtt{010}$ subsequences. 16 17 You can fix the number of $\mathtt{1}$ bits to be $k$ and then put $n-k$ $\mathtt{0}$ bits after them. This achieves a perfect bitstring with the number of $\mathtt{1}$ bits being $k$. 18 19 **Implementation** 20 21 [324251060](/contest/2118/submission/324251060 "Submission 324251060 by szilb") 22 23 [2118B - Make It Permutation](/contest/2118/problem/B "Codeforces Round 1030 (Div. 2)") 24 25 **Hint 1** 26 27 The answer matrix will have permutations in every row and column. Can you think of such a matrix? 28 29 **Hint 2** 30 31 Let our final matrix have all cyclic shifts of the identity permutation in each row. Can you perform a cyclic shift using $3$ operations? 32 33 **Hint 3** 34 35 One of the operations performed on each row becomes redundant. 36 37 **Tutorial** 38 39 **Key observation:** You can cyclic shift an array using $3$ operations. 40 41 The operations to achieve this are "$1$ $n$", "$1$ $i$", "$i+1$ $n$". Perform these with a different $i$ for each row, you will obtain all cyclic shifts of the identity permutation. To optimize it to $2n$ operations observe that performing "$1$ $n$" on each row does nothing. 42 43 **Implementation** 44 45 [324251108](/contest/2118/submission/324251108 "Submission 324251108 by szilb") 46 47 [2118C - Make It Beautiful](/contest/2118/problem/C "Codeforces Round 1030 (Div. 2)") 48 49 **Hint 0** 50 51 Think in binary. 52 53 **Hint 1** 54 55 Let $x$ be an integer. What is the smallest number $y \gt x$ that is more beautiful than $x$? 56 57 **Answer to hint 1** 58 59 $y$ always equals $x$ with the smallest valued $0$ bit set to $1$. 60 61 **Tutorial** 62 63 **Key observation:** To increase the beauty of a number, it is always optimal to set the least valued $0$ bit to $1$. 64 65 Let our number be $x$ and call the least valued $0$ bit special. Let $y$ be $x$ with the special bit set to $1$. To increase the beauty, we must increase $x$ by at least $1$. This will set the special bit to $1$, and all bits with a smaller value to $0$. Until we reach $y$, there will always be at least one $0$ bit with a smaller value than the special bit while the bits with a higher value stay the same. This means that no number is more beautiful between $x$ and $y$, showing that the observation is correct. 66 67 From this, we can construct a solution. Let us count the number of $0$ bits at each position. Iterate from the least valued bit to the highest. Greedily set one such bit to $1$ until we run out of $0$ bits or the remaining $k$ is less than the value of the bit. 68 69 This solution has a time complexity $O(N\log{10^{18}})$. 70 71 **Implementation** 72 73 [324251138](/contest/2118/submission/324251138 "Submission 324251138 by szilb") 74 75 [2118D2 - Red Light, Green Light (Hard version)](/contest/2118/problem/D2 "Codeforces Round 1030 (Div. 2)") 76 77 **General outline (hint for both subtasks, read first)** 78 79 Divide the problem into some subproblems: 80 81 * Find the next traffic light efficiently. 82 * Detect cycles efficiently. 83 84 For D1 it is enough to do the first subproblem in $O(N)$, the second subproblem with $O(N)$ calls of the first subproblem. For D2 we need to do better. 85 86 **Subproblems for D1** 87 88 Try to simulate the problem by hand. 89 90 Iterate over all traffic lights and check if we would collide with it if we don't turn. Then we can select the next traffic light in the correct direction. This is $O(N)$. 91 92 If we collide with the same traffic light from the same direction twice than the answer is no. For detecting cycles we can store visited traffic lights that we collided together with direction. Notice that we can only collide with a specific traffic light in a unique time modulo $k$. 93 94 This solution has a time complexity $O(Q*N^2)$. 95 96 **Subproblems for D2** 97 98 First, let's quickly find the next traffic light in the positive direction. Imagine movement by moving along diagonals, refer to the images in the statement for a visual representation. Group the traffic lights by $(d_i-p_i)\bmod k$, when at position $x$ at time $t$ you will collide with the group of $(t-x)\bmod k$. We can binary search the next position on this. To do the same for the anti-diagonals you can group by $(d_i+p_i)\bmod k$ and search by $(t+x)\bmod k$. 99 100 We can still simulate each query, but after finding out the answer you can store for each state the result. In later queries, you can refer to the already checked states. In total, you will only check each state at most once. 101 102 Alternatively, you can notice that after colliding with a traffic light in a specific direction, the next traffic light will always be the same. From this you can build a graph and detect cycles before reading queries. 103 104 Both solutions have a time complexity of $O(N\log{N})$. 105 106 **Implementation** 107 108 [324251333](/contest/2118/submission/324251333 "Submission 324251333 by szilb") 109 110 [2118E - Grid Coloring](/contest/2118/problem/E "Codeforces Round 1030 (Div. 2)") 111 112 **Hint 1** 113 114 Why is it important that both $N$ and $M$ are odd? 115 116 **Hint 2** 117 118 Try generalizing the trivial case when $N=1$. 119 120 **Hint 3** 121 122 Try extending the solution from a smaller case... in a literal sense. 123 124 **Tutorial** 125 126 **Key observation:** Having $N \ge M$ and N, M both odd, an $(N - 2) \times M$ grid can easily be extended into a $N \times M$ grid 127 128 To achieve this first color a cell in the middle of both of the $M$ long sides. By this we ensure that the rectangle will be so wide that its side will be at maximum chessboard distance from each other. This means that any cells colored next to one of its sides can only increase the penalty of cells of the opposite side. By coloring cells alternating up and down on each side (similarly to the solution to the case $N=1$) we can ensure that every cell gets at most $2$ penalty. 129 130 This only leaves the corners as corner cases (as they can be increased from two sides), but they can also be solved by choosing the order of vertical and horizontal extensions correctly. 131 132 **Implementation** 133 134 [324251385](/contest/2118/submission/324251385 "Submission 324251385 by szilb") 135 136 **Extra** 137 138 Some interesting observations: 139 140 * It can be observed that order that ordering the points from the center (and always deciding the ties in the right manner) can also yield a solution. 141 * There actually exists a solution which works for even sized boards 142 * As an extra challenge it can be interesting to find a solution where no cell has more than 2 penalties. 143 144 [2118F - Shifts and Swaps](/contest/2118/problem/F "Codeforces Round 1030 (Div. 2)") 145 146 **Hint 1** 147 148 The order of two elements only matters if the absolute value of their difference is at most 1. Try to store the positions of elements with value $v$ relative to elements with value $v+1$. (The next hint will be about what to do with these.) 149 150 **Hint 2** 151 152 We want to somehow hash the relative positions. (The next hint will be about a thing you might not have known you can hash.) 153 154 **Hint 3** 155 156 It is possible to hash rooted trees, see [Vladosiya's blog post](https://codeforces.com/blog/entry/113465). Note: the structure you hopefully came up with using hint 2 will certainly not be a single rooted tree, use this algorithm more as a guide. (The next hint will be about how you can check if two strings are rotations of each other.) 157 158 **Hint 4** 159 160 You can check if two strings are rotations of each other either by [using KMP](https://www.geeksforgeeks.org/a-program-to-check-if-strings-are-rotations-of-each-other/) or [hashing](https://cp-algorithms.com/string/string-hashing.html). 161 162 **Tutorial** 163 164 We'll consider the arrays cyclic: $a_1$ and $a_n$ are also adjacent. 165 166 For each array, let's build rooted trees where the children of each vertex are ordered. Each vertex corresponds to an value in an array. For each index $i$, let its children be the occurrences of the value $a_i - 1$ in order between the $i$-th element and the next occurrence of the value $a_i$. The roots of the trees will be nodes with value $m$ in an array. We hash each tree, then compare if the sequences of hashes are rotations of each other (for example [using KMP](https://www.geeksforgeeks.org/a-program-to-check-if-strings-are-rotations-of-each-other/)). 167 168 For hashing a tree, see [Vladosiya's blog post](https://codeforces.com/blog/entry/113465). 169 170 This solution has a time complexity $O(N\log{N})$ if you use a map for deterministic hashing. 171 172 **Implementation** 173 174 [324251436](/contest/2118/submission/324251436 "Submission 324251436 by szilb")