1534.md (4633B)
1 Source: https://codeforces.com/blog/entry/91760 2 3 [1534A - Colour the Flag](/contest/1534/problem/A) 4 5 Author: [crackersamdjam](/profile/crackersamdjam "Grandmaster crackersamdjam") 6 7 **Hint 1** 8 9 Let's say you know the colour of the first square, what colours can you figure out next? 10 11 **Hint 2** 12 13 Colour it like a chessboard, but there's more than one possible chessboard! 14 15 **Hint 3** 16 17 Brute force the color of the first square! 18 19 **Tutorial** 20 21 Tutorial is loading... 22 23 **Solution** 24 25 [119400830](/contest/1534/submission/119400830 "Submission 119400830 by Dormi") 26 27 [1534B - Histogram Ugliness](/contest/1534/problem/B) 28 29 Author: [Dormi](/profile/Dormi "Grandmaster Dormi") 30 31 **Hint 1** 32 33 Consider the contribution of each pillar to the answer. 34 35 **Hint 2** 36 37 How does doing the operation on a pillar change the contribution to the answer? 38 39 **Hint 3** 40 41 You only want to do an operation on a pillar if the top cell contributes 2 to the answer. 42 43 **Tutorial** 44 45 Tutorial is loading... 46 47 **Solution** 48 49 [119400874](/contest/1534/submission/119400874 "Submission 119400874 by Dormi") 50 51 [1534C - Little Alawn's Puzzle](/contest/1534/problem/C) 52 53 Author: [Ninjaclasher](/profile/Ninjaclasher "Candidate Master Ninjaclasher") 54 55 **Hint 1** 56 57 Let's say you know whether you flipped the first cell or not, which new columns must be flipped? 58 59 **Hint 2** 60 61 Create a graph of $n$ nodes, draw an edge between two values if they both exist in the same column, what structure does this graph have? 62 63 **Hint 3** 64 65 It is a bunch of disjoint cycles (since each node has an in-degree of $2$). 66 67 **Hint 4** 68 69 Each cycle is independent, and there are $2$ ways to flip each cycle. 70 71 **Tutorial** 72 73 Tutorial is loading... 74 75 **Solution** 76 77 [119400885](/contest/1534/submission/119400885 "Submission 119400885 by Dormi") 78 79 [1534D - Lost Tree](/contest/1534/problem/D) 80 81 Author: [Plasmatic](/profile/Plasmatic "Grandmaster Plasmatic") 82 83 **Hint 1** 84 85 All trees are bipartite. 86 87 **Hint 2** 88 89 Find a $2$-coloring of a tree in one query. 90 91 **Hint 3** 92 93 You can find all nodes adjacent to one node in one query. 94 95 **Hint 4** 96 97 The min(number of black, number of white) nodes is $\leq \left \lfloor{\frac{n}{2}}\right \rfloor$. 98 99 **Tutorial** 100 101 Tutorial is loading... 102 103 **Solution** 104 105 [119400891](/contest/1534/submission/119400891 "Submission 119400891 by Dormi") 106 107 [1534E - Lost Array](/contest/1534/problem/E) 108 109 Author: [Plasmatic](/profile/Plasmatic "Grandmaster Plasmatic") 110 111 **Hint 1** 112 113 Try to solve this problem for $n \leq 15$. 114 115 **Hint 2** 116 117 Try BFSing on the bitmasks. 118 119 **Hint 3** 120 121 Do we really care about what elements are in the bitmask? 122 123 **Hint 4** 124 125 Only the number of nodes in each mask matters. 126 127 **Tutorial** 128 129 Tutorial is loading... 130 131 **Solution** 132 133 [119400897](/contest/1534/submission/119400897 "Submission 119400897 by Dormi") 134 135 [1534F1 - Falling Sand (Easy Version)](/contest/1534/problem/F1) 136 137 Author: [Dormi](/profile/Dormi "Grandmaster Dormi") 138 139 **Hint 1** 140 141 Make a directed graph on the sand. 142 143 **Hint 2** 144 145 The graph should satisfy the following property: if a node $a$ can reach another node $b$ by a sequence of edges, disturbing $a$ will disturb $b$. 146 147 **Hint 3** 148 149 Compress scc's in the graph. 150 151 **Hint 4** 152 153 You must disturb all nodes with in-degree $0$ in the new graph. 154 155 **Tutorial** 156 157 Tutorial is loading... 158 159 **Solution** 160 161 [119400903](/contest/1534/submission/119400903 "Submission 119400903 by Dormi") 162 163 [1534F2 - Falling Sand (Hard Version)](/contest/1534/problem/F2) 164 165 Author: [Dormi](/profile/Dormi "Grandmaster Dormi") 166 167 **Hint 1** 168 169 Continued from $F1$, read that first. 170 171 **Hint 2** 172 173 The $a_i^\texttt{th}$ nodes from the bottom of each column must eventually be disturbed (call them special). 174 175 **Hint 3** 176 177 If a special node can reach another special node, you can delete that node. 178 179 **Hint 4** 180 181 Each node will remove some contiguous subsegment of the remaining special nodes' columns. 182 183 **Hint 5** 184 185 Find a greedy strategy to cover all of the columns. 186 187 **Tutorial** 188 189 Tutorial is loading... 190 191 **Solution** 192 193 [119400908](/contest/1534/submission/119400908 "Submission 119400908 by Dormi") 194 195 [1534G - A New Beginning](/contest/1534/problem/G) 196 197 Author: [Aaeria](/profile/Aaeria "Master Aaeria") 198 199 **Tutorial** 200 201 Tutorial is loading... 202 203 **Solution** 204 205 [119400915](/contest/1534/submission/119400915 "Submission 119400915 by Dormi") 206 207 [Tests generator](https://github.com/zzaria/programming-contest-resources/blob/main/my%20problems/cf1524/g.zip) 208 209 [1534H - Lost Nodes](/contest/1534/problem/H) 210 211 Author: [Ninjaclasher](/profile/Ninjaclasher "Candidate Master Ninjaclasher") 212 213 **Tutorial** 214 215 Tutorial is loading... 216 217 **Solution** 218 219 [119400928](/contest/1534/submission/119400928 "Submission 119400928 by Dormi")