1969.md (9140B)
1 Source: https://codeforces.com/blog/entry/129022 2 3 [1969A - Two Friends](/contest/1969/problem/A "Educational Codeforces Round 165 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 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 p = [int(x) - 1 for x in input().split()] 17 ans = 3 18 for i in range(n): 19 if p[p[i]] == i: 20 ans = 2 21 print(ans) 22 ``` 23 24 [1969B - Shifts and Sorting](/contest/1969/problem/B "Educational Codeforces Round 165 (Rated for Div. 2)") 25 26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (adedalic)** 33 34 ``` 35 fun main() { 36 repeat(readln().toInt()) { 37 val s = readln().map { it.code - '0'.code } 38 val zeroes = s.count { it == 0 } 39 val cnt = intArrayOf(0, 0) 40 var ans = 0L 41 for (c in s) { 42 cnt[c]++ 43 if (c == 0) 44 ans += if (cnt[1] > 0) 1 else 0 45 else 46 ans += (zeroes - cnt[0]) 47 } 48 println(ans) 49 } 50 } 51 ``` 52 53 [1969C - Minimizing the Sum](/contest/1969/problem/C "Educational Codeforces Round 165 (Rated for Div. 2)") 54 55 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 56 57 **Tutorial** 58 59 Tutorial is loading... 60 61 **Solution (Neon)** 62 63 ``` 64 #include <bits/stdc++.h> 65 66 using namespace std; 67 68 using li = long long; 69 const li INF = 1e18; 70 71 int main() { 72 int t; 73 cin >> t; 74 while (t--) { 75 int n, k; 76 cin >> n >> k; 77 vector<li> a(n); 78 for (auto& x : a) cin >> x; 79 vector<vector<li>> dp(n + 1, vector<li>(k + 1, INF)); 80 dp[0][0] = 0; 81 for (int i = 0; i < n; ++i) { 82 for (int j = 0; j <= k; ++j) { 83 li mn = INF; 84 for (int d = 0; j + d <= k && i + d < n; ++d) { 85 mn = min(mn, a[i + d]); 86 dp[i + d + 1][j + d] = min(dp[i + d + 1][j + d], dp[i][j] + (d + 1) * mn); 87 } 88 } 89 } 90 cout << *min_element(dp[n].begin(), dp[n].end()) << '\n'; 91 } 92 } 93 ``` 94 95 [1969D - Shop Game](/contest/1969/problem/D "Educational Codeforces Round 165 (Rated for Div. 2)") 96 97 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 98 99 **Tutorial** 100 101 Tutorial is loading... 102 103 **Solution (Neon)** 104 105 ``` 106 #include <bits/stdc++.h> 107 108 using namespace std; 109 110 #define sz(a) int((a).size()) 111 using li = long long; 112 113 int main() { 114 int t; 115 cin >> t; 116 while (t--) { 117 int n, k; 118 cin >> n >> k; 119 vector<int> a(n), b(n); 120 for (auto& x : a) cin >> x; 121 for (auto& x : b) cin >> x; 122 vector<int> ord(n); 123 iota(ord.begin(), ord.end(), 0); 124 sort(ord.begin(), ord.end(), [&](int i, int j) { 125 return b[i] > b[j]; 126 }); 127 li f = 0, p = 0; 128 for (int i : ord) p += max(0, b[i] - a[i]); 129 li ans = 0; 130 multiset<int> s; 131 if (sz(s) == k) ans = max(ans, p - f); 132 for (int i : ord) { 133 p -= max(0, b[i] - a[i]); 134 s.insert(a[i]); 135 f += a[i]; 136 if (sz(s) > k) { 137 f -= *s.rbegin(); 138 s.erase(--s.end()); 139 } 140 if (sz(s) == k) ans = max(ans, p - f); 141 } 142 cout << ans << '\n'; 143 } 144 } 145 ``` 146 147 [1969E - Unique Array](/contest/1969/problem/E "Educational Codeforces Round 165 (Rated for Div. 2)") 148 149 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 150 151 **Tutorial** 152 153 Tutorial is loading... 154 155 **Solution (Neon)** 156 157 ``` 158 #include <bits/stdc++.h> 159 160 using namespace std; 161 162 #define sz(a) int((a).size()) 163 164 vector<int> t, p; 165 166 void push(int v) { 167 if (v * 2 + 2 >= sz(t)) return; 168 t[v * 2 + 1] += p[v]; p[v * 2 + 1] += p[v]; 169 t[v * 2 + 2] += p[v]; p[v * 2 + 2] += p[v]; 170 p[v] = 0; 171 } 172 173 void upd(int v, int l, int r, int L, int R, int x) { 174 if (L >= R) return; 175 if (l == L && r == R) { 176 t[v] += x; p[v] += x; 177 return; 178 } 179 int m = (l + r) / 2; 180 push(v); 181 upd(v * 2 + 1, l, m, l, min(m, R), x); 182 upd(v * 2 + 2, m, r, max(m, L), R, x); 183 t[v] = min(t[v * 2 + 1], t[v * 2 + 2]); 184 } 185 186 int get(int v, int l, int r, int L, int R) { 187 if (L >= R) return 1e9; 188 if (l == L && r == R) return t[v]; 189 int m = (l + r) / 2; 190 push(v); 191 return min( 192 get(v * 2 + 1, l, m, l, min(m, R)), 193 get(v * 2 + 2, m, r, max(m, L), R) 194 ); 195 } 196 197 void solve() { 198 int n; 199 cin >> n; 200 vector<int> a(n); 201 for (auto& x : a) cin >> x, --x; 202 t = p = vector<int>(4 * n); 203 vector<vector<int>> pos(n); 204 int ans = 0, st = 0; 205 for (int i = 0; i < n; ++i) { 206 int x = a[i]; 207 pos[x].push_back(i); 208 int k = sz(pos[x]); 209 if (k > 0) upd(0, 0, n, st, pos[x][k - 1] + 1, +1); 210 if (k > 1) upd(0, 0, n, st, pos[x][k - 2] + 1, -2); 211 if (k > 2) upd(0, 0, n, st, pos[x][k - 3] + 1, +1); 212 if (get(0, 0, n, st, i + 1) == 0) { 213 ans += 1; 214 st = i + 1; 215 } 216 } 217 cout << ans << '\n'; 218 } 219 220 int main() { 221 int t; 222 cin >> t; 223 while (t--) solve(); 224 } 225 ``` 226 227 [1969F - Card Pairing](/contest/1969/problem/F "Educational Codeforces Round 165 (Rated for Div. 2)") 228 229 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 230 231 **Tutorial** 232 233 Tutorial is loading... 234 235 **Solution (BledDest)** 236 237 ``` 238 #include<bits/stdc++.h> 239 240 using namespace std; 241 242 mt19937_64 rnd(12341234); 243 244 int n, k; 245 vector<int> deck; 246 vector<int> dp; 247 vector<vector<bool>> odd; 248 vector<bool> full_odd; 249 vector<long long> val; 250 vector<long long> hs; 251 252 bool bad(const vector<bool>& v) 253 { 254 for(int i = 0; i < k; i++) 255 if(!v[i]) 256 return false; 257 return true; 258 } 259 260 vector<bool> inv(const vector<bool>& v) 261 { 262 vector<bool> res(k); 263 for(int i = 0; i < k; i++) 264 res[i] = !v[i]; 265 return res; 266 } 267 268 vector<bool> get_suffix(int l) 269 { 270 vector<bool> v(k); 271 for(int i = l; i < n; i++) v[deck[i]] = !v[deck[i]]; 272 return v; 273 } 274 275 int get_next(long long cur, int x) 276 { 277 for(int i = x; i <= n; i += 2) 278 if(hs[i] == cur) 279 return i; 280 return -1; 281 } 282 283 int main() 284 { 285 cin >> n >> k; 286 deck.resize(n); 287 for(int i = 0; i < n; i++) cin >> deck[i]; 288 for(int i = 0; i < n; i++) --deck[i]; 289 val.resize(k); 290 for(int i = 0; i < k; i++) 291 while(val[i] == 0) 292 val[i] = rnd(); 293 294 int max_score = 0; 295 dp.resize(n + 1); 296 full_odd.resize(k); 297 odd.resize(n + 1, vector<bool>(k)); 298 hs.resize(n + 1); 299 long long cur_hash = 0; 300 for(int i = 0; i < n; i++) 301 { 302 cur_hash ^= val[deck[i]]; 303 if(full_odd[deck[i]]) max_score++; 304 full_odd[deck[i]] = !full_odd[deck[i]]; 305 odd[i + 1] = full_odd; 306 hs[i + 1] = cur_hash; 307 } 308 309 for(int i = k; i <= n; i++) 310 dp[i] = 1e9; 311 long long start = 0ll; 312 for(int i = 0; i < k; i++) start ^= val[i]; 313 int pos = get_next(start, k); 314 if(pos == -1) 315 { 316 cout << max_score << endl; 317 } 318 else 319 { 320 dp[pos] = 0; 321 int ans = 1e9; 322 for(int p = k; p <= n; p += 2) 323 { 324 if(dp[p] > 1e8) continue; 325 vector<bool> suff = get_suffix(p); 326 vector<int> o, e; 327 for(int j = 0; j < k; j++) 328 if(suff[j]) 329 e.push_back(j); 330 else 331 o.push_back(j); 332 int es = e.size(); 333 int os = o.size(); 334 bool flag = true; 335 for(int i = 0; i < os && flag; i++) 336 for(int j = 0; j < i && flag; j++) 337 { 338 int x = o[i]; 339 int y = o[j]; 340 int add = 0; 341 long long h = hs[p] ^ val[x] ^ val[y]; 342 int pos = get_next(h, p); 343 if(pos == -1) 344 { 345 flag = false; 346 ans = min(ans, dp[p] + add); 347 } 348 else 349 dp[pos] = min(dp[pos], dp[p] + add); 350 } 351 352 for(int i = 0; i < os && flag; i++) 353 for(int j = 0; j < es && flag; j++) 354 { 355 int x = o[i]; 356 int y = e[j]; 357 int add = 1; 358 long long h = hs[p] ^ val[x] ^ val[y]; 359 int pos = get_next(h, p); 360 if(pos == -1) 361 { 362 flag = false; 363 ans = min(ans, dp[p] + add); 364 } 365 else 366 dp[pos] = min(dp[pos], dp[p] + add); 367 } 368 369 for(int i = 0; i < es && flag; i++) 370 for(int j = 0; j < i && flag; j++) 371 { 372 int x = e[i]; 373 int y = e[j]; 374 int add = 2; 375 long long h = hs[p] ^ val[x] ^ val[y]; 376 int pos = get_next(h, p); 377 if(pos == -1) 378 { 379 flag = false; 380 ans = min(ans, dp[p] + add); 381 } 382 else 383 dp[pos] = min(dp[pos], dp[p] + add); 384 } 385 } 386 cout << max_score - ans << endl; 387 } 388 } 389 ```