1983.md (8583B)
1 Source: https://codeforces.com/blog/entry/131268 2 3 Thank you for participating in our contest! We hope you enjoyed it. 4 5 **On a personal note (contains spoilers)** 6 7 This is the first time some of us are problemsetting. I apologise in case some of you did not have a good experience with the contest. I realise B was probably too hard for its position, we had a 2 hour 15 minutes contest and I expected the extra time to compensate for that. I believe some people did not like B being easily guessable. We were actually in a position where we could punish guessers who submit without proof. A lot of testers had submitted the sum over the entire grid modulo 3 to be equal as an initial guess (the samples were weak back then). I added a lot of samples to B (and, for that matter, to C, too) to make the problem easier instead of going the other way and punishing guessers. I really do not know if going the other way would have been appreciated, either. 8 9 I really like observation-based problems, like the format we have on CF nowadays. I did not realise all these constructives might cause a bad experience. I've never prepared for math olympiads or related stuff, and it has been CF that introduced me to all these sorts of problems, so I have no idea what would count as math-heavy and what would not. 10 11 For D I'm very surprised people managed to guess permutation parity without proving. We wanted to introduce new and uncommon problems, like the usage of permutation parity here would have been for a div2D. D and G are my personal favourites from this round. For G, too, it is possible to solve it without any heavy data structures, just plain observations. 12 13 It had been a complaint in last year's ByteRace round that the problems in the Div1 range were not hard or interesting enough. This time, we did try to ensure that, hopefully. I really like problem G, as said before. Actually, we were planning to have a 3-hour long 8 problem round, but we had to get down to this. 14 15 We ended up overlooking some mistakes in the statement of E. I'm sorry about that, too. Many of us preparing the contest have been busy interning, and sometimes it gets hard to manage time. 16 17 I believe the observations required for B and D make them really good and unique problems. We just did not put them in ways that would, like, prevent guessing. Are we supposed to? E was one math-heavy problem, is that a lot? I'm genuinely curious, can any experienced problemsetter (and not random greys echoing each other) explain what did not go well with this contest, if anything? 18 19 [1983A - Array Divisibility](/contest/1983/problem/A "Codeforces Round 956 (Div. 2) and ByteRace 2024") 20 21 Idea: [BlazingDragon](/profile/BlazingDragon "Expert BlazingDragon") 22 Preparation: [Pew_Pew.](/profile/Pew_Pew. "Expert Pew_Pew.") 23 Editorial: [Swap-nil](/profile/Swap-nil "Expert Swap-nil") 24 25 **Hints** 26 27 **Hint 1** 28 29 Think simple. 30 31 **Hint 2** 32 33 If $a$ and $b$ both are divisible by $c$ then, $a + b$ will also be divisible by $c$. 34 35 **Solution** 36 37 Tutorial is loading... 38 39 **Implementation (C++)** 40 41 [269328935](/contest/1983/submission/269328935 "Submission 269328935 by Swap-nil") 42 43 **Implementation (Python)** 44 45 [269329008](/contest/1983/submission/269329008 "Submission 269329008 by Swap-nil") 46 47 **Feedback** 48 49 * Good problem 50 * Average problem 51 * Bad problem 52 * Did not solve 53 54 [1983B - Corner Twist](/contest/1983/problem/B "Codeforces Round 956 (Div. 2) and ByteRace 2024") 55 56 Idea: [Swap-nil](/profile/Swap-nil "Expert Swap-nil") 57 Preparation: [Swap-nil](/profile/Swap-nil "Expert Swap-nil") 58 Editorial: [Swap-nil](/profile/Swap-nil "Expert Swap-nil") 59 60 **Hint** 61 62 **Hint 1** 63 64 $1 + 2 \equiv 0 \pmod{3}$. 65 66 **Hint 2** 67 68 Can you notice something that does not change, an invariant? 69 70 **Solution** 71 72 Tutorial is loading... 73 74 **Implementation (C++)** 75 76 [269329137](/contest/1983/submission/269329137 "Submission 269329137 by Swap-nil") 77 78 **Implementation (Python)** 79 80 [269329083](/contest/1983/submission/269329083 "Submission 269329083 by Swap-nil") 81 82 **Feedback** 83 84 * Good problem 85 * Average problem 86 * Bad problem 87 * Did not solve 88 89 [1983C - Have Your Cake and Eat It Too](/contest/1983/problem/C "Codeforces Round 956 (Div. 2) and ByteRace 2024") 90 91 Idea: [DC17](/profile/DC17 "Candidate Master DC17") 92 Preparation: [Swap-nil](/profile/Swap-nil "Expert Swap-nil") 93 Editorial: [BlazingDragon](/profile/BlazingDragon "Expert BlazingDragon") 94 95 **Solution** 96 97 Tutorial is loading... 98 99 **Implementation (C++)** 100 101 [269329204](/contest/1983/submission/269329204 "Submission 269329204 by Swap-nil") 102 103 **Implementation (Python)** 104 105 [269329258](/contest/1983/submission/269329258 "Submission 269329258 by Swap-nil") 106 107 **Feedback** 108 109 * Good problem 110 * Average problem 111 * Bad problem 112 * Did not solve 113 114 [1983D - Swap Dilemma](/contest/1983/problem/D "Codeforces Round 956 (Div. 2) and ByteRace 2024") 115 116 Idea: [MrSavageVS](/profile/MrSavageVS "Expert MrSavageVS") 117 Preparation: [MrSavageVS](/profile/MrSavageVS "Expert MrSavageVS") 118 Editorial: [MrSavageVS](/profile/MrSavageVS "Expert MrSavageVS") 119 120 **Hint** 121 122 **Hint 1** 123 124 Can we convert this complicated operation to something simpler? 125 126 **Hint 2** 127 128 We can convert the operation to basically swapping adjacent elements and it still works. Try to prove why? 129 130 **Hint 3** 131 132 Swapping adjacent elements in a distinct array is basically trying to equate two permutations using adjacent swaps. When is it possible? 133 134 **Hint 4** 135 136 Inversions in a permutation 137 138 **Solution** 139 140 Tutorial is loading... 141 142 **Implementation (C++)** 143 144 [269303026](/contest/1983/submission/269303026 "Submission 269303026 by MrSavageVS") 145 146 **Feedback** 147 148 * Good problem 149 * Average problem 150 * Bad problem 151 * Did not solve 152 153 [1983E - I Love Balls](/contest/1983/problem/E "Codeforces Round 956 (Div. 2) and ByteRace 2024") 154 155 Idea: [DC17](/profile/DC17 "Candidate Master DC17") 156 Preparation: [BlazingDragon](/profile/BlazingDragon "Expert BlazingDragon") 157 Editorial: [BlazingDragon](/profile/BlazingDragon "Expert BlazingDragon") 158 159 **Solution** 160 161 Tutorial is loading... 162 163 **Implementation (C++)** 164 165 [269329340](/contest/1983/submission/269329340 "Submission 269329340 by Swap-nil") 166 167 **Feedback** 168 169 * Good problem 170 * Average problem 171 * Bad problem 172 * Did not solve 173 174 [1983F - array-value](/contest/1983/problem/F "Codeforces Round 956 (Div. 2) and ByteRace 2024") 175 176 Idea: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101") 177 Preparation: [MrSavageVS](/profile/MrSavageVS "Expert MrSavageVS") 178 Editorial: [MrSavageVS](/profile/MrSavageVS "Expert MrSavageVS") 179 180 **Hint** 181 182 **Hint 1** 183 184 Can we fix an upper bound to count the number of subarrays having xor-pair less than that? 185 186 **Hint 2** 187 188 We can use binary search to fix an upper bound and calculate all subarrays with xor-pair less than the given value. 189 190 **Hint 3** 191 192 In order to count the number of subarrays we can use a popular data-structure used for a lot of xor-operations. 193 194 **Hint 4** 195 196 We can binary search on the upper bound and use tries to count the number of subarrays with xor-pair less than given value. This way we can find the kth-smallest value. 197 198 **Solution** 199 200 Tutorial is loading... 201 202 **Implementation (C++)** 203 204 [269305957](/contest/1983/submission/269305957 "Submission 269305957 by MrSavageVS") 205 206 **Feedback** 207 208 * Good problem 209 * Average problem 210 * Bad problem 211 * Did not solve 212 213 [1983G - Your Loss](/contest/1983/problem/G "Codeforces Round 956 (Div. 2) and ByteRace 2024") 214 215 Idea: [AwakeAnay](/profile/AwakeAnay "Grandmaster AwakeAnay"),[TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101") 216 Preparation: [ShivanshJ](/profile/ShivanshJ "Master ShivanshJ"), [Swap-nil](/profile/Swap-nil "Expert Swap-nil"), [Pew_Pew.](/profile/Pew_Pew. "Expert Pew_Pew.") 217 Editorial: [Swap-nil](/profile/Swap-nil "Expert Swap-nil") 218 219 **Hints** 220 221 **Hint 1** 222 223 Try looking at the problem bit by bit. 224 225 **Hint 2** 226 227 What does the contribution of a particular bit over a path look like? 228 229 **Hint 3** 230 231 Can you think of some simpler queries you can easily solve the problem for? 232 233 **Hint 4** 234 235 Root the tree. 236 237 **Hint 5** 238 239 For a query from a node $u$ to its ancestor $v$, the countribution from the counting term $(0,1,2,3, \ldots)$ changes for the first time at an ancestor at a jump of a power of two. 240 241 **Hint 6** 242 243 Let $dp[u][k]$ be the contribution of bit $k$ to the query from $u$ to the root. 244 245 **Hint 7** 246 247 Keep track of a few additional nodes for each query. Read hint 5 again. 248 249 **Solution** 250 251 Tutorial is loading... 252 253 **Implementation (C++)** 254 255 [269315826](/contest/1983/submission/269315826 "Submission 269315826 by Swap-nil") 256 257 **Feedback** 258 259 * Good problem 260 * Average problem 261 * Bad problem 262 * Did not solve