2220.md (6165B)
1 Source: https://codeforces.com/blog/entry/152936 2 3 Thanks everybody for participating in the round! 4 5 ### [Div2A. Blocked](https://codeforces.com/contest/2220/problem/A) 6 7 Author: [misteg168](/profile/misteg168 "International Master misteg168") Preparation: [misteg168](/profile/misteg168 "International Master misteg168") 8 9 **Hint1** 10 11 What happens when there are two equal elements? 12 13 **Solution** 14 15 Tutorial is loading... 16 17 **Code** 18 19 ``` 20 #include <bits/stdc++.h> 21 using namespace std; 22 23 void solve() { 24 int n; 25 cin >> n; 26 vector<int> a(n); 27 for (auto &x : a) 28 cin >> x; 29 30 sort(a.rbegin(), a.rend()); 31 32 for (int i = 0; i < n-1; i++) 33 if (a[i] == a[i+1]) { 34 cout << "-1\n"; 35 return; 36 } 37 38 for (auto x : a) 39 cout << x << " "; 40 cout << "\n"; 41 } 42 43 int main() { 44 int T; 45 cin >> T; 46 while (T--) 47 solve(); 48 } 49 ``` 50 51 ### [Div2B. OIE excursion](https://codeforces.com/contest/2220/problem/B) 52 53 Author: [danx](/profile/danx "Master danx") Preparation: [danx](/profile/danx "Master danx") 54 55 **Solution** 56 57 Tutorial is loading... 58 59 **Code** 60 61 ``` 62 #pragma GCC optimize ("O3") 63 #include <bits/stdc++.h> 64 using namespace std; 65 66 int t, n, m; 67 68 int main() { 69 70 int t; cin >> t; 71 while(t--) { 72 int n, m; cin >> n >> m; 73 74 int c, cnt, mx = 1; 75 76 for(int i = 0; i < n; i++) { 77 int a; cin >> a; 78 79 if (!i) { 80 c = a; 81 cnt = 1; 82 } 83 else if (a != c) { 84 c = a; 85 mx = max(mx, cnt); 86 cnt = 1; 87 } 88 else { 89 cnt++; 90 } 91 } 92 93 mx = max(mx, cnt); 94 95 if(mx < m) cout << "YES" << "\n"; 96 else cout << "NO" << "\n"; 97 } 98 99 return 0; 100 } 101 ``` 102 103 ### [Div1A Grid-L](https://codeforces.com/contest/2219/problem/A) 104 105 Author: [rlidon2006](/profile/rlidon2006 "Master rlidon2006") Preparation: [misteg168](/profile/misteg168 "Master misteg168") 106 107 **Hint1** 108 109 We want an easy to check condition on $m$, $n$, $p$, $q$ that is equivalent to being able to fill the grid. 110 111 **Hint2 (strong spoiler)** 112 113 You can fill the $m\times n$ grid if and only if $p+2q = m(n+1)+n(m+1)$ and $p\ge \vert m-n\vert$. (See tutorial for proof) 114 115 **Hint3** 116 117 $p+2q = m(n+1) + n(m+1)$ is quadratic on $m$ and $n$. If you assume $m\ge n$, can you say anything on the size of $n$? 118 119 **Solution** 120 121 Tutorial is loading... 122 123 **Code** 124 125 [370969986](/contest/2219/submission/370969986 "Submission 370969986 by NanYan") 126 127 ### [Div1B Unique values](https://codeforces.com/contest/2219/problem/B1) 128 129 Author: [misteg168](/profile/misteg168 "International Master misteg168") Preparation: [misteg168](/profile/misteg168 "International Master misteg168") 130 131 **Solution B1** 132 133 Tutorial is loading... 134 135 **Code** 136 137 [371019251](/contest/2219/submission/371019251 "Submission 371019251 by tourist") 138 139 **Solution B2** 140 141 Tutorial is loading... 142 143 **Code** 144 145 [371035963](/contest/2219/submission/371035963 "Submission 371035963 by Baskot") 146 147 ### [Div1C](https://codeforces.com/contest/2219/problem/C) 148 149 Author: [misteg168](/profile/misteg168 "Master misteg168") Preparation: [misteg168](/profile/misteg168 "Master misteg168") 150 151 **Hint1** 152 153 Think of some kind of subtree DP. 154 155 **Solution** 156 157 Tutorial is loading... 158 159 **Code** 160 161 [370987541](/contest/2219/submission/370987541 "Submission 370987541 by NanYan") 162 163 ### [Div1D. MEX Replacement on Tree](https://codeforces.com/contest/2219/problem/D) 164 165 Author: [Misuki](/profile/Misuki "Grandmaster Misuki") Preparation: [Misuki](/profile/Misuki "Grandmaster Misuki") 166 167 **Hint1** 168 169 Having a good visual image of the problem in mind may help. That is, for each vertex, thinking there is an array of infinite slot, and some of them are occupied by token, and the operation correspond to moving certain token to the first hole. 170 171 **Hint2** 172 173 Draw some small cases! What would these infinite arrays change when doing operation on root? 174 175 **Hint3** 176 177 Doing operation on vertex with $p_v \lt f(v)$ is useless. Consider the rest situations. 178 179 **Hint4** 180 181 when doing operation on $v$, how would $f(x)$ change if $x$ is in subtree of $v$? 182 183 **Hint5** 184 185 There are two cases, $f(x) = f(v)$ and $f(x) \gt f(v)$. 186 187 **Hint6** 188 189 Solve <https://judge.yosupo.jp/problem/vertex_add_subtree_sum> 190 191 **Solution** 192 193 Tutorial is loading... 194 195 **Code** 196 197 [371007707](/contest/2219/submission/371007707 "Submission 371007707 by NanYan") 198 199 ### [DivE. Weird Chessboard](https://codeforces.com/contest/2219/problem/E) 200 201 Author: [rlidon2006](/profile/rlidon2006 "Master rlidon2006") Preparation: [misteg168](/profile/misteg168 "Master misteg168"), [rlidon2006](/profile/rlidon2006 "Master rlidon2006") 202 203 **Hint1** 204 205 Can you rewrite the condition on the board to something simpler? 206 207 **Hint2** 208 209 Label the board $v_{i,j}$ where $v_{0,0}$ is the top left cell. We work mod $2$. A board $v_{i,j}$ is valid if and only if $v_{i,j}+v_{i+1,j}+v_{i,j+1}=0$ and all entries above the secondary diagonal are zero. 210 211 **Hint3** 212 213 Warm up: try to get a construction of density $1/4$. 214 215 **Hint4** 216 217 The next few hints get quite spoilery. If you don't want to see them yet but are stuck, consider coding some kind of heuristic (say, simulated annealing or A*) and running it on small values of $n$ to see what the result looks like. 218 219 **Hint5** 220 221 Prove that the density is at most $1/3$. 222 223 **Hint6** 224 225 Consider the grid $w_{i,j}$ with $w_{i,j}=1$ when $i+j\ge n-1$ and $i\not\equiv j\pmod 3$, and $w_{i,j}=0$ otherwise. 226 227 **Hint7** 228 229 This grid is almost valid: $v_{i,j}+v_{i+1,j}+v_{i,j+1}=1$ only for very few concrete positions $(i,j)$. Try to fix the issues at those positions in a way that does not disturb much of the grid. 230 231 **Hint8** 232 233 For each position $(i_0, j_0)$ on the diagonal where $w_{i_0,j_0} = 0$, we want to add a pattern to the grid that fixes the issues there. 234 235 **Hint9** 236 237 For each such $(i_0,j_0)$, flip $w_{i_0,j_0}$ and add a Pascal triangle mod $2$ to the grid. 238 239 **Hint10** 240 241 To implement this in $O(n^2)$, instead of adding each pascal independently, try to compute the sum of all of the pascals directly. 242 243 **Solution** 244 245 Tutorial is loading... 246 247 **Code** 248 249 [371015865](/contest/2219/submission/371015865 "Submission 371015865 by tourist")