1922.md (6715B)
1 Source: https://codeforces.com/blog/entry/124890 2 3 [1922A - Tricky Template](/contest/1922/problem/A "Educational Codeforces Round 161 (Rated for Div. 2)") 4 5 Idea: [Roms](/profile/Roms "Master Roms") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 n = int(input()) 16 a = input() 17 b = input() 18 c = input() 19 print("YES" if any([a[i] != c[i] and b[i] != c[i] for i in range(n)]) else "NO") 20 ``` 21 22 [1922B - Forming Triangles](/contest/1922/problem/B "Educational Codeforces Round 161 (Rated for Div. 2)") 23 24 Idea: [Roms](/profile/Roms "Master Roms") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution (Roms)** 31 32 ``` 33 #include <bits/stdc++.h> 34 35 using namespace std; 36 37 int t; 38 39 int main() { 40 cin >> t; 41 for (int tc = 0; tc < t; ++tc) { 42 int n; 43 cin >> n; 44 map<int, int> numOfLens; 45 for (int i = 0; i < n; ++i){ 46 int x; 47 cin >> x; 48 ++numOfLens[x]; 49 } 50 51 long long res = 0; 52 int sum = 0; 53 for (auto it : numOfLens) { 54 long long cnt = it.second; 55 if(cnt >= 3) 56 res += cnt * (cnt - 1) * (cnt - 2) / 6; 57 if(cnt >= 2) 58 res += cnt * (cnt - 1) / 2 * sum; 59 sum += cnt; 60 } 61 62 cout << res << endl; 63 } 64 return 0; 65 } 66 ``` 67 68 [1922C - Closest Cities](/contest/1922/problem/C "Educational Codeforces Round 161 (Rated for Div. 2)") 69 70 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 71 72 **Tutorial** 73 74 Tutorial is loading... 75 76 **Solution (Roms)** 77 78 ``` 79 #include <bits/stdc++.h> 80 81 using namespace std; 82 83 const int N = 200'000; 84 const int INF = 1'000'000'009; 85 int t; 86 87 char type(const vector <int>& a, int id) { 88 int distL = (id == 0? INF : a[id] - a[id - 1]); 89 int distR = (id + 1 == a.size()? INF : a[id + 1] - a[id]); 90 if(distL < distR) return 'L'; 91 if(distL > distR) return 'R'; 92 assert(false); 93 } 94 95 int main() { 96 ios::sync_with_stdio(false); 97 cin >> t; 98 for (int tc = 0; tc < t; ++tc) { 99 int n; 100 cin >> n; 101 vector <int> a(n); 102 for (int i = 0; i < n; ++i) 103 cin >> a[i]; 104 105 vector <int> l(n), r(n); 106 for (int i = 1; i < n; ++i) 107 r[i] = r[i - 1] + (type(a, i - 1) == 'R'? 1 : a[i] - a[i - 1]); 108 for (int i = n - 2; i >= 0; --i) 109 l[i] = l[i + 1] + (type(a, i + 1) == 'L'? 1 : a[i + 1] - a[i]); 110 111 int m; 112 cin >> m; 113 for (int i = 0; i < m; ++i) { 114 int x, y; 115 cin >> x >> y; 116 --x, --y; 117 if (x < y) 118 cout << r[y] - r[x] << endl; 119 else 120 cout << l[y] - l[x] << endl; 121 } 122 } 123 return 0; 124 } 125 ``` 126 127 [1922D - Berserk Monsters](/contest/1922/problem/D "Educational Codeforces Round 161 (Rated for Div. 2)") 128 129 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 130 131 **Tutorial** 132 133 Tutorial is loading... 134 135 **Solution (Neon)** 136 137 ``` 138 #include <bits/stdc++.h> 139 140 using namespace std; 141 142 int main() { 143 ios::sync_with_stdio(false); cin.tie(0); 144 int t; 145 cin >> t; 146 while (t--) { 147 int n; 148 cin >> n; 149 vector<int> a(n + 2), d(n + 2, INT_MAX); 150 for (int i = 1; i <= n; ++i) cin >> a[i]; 151 for (int i = 1; i <= n; ++i) cin >> d[i]; 152 set<int> lft, cur; 153 for (int i = 0; i < n + 2; ++i) { 154 lft.insert(i); 155 cur.insert(i); 156 } 157 for (int z = 0; z < n; ++z) { 158 set<int> del, ncur; 159 for (int i : cur) { 160 auto it = lft.find(i); 161 if (it == lft.end()) continue; 162 int prv = *prev(it); 163 int nxt = *next(it); 164 if (a[prv] + a[nxt] > d[i]) { 165 del.insert(i); 166 ncur.insert(prv); 167 ncur.insert(nxt); 168 } 169 } 170 cout << del.size() << ' '; 171 for (auto it : del) lft.erase(it); 172 cur = ncur; 173 } 174 cout << '\n'; 175 } 176 } 177 ``` 178 179 [1922E - Increasing Subsequences](/contest/1922/problem/E "Educational Codeforces Round 161 (Rated for Div. 2)") 180 181 Idea: [Roms](/profile/Roms "Master Roms") 182 183 **Tutorial** 184 185 Tutorial is loading... 186 187 **Solution (Neon)** 188 189 ``` 190 #include <bits/stdc++.h> 191 192 using namespace std; 193 194 vector<int> f(long long x) { 195 vector<int> res; 196 if (x == 2) { 197 res.push_back(0); 198 } else if (x & 1) { 199 res = f(x - 1); 200 res.push_back(*min_element(res.begin(), res.end()) - 1); 201 } else { 202 res = f(x / 2); 203 res.push_back(*max_element(res.begin(), res.end()) + 1); 204 } 205 return res; 206 } 207 208 int main() { 209 int t; 210 cin >> t; 211 while (t--) { 212 long long x; 213 cin >> x; 214 auto ans = f(x); 215 cout << ans.size() << '\n'; 216 for (int i : ans) cout << i << ' '; 217 cout << '\n'; 218 } 219 } 220 ``` 221 222 [1922F - Replace on Segment](/contest/1922/problem/F "Educational Codeforces Round 161 (Rated for Div. 2)") 223 224 Idea: [Roms](/profile/Roms "Master Roms") 225 226 **Tutorial** 227 228 Tutorial is loading... 229 230 **Solution (Neon)** 231 232 ``` 233 #include <bits/stdc++.h> 234 235 using namespace std; 236 237 const int N = 111; 238 239 int n, k; 240 int a[N]; 241 int nxtx[N][N], prvx[N][N]; 242 int nxtnx[N][N], prvnx[N][N]; 243 int dp1[N][N][N], dp2[N][N][N]; 244 245 int calc2(int, int, int); 246 247 int calc1(int l, int r, int x) { 248 l = nxtnx[l][x], r = prvnx[r][x]; 249 if (l > r) return 0; 250 if (dp1[l][r][x] != -1) return dp1[l][r][x]; 251 dp1[l][r][x] = calc2(l, r, x) + 1; 252 for (int i = l; i < r; ++i) dp1[l][r][x] = min(dp1[l][r][x], calc1(l, i, x) + calc1(i + 1, r, x)); 253 return dp1[l][r][x]; 254 } 255 256 int calc2(int l, int r, int x) { 257 l = nxtx[l][x], r = prvx[r][x]; 258 if (l > r) return 0; 259 if (dp2[l][r][x] != -1) return dp2[l][r][x]; 260 dp2[l][r][x] = n; 261 for (int i = l; i < r; ++i) dp2[l][r][x] = min(dp2[l][r][x], calc2(l, i, x) + calc2(i + 1, r, x)); 262 for (int y = 0; y < k; ++y) if (x != y) dp2[l][r][x] = min(dp2[l][r][x], calc1(l, r, y)); 263 return dp2[l][r][x]; 264 } 265 266 void solve() { 267 cin >> n >> k; 268 for (int i = 0; i < n; ++i) cin >> a[i], --a[i]; 269 for (int x = 0; x < k; ++x) prvx[0][x] = prvnx[0][x] = -1; 270 for (int i = 0; i < n; ++i) { 271 prvx[i][a[i]] = i; 272 for (int x = 0; x < k; ++x) prvx[i + 1][x] = prvx[i][x]; 273 for (int x = 0; x < k; ++x) if (x != a[i]) prvnx[i][x] = i; 274 for (int x = 0; x < k; ++x) prvnx[i + 1][x] = prvnx[i][x]; 275 } 276 for (int x = 0; x < k; ++x) nxtx[n][x] = nxtnx[n][x] = n; 277 for (int i = n - 1; i >= 0; --i) { 278 for (int x = 0; x < k; ++x) nxtx[i][x] = nxtx[i + 1][x]; 279 nxtx[i][a[i]] = i; 280 for (int x = 0; x < k; ++x) nxtnx[i][x] = nxtnx[i + 1][x]; 281 for (int x = 0; x < k; ++x) if (x != a[i]) nxtnx[i][x] = i; 282 } 283 memset(dp1, -1, sizeof(dp1)); 284 memset(dp2, -1, sizeof(dp2)); 285 int ans = n; 286 for (int x = 0; x < k; ++x) ans = min(ans, calc1(0, n - 1, x)); 287 cout << ans << '\n'; 288 } 289 290 int main() { 291 int t; 292 cin >> t; 293 while (t--) solve(); 294 } 295 ```