1746.md (33541B)
1 Source: https://codeforces.com/blog/entry/108011 2 3 Hi Codeforces, 4 5 I've tried my best to make a different editorial, I wish you enjoy it ... 6 7 [1746A - Maxmina](/contest/1746/problem/A "Codeforces Global Round 23") 8 9 problem author: [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Candidate Master MohammadParsaElahimanesh"), [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM") 10 11 **step by step solution** 12 13 step 1: 14 15 It's obvious that the answer is "NO" if $a_{i} = 0$ for all $1 \le i \le n$. 16 17 step 2: 18 19 Lets prove that the answer is "YES" if $a_{i} = 1$ for at least one $1 \le i \le n$. 20 21 step 3: 22 23 If size of $a$ is equal to $k$, just use second type operation once and we are done. 24 25 step 4: 26 27 Otherwise (if $|a| \gt k$), there will be three cases: (assume that $a_{j} = 1$) 28 29 * if $j \gt 2$, you can use first type operation on first and second element and decrease size of $a$ by 1. 30 * else if $j \lt |a|-1$, you can use first type operation on last and second to last element and decrease size of $a$ by 1. 31 * else, it can be shown easily that $|a| = 3$ and $k = 2$ so you can use second type operation twice and turn $a$ into a single $1$. 32 33 In first and second case, you can continue decreasing size of $a$ until $|a| = k$ (or you reach $3$-rd case) and you can use second type operation to reach your aim. 34 35 step 5: 36 37 So we proved that the answer is "YES" iff $a_{i} = 1$ for at least one $1 \le i \le n$ or in other words, iff $\sum_{i = 1}^n a_{i} \gt 0$. 38 39 **solution** 40 41 ``` 42 // In the name of God 43 #include <iostream> 44 45 using namespace std; 46 47 int main() 48 { 49 int t; 50 cin >> t; 51 while(t--) 52 { 53 int n, k; 54 cin >> n >> k; 55 int sum = 0; 56 for(int i = 0 ; i < n ; i++){ 57 int a; 58 cin >> a; 59 sum += a; 60 } 61 if(sum > 0) cout << "YES" << endl; 62 else cout << "NO" << endl; 63 } 64 return 0; 65 } 66 // Thank God 67 ``` 68 69 [1746B - Rebellion](/contest/1746/problem/B "Codeforces Global Round 23") 70 71 problem author: [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Candidate Master MohammadParsaElahimanesh") 72 73 **step by step solution** 74 75 step 1: 76 77 **task** 78 79 Assume that $a_{i} = 0$ for each $1 \le i \le n$, what should we do? 80 81 **solution** 82 83 Nothing! The array is already sorted and the answer is $0$. 84 85 step 2: 86 87 **task** 88 89 After sorting the array, consider the first non-zero element of $a$, how many elements after that are equal to zero? In other words, consider smallest $i$ such that $a_{i} \gt 0$, how many indices $k$ exist such that $i \lt k$ and $a_{k} = 0$? 90 91 **solution** 92 93 0, because we call an array $a$ sorted (in non-decreasing order), if for all $1 \le i \lt j \le n$, $a_{i} \le a_{j}$ holds. So all numbers after leftmost non-zero element must be non-zero too. 94 95 step 3: 96 97 **task** 98 99 assume that after sorting $a$, $a_{i}$ ($1 \le i \le n$) is the leftmost non-zero element. Define $G_{1}$ as the set of indices $j$ such that $1 \le j \lt i$ and $a_{j} \gt 0$ at the beginning, also define $G_{2}$ as the set of indices $j$ such that $i \le j \le n$ and $a_{j} = 0$ at the beginning. What is the answer? 100 101 **solution** 102 103 $max(|G_{1}|, |G_{2}|)$. It's obvious that in one operation at most one element will be deleted from each group. So we must perform at least $max(|G_{1}|, |G_{2}|)$ operations. Now we want to show that it's sufficient too. There are three cases: 104 105 $min(|G_{1}|, |G_{2}|) \gt 1$, at this point, we know that all elements of $a$ are $0$ or $1$. So we can pick one element from $G_{1}$ and add it to an element from $G_{2}$, so the size of both groups will decrease by $1$. It's obvious that all elements of $a$ will remain less than or equal to $1$ after this operation. 106 107 $|G_{1}| = 0$, it's easy to see that we can add $a[k]$ ($k \in G_{2}$) to a random element. So $|G_{2}|$ will decrease by $1$. 108 109 $|G_{2}| = 0$, it's easy to see that we can add $a[k]$ ($k \in G_{1}$) to the last element of $a$. So $|G_{1}|$ will decrease by $1$. 110 111 step 4: 112 113 **task** 114 115 Now how can we solve the problem using previous steps? 116 117 **solution** 118 119 If all elements are equal to $0$, the answer is obviously zero. Otherwise we will calculate two arrays, number of ones in each prefix and number of zeros in each suffix. We will also fix the leftmost non-zero element and calculate the answer for it easily by using Step 3 algorithm in O(n). 120 121 **solution** 122 123 ``` 124 /// In the name of God 125 #include <iostream> 126 127 using namespace std; 128 129 int main() 130 { 131 int t; 132 cin >> t; 133 while(t--) 134 { 135 int n; 136 cin >> n; 137 int A[n], cnt[2][n+1]; 138 cnt[0][0] = cnt[1][0] = 0; 139 for(int i = 0; i < n; i++) 140 { 141 cin >> A[i]; 142 cnt[0][i+1] = cnt[0][i]+(A[i]==0?1:0); 143 cnt[1][i+1] = cnt[1][i]+(A[i]==1?1:0); 144 } 145 int ans = n-1; 146 for(int last_zero = 0; last_zero <= n; last_zero++) 147 ans= min(ans, max(cnt[1][last_zero], cnt[0][n]-cnt[0][last_zero])); 148 cout << ans << endl; 149 } 150 } 151 152 /// Thank God . . . 153 ``` 154 155 [1746C - Permutation Operations](/contest/1746/problem/C "Codeforces Global Round 23") 156 157 problem author: [napstablook](/profile/napstablook "Candidate Master napstablook") 158 159 **step by step solution** 160 161 step 1: 162 163 **task** 164 165 Try to prove that the answer is always zero. Or in other words, we can always make the array $a$ non-decreasing. 166 167 **solution** 168 169 We will prove this fact in next steps. 170 171 step 2: 172 173 **task** 174 175 If some array $a$ is non-decreasing, what can we say about array $d=[a_{2}-a_{1}, a_{3}-a_{2}, ... a_{n}-a_{n-1}]$? 176 177 **solution** 178 179 It's obvious that all elements of array $d$ should be non-negative. 180 181 step 3: 182 183 **task** 184 185 If we perform the $i$-th operation on the suffix starting at index $j$, what happens to array $d$? 186 187 **solution** 188 189 All elements of it will remain the same except $d_{j-1}=a_{j}-a_{j-1}$ which will increase by $i$. 190 191 step 4: 192 193 **task** 194 195 Considering the fact that array $a$ consists only of positive integers, what can we say about $d_{i}=a_{i+1}-a_{i}$? 196 197 **solution** 198 199 Since $a_{i+1} \ge 0$, we can say that $d_{i} \ge -a_{i}$. 200 201 step 5: 202 203 **task** 204 205 Using step 3 and 4 and knowing that $a$ is a permutation of numbers $1$ to $n$, what can we do to make all elements of $d$ non-negative? 206 207 **solution** 208 209 for $i \le n-1$, we can perform $a_{i}$-th operation on the suffix starting from index $i+1$. So $d_{i}$ will increase by $a_{i}$ and since we knew that $d_{i} \ge -a_{i}$, after performing this operation $d_{i} \ge 0$ will hold. So after this steps, elements of $d$ will be non-negative and according to Step 2, that's exactly what we want. It's also easy to see that it doesn't matter how we perform $a_{n}$-th operation, so we can do anything we want. 210 211 **solution** 212 213 ``` 214 /// In the name of God 215 #include <bits/stdc++.h> 216 217 using namespace std; 218 219 inline void solve() 220 { 221 int n; 222 cin >> n; 223 int permutation[n], location[n]; 224 for(int i = 0; i < n; i++) 225 { 226 cin >> permutation[i]; 227 permutation[i]--; 228 location[permutation[i]] = i; 229 } 230 for(int i = 0; i < n; i++) 231 { 232 if(location[i] == n-1) 233 cout << rand()%n+1 << (i == n-1?'\n':' '); 234 else 235 cout << location[i]+2 << (i == n-1?'\n':' '); 236 } 237 } 238 239 int main() 240 { 241 int t; 242 cin >> t; 243 while(t--) 244 solve(); 245 return 0; 246 } 247 /// Thank God . . . 248 ``` 249 250 [1746D - Paths on the Tree](/contest/1746/problem/D "Codeforces Global Round 23") 251 252 problem author: [AquaMoon](/profile/AquaMoon "International Master AquaMoon"), [Cirno_9baka](/profile/Cirno_9baka "International Grandmaster Cirno_9baka"), [mejiamejia](/profile/mejiamejia "Expert mejiamejia"), [ChthollyNotaSeniorious](/profile/ChthollyNotaSeniorious "Master ChthollyNotaSeniorious"), [SSerxhs](/profile/SSerxhs "International Grandmaster SSerxhs"), [TomiokapEace](/profile/TomiokapEace "Expert TomiokapEace") 253 254 **single step solution** 255 256 Define $f(u, cnt)$ represents the maximum score of $cnt$ balls passing through the subtree of node $u$. 257 258 Define $num$ as the number of the sons of node $u$. The transition is only related to $\lceil cnt / num \rceil$ and $\lfloor cnt / num \rfloor$ two states of the subtree. 259 260 For each node $u$, $cnt$ can only be two adjacent integer $(x, x + 1)$. 261 262 It can be proved that the four numbers $\lfloor x/num \rfloor$, $\lceil x/num \rceil$, $\lceil (x + 1)/num \rceil$ and $\lfloor (x + 1)/num \rfloor$ can only have two kinds of numbers at most, and they are adjacent natural numbers. 263 264 So the number of states can be proved to be $\mathcal{O}(n)$. 265 266 **solution** 267 268 ``` 269 /// In the name of God 270 #include <bits/stdc++.h> 271 using namespace std; 272 typedef long long ll; 273 274 const int N = 200000; 275 ll V[N], dp[N]; 276 int dad[N]; 277 vector<int> child[N]; 278 vector<pair<int, ll>> answers[N]; 279 280 inline ll DP(int v, ll k) 281 { 282 for(auto [kp, ans]: answers[v]) 283 if(k == kp) 284 return ans; 285 ll cnt_child = (ll)child[v].size(); 286 ll ans = k*V[v]; 287 if(cnt_child == 0) 288 return ans; 289 if(k%cnt_child == 0) 290 for(auto u: child[v]) 291 ans += DP(u, k/cnt_child); 292 else 293 { 294 ll dp1[cnt_child], dp2[cnt_child], diff[cnt_child]; 295 for(int i = 0; i < cnt_child; i++) 296 dp1[i] = DP(child[v][i], k/cnt_child), dp2[i] = DP(child[v][i], k/cnt_child+1); 297 for(int i = 0; i < cnt_child; i++) 298 diff[i] = dp2[i] - dp1[i]; 299 sort(diff, diff+cnt_child, greater<int>()); 300 for(int i = 0; i < cnt_child; i++) 301 ans += dp1[i]; 302 for(int i = 0; i < k%cnt_child; i++) 303 ans += diff[i]; 304 } 305 answers[v].push_back({k, ans}); 306 return ans; 307 } 308 309 inline ll solve() 310 { 311 ll n, k; 312 cin >> n >> k; 313 for(int i = 0; i < n; i++) 314 child[i].clear(), answers[i].clear(); 315 dad[0] = 0; 316 for(int i = 0; i < n-1; i++) 317 { 318 cin >> dad[i+1]; 319 dad[i+1]--; 320 child[dad[i+1]].push_back(i+1); 321 } 322 for(int i = 0; i < n; i++) 323 cin >> V[i]; 324 return DP(0, k); 325 } 326 327 int main() 328 { 329 int t; 330 cin >> t; 331 while(t--) 332 cout << solve() << '\n'; 333 return 0; 334 } 335 /// Thank God . . . 336 ``` 337 338 [1746E1 - Joking (Easy Version)](/contest/1746/problem/E1 "Codeforces Global Round 23") 339 340 problem author: [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Candidate Master MohammadParsaElahimanesh") 341 342 **step by step solution** 343 344 step 1: 345 346 **task** 347 348 How can we make sure that some statement is not joking? 349 350 **solution** 351 352 If something is told for two times in a row, we can be sure that it's true. For example if we are told that $x \ne 3$ in two consecutive questions, we can be sure that it's true. Because at least one of those questions is answered correctly and that's enough. 353 354 step 2: 355 356 **task** 357 358 What can be found out if we ask about a set $S$? (assume that we will be answered correctly) 359 360 **solution** 361 362 If the answer is "YES", then $x \in S$ and we can reduce our search domain to $S$. Otherwise, we can remove $S$ from the search domain. 363 364 step 3: 365 366 **task** 367 368 Using previous steps, how can we really reduce our search domain? Step 2 can do it only if we have a correct statement about $x$ and using Step 1, we can find something that is surely correct. 369 370 **solution** 371 372 Assume that $V$ is our current search domain. Split it into $4$ subsets $V_{1}, V_{2}, V_{3}$ and $V_{4}$. then ask about following sets: 373 374 * $V_{1} \cup V_{2}$ 375 * $V_{1} \cup V_{3}$ 376 377 It's easy to show that no matter what the answers are, we can always remove at least one of the subsets from the search domain. For example if both answers are "YES", we can remove $V_{4}$ and if both answers are "NO", then we can remove $V_{1}$. 378 379 So after these questions, we can reduce size of search domain by at least $min(|V_{1}|,|V_{2}|,|V_{3}|,|V_{4}|)$, and it's obvious to see that we can choose $V_{i}$'s in such a way that this value is at least $\frac{|V|}{4}$. 380 381 Finally, as long as size of the search domain is greater than $3$, we can reduce it using this algorithm. It can be shown easily that we can reduce our search domain to only $3$ numbers with at most $76$ questions. 382 383 step 4: 384 385 **task** 386 387 Now assume that we have only $3$ candidates for $x$, since we have only $2$ chances to guess, we must remove one of them. How can we do it? Note that since we've used $76$ questions in previous step, we only have $6$ questions left. 388 389 **solution** 390 391 Assume that our three candidates are $a, b$ and $c$. it can be shown that using following questions, we can always remove at least one of them from the search domain: 392 393 * ${a}$ 394 * ${b}$ 395 * ${b}$ 396 * ${a}$ 397 398 After that, when we have only two candidates for $x$, we can guess them one by one and we are done. 399 400 **solution** 401 402 ``` 403 /// In the name of God 404 #pragma GCC optimize("Ofast","unroll-loops","O3") 405 #include <bits/stdc++.h> 406 407 using namespace std; 408 409 inline bool get_answer(){string s; cin >> s; return s == "YES";} 410 411 inline bool f(int i){return i&1;} 412 inline bool g(int i){return i&2;} 413 414 void solve(const vector<int> &Valid) 415 { 416 if(Valid.size() < 3u) 417 { 418 cout << "! " << Valid[0] << endl; 419 string s; 420 cin >> s; 421 if(s == ":)")return; 422 cout << "! " << Valid[1] << endl; 423 return; 424 } 425 else if(Valid.size() == 3u) 426 { 427 bool is[4]; 428 cout << "? 1 " << Valid[0] << endl;is[0] = get_answer(); 429 cout << "? 1 " << Valid[1] << endl;is[1] = get_answer(); 430 cout << "? 1 " << Valid[1] << endl;is[2] = get_answer(); 431 cout << "? 1 " << Valid[0] << endl;is[3] = get_answer(); 432 if(is[1] and is[2])return solve({Valid[1]}); 433 else if(!is[1] and !is[2])return solve({Valid[0], Valid[2]}); 434 else if((is[0] and is[1]) or (is[2] and is[3]))return solve({Valid[0], Valid[1]}); 435 else if((is[0] and !is[1]) or (!is[2] and is[3]))return solve({Valid[0], Valid[2]}); 436 else return solve({Valid[1], Valid[2]}); 437 } 438 else 439 { 440 vector<int> query[2]; 441 for(int i = 0; i < (int)Valid.size(); i++) 442 { 443 if(f(i))query[0].push_back(Valid[i]); 444 if(g(i))query[1].push_back(Valid[i]); 445 } 446 bool is[2]; 447 for(int i = 0; i < 2; i++) 448 { 449 cout << "? " << query[i].size(); 450 for(auto u: query[i])cout << ' ' << u; 451 cout << endl; 452 is[i] = get_answer(); 453 } 454 vector<int> NewValid; 455 for(int i = 0; i < (int)Valid.size(); i++) 456 { 457 if((!f(i) ^ is[0]) or (!g(i) ^ is[1]))NewValid.push_back(Valid[i]); 458 } 459 return solve(NewValid); 460 } 461 } 462 int main() 463 { 464 int n = 0; 465 cin >> n; 466 vector<int> all(n); 467 for(int i = 0; i < n; i++)all[i] = i+1; 468 solve(all); 469 return 0; 470 } 471 /// Thank God . . . 472 ``` 473 474 [1746E2 - Joking (Hard Version)](/contest/1746/problem/E2 "Codeforces Global Round 23") 475 476 problem author: [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Candidate Master MohammadParsaElahimanesh"), [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM") 477 478 **step by step solution** 479 480 step 1: 481 482 First note that in any question we ask, a set will be introduced as the set that contains $x$. If the answer is "YES", then the set that we asked is introduced and otherwise, its complement. 483 484 **task** 485 486 Assume that our current search domain is some set $V$. In addition, assume that $V = A \cup B$ such that set $A$ is the set that introduced to contain $x$ in very last step and $B$ is the set of other candidates for $x$ (candidates that don't belong to $A$). Now assume that in next question, a set $C$ is introduced to contain $x$ such that $C = a \cup b, (a \in A , b \in B)$. what can we do? how can we reduce our search domain after this question? 487 488 **solution** 489 490 Considering the solution of E1, it's not so hard to see that we can remove $B-b$ from our search domain. So our new search domain will be $V' = A' \cup B'$ such that $A' = C = a \cup b$ is the set of candidates that introduced in last question and $B' = A - a$ is the set of other candidates. 491 492 step 2: 493 494 **task** 495 496 Let's calculate minimum needed questions for a search domain of size $n$ using the idea of previous step. 497 498 **solution** 499 500 We can do it using a simple dp, let $dp[A][B]$ be the minimum number of questions needed to find $x$ in a search domain of size $A+B$ in which $A$ numbers are introduced in last question and $B$ numbers are not. In order to calculate our dp, if we ask about some set which consists of $a$ numbers from first set and $b$ numbers from second set, we should update $dp[A][B]$ from $dp[A-a][a+b]$. So we can say that: 501 502 $dp[A][B] = \min_{a \le A , b \le B} dp[A-a][a+b]$ 503 504 . Using this dp and keeping track of its updates, we can simply solve the task. But there is a problem, we don't have enough time to calculate the whole dp. So what can we do? 505 506 step 3: 507 508 **task** 509 510 Since calculating $dp[A][B]$ for $A \lt = n , B \lt = m$ is $O(n^2 \cdot m^2)$, we can only calculate it for small $n$ and $m$ like $n,m \le 100$. What can we do for the rest? Maybe some heuristic method? 511 512 **solution** 513 514 It's not so hard to see that for most $A$ and $B$ (especially for large values) it's best to update $dp[A][B]$ from something around $dp[A-A/2][A/2+B/2]$ (in other words, asking $A/2$ numbers from the first set and $B/2$ numbers from the second one). Using such method, we can calculate dp in a reasonable time and with a very good accuracy, and this accuracy is enough to find the answer in less than $53$ questions. 515 516 **solution** 517 518 ``` 519 /// In the name of God 520 #pragma GCC optimize("Ofast","unroll-loops","O3") 521 #include <bits/stdc++.h> 522 523 using namespace std; 524 525 const int SUM = 50; 526 int dp[SUM][SUM]; 527 pair<int,int> updater[SUM][SUM]; 528 map<pair<int,int>, int> Dp; 529 map<pair<int,int>, pair<int,int>> Updater; 530 531 inline void preprocess() 532 { 533 for(int i = 0; i < SUM; i++) 534 { 535 for(int j = 0; j < SUM; j++) 536 { 537 dp[i][j] = SUM; 538 updater[i][j] = {i, j}; 539 } 540 } 541 dp[0][0] = dp[0][1] = dp[1][0] = dp[2][0] = dp[1][1] = dp[0][2] = 0; 542 for(int sum = 0; sum < SUM; sum ++)for(int last = sum; last >= 0; last--) 543 { 544 int now = sum - last; 545 for(int SelectLast = 0; SelectLast <= last; SelectLast++)for(int SelectNow = 0; SelectNow <= now; SelectNow++) 546 { 547 if(dp[last][now] > 1 + max(dp[now-SelectNow][SelectNow+SelectLast], dp[SelectNow][sum-SelectNow-SelectLast])) 548 { 549 dp[last][now] = 1 + max(dp[now-SelectNow][SelectNow+SelectLast], dp[SelectNow][now+last-SelectNow-SelectLast]); 550 updater[last][now] = {SelectLast, SelectNow}; 551 } 552 } 553 } 554 } 555 556 inline int DP(const int last, const int now) 557 { 558 if(last < 0 || now < 0)return SUM; 559 if(last + now < SUM)return dp[last][now]; 560 if(Dp.find({last, now}) != Dp.end())return Dp[{last, now}]; 561 if((last&1) && (now&1)) 562 { 563 Dp[{last, now}] = 1 + DP((now+1)/2, (last+ now)/2); 564 Updater[{last, now}] = {(last+1)/2, now/2}; 565 } 566 else 567 { 568 Dp[{last, now}] = 1 + DP((now+1)/2, (last+1)/2+(now+1)/2); 569 Updater[{last, now}] = {(last+1)/2, (now+1)/2}; 570 } 571 return Dp[{last, now}]; 572 } 573 574 inline bool IsIn(const int x, const vector<int> &Sorted) 575 { 576 auto u = lower_bound(Sorted.begin(), Sorted.end(), x); 577 if(u == Sorted.end() or *u != x)return false; 578 return true; 579 } 580 581 vector<int> solve(const vector<int> &LastAns, const vector<int> &Valid) 582 { 583 if((int)Valid.size() < 3) 584 { 585 return Valid; 586 } 587 pair<int,int> Select; 588 if((int)Valid.size() < SUM) 589 { 590 Select = updater[LastAns.size()][Valid.size()-LastAns.size()]; 591 } 592 else 593 { 594 DP((int)LastAns.size(), (int)(Valid.size()-LastAns.size())); 595 Select = Updater[{LastAns.size(), Valid.size()-LastAns.size()}]; 596 } 597 vector<int> query; 598 int p = 0; 599 while(Select.first --)query.push_back(LastAns[p++]); 600 p = 0; 601 vector<int> LastAnsSorted = LastAns; 602 sort(LastAnsSorted.begin(), LastAnsSorted.end()); 603 while(Select.second --) 604 { 605 while(IsIn(Valid[p], LastAnsSorted)) p++; 606 query.push_back(Valid[p++]); 607 } 608 cout << "? " << query.size(); 609 for(auto u: query)cout << ' ' << u; 610 cout << endl; 611 612 string s; 613 cin >> s; 614 bool correct = (s == "YES"); 615 sort(query.begin(), query.end()); 616 vector<int> NewLast, NewValid; 617 for(auto u: Valid) 618 { 619 if(!IsIn(u, LastAnsSorted) and (correct ^ IsIn(u, query))) 620 { 621 NewLast.push_back(u); 622 } 623 if(!IsIn(u, LastAnsSorted) or !(correct ^ IsIn(u, query))) 624 { 625 NewValid.push_back(u); 626 } 627 } 628 vector<int> ans = solve(NewLast, NewValid); 629 return ans; 630 } 631 632 int main() 633 { 634 preprocess(); 635 636 int n; 637 cin >> n; 638 vector<int> all(n); 639 for(int i = 0; i < n; i++)all[i] = i+1; 640 vector<int> valid = solve({}, all); 641 for(auto guess: valid) 642 { 643 cout << "! " << guess << endl; 644 string s; 645 cin >> s; 646 if(s == ":)")return 0; 647 } 648 649 return 0; 650 } 651 /// Thank God . . . 652 ``` 653 654 [1746F - Kazaee](/contest/1746/problem/F "Codeforces Global Round 23") 655 656 problem author: [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Candidate Master MohammadParsaElahimanesh") 657 658 **step by step solution** 659 660 step 1: 661 662 First of all, we can compress $a_{i}$'s and $x$'s (in second type query). so we can assume that all numbers are less than $n+q \le 6 \cdot 10^5$. 663 664 step 2: 665 666 **task** 667 668 Lets first solve the problem for smaller constrains. 669 670 **solution** 671 672 We can use data structures like fenwick tree or segment tree to count the number of occurrences of each number and check if it's divisible by $k$ to answer second type query. And we can simply update our data structure after each query of the first type. 673 674 So if we use something like fenwick tree, we can handle everything in $O((n+q) \cdot n + (n+q) \cdot q \cdot log_{2}(n))$. 675 676 step 3: 677 678 **task** 679 680 Obviously we can not use previous step solution for original constrains. In other words, we don't have enough time to check all numbers one by one. How can we do better? Checking them together?! 681 682 **solution** 683 684 It's obviously not a good idea to check all numbers together (checking that sum of their occurrences is divisible by $k$). So what can we do? What if we check a random subset of numbers? 685 686 step 4: 687 688 **task** 689 690 Assume that $S$ is a random subset of all numbers, it's obvious that if the answer of the query is "YES" (number of occurrences of every number is divisible by $k$), the condition holds for $S$ too (sum of number of occurrences of numbers that belong to $S$ is divisible by $k$). What about the opposite? What is the probability that the answer of the query is "NO" and yet sum of occurrences of numbers belonging to $S$ is divisible by $k$? 691 692 **solution** 693 694 It's not so hard to prove that the probability is equal to $\frac{1}{2}$ for $k = 2$ and it's less than $\frac{1}{2}$ for $k \ge 2$. So in general, the probability that a random subset $S$ leads to a wrong answer is less than or equal to $\frac{1}{2}$. So if we use something like $30$ random subsets, the probability will be less than $\frac{1}{2^{30}}$ which is reasonable for problem constrains and we can use this random method to solve the task. 695 696 **solution** 697 698 ``` 699 #include <bits/stdc++.h> 700 701 using namespace std; 702 703 typedef long long int ll; 704 705 mt19937 rnd(time(0)); 706 707 const int N = 300'000 + 5; 708 const int Q = 300'000 + 5; 709 const int T = 50; 710 bitset<N+Q> RandomSet[T]; 711 unordered_map<int, int> id; int cnt_id = 0; 712 int n, q, A[N]; 713 714 struct fenwick 715 { 716 int PartialSum[N]; 717 fenwick() 718 { 719 for(int i = 0; i < N; i++)PartialSum[i] = 0; 720 } 721 inline void add(int index, bool increase) 722 { 723 while(index < N) 724 { 725 PartialSum[index] += (increase? 1 : -1); 726 index += index&-index; 727 } 728 } 729 inline int get(int index) 730 { 731 int sum = 0; 732 while(index) 733 { 734 sum += PartialSum[index]; 735 index -= index&-index; 736 } 737 return sum; 738 } 739 }Fen[T]; 740 741 inline int GetId(const int x) 742 { 743 auto id_iterator = id.find(x); 744 if(id_iterator == id.end()) 745 { 746 return id[x] = cnt_id++; 747 } 748 else return (*id_iterator).second; 749 } 750 751 inline void ChooseRandomSets() 752 { 753 for(int i = 0; i < T; i++) 754 { 755 for(int j = 0; j < N+Q; j++) 756 { 757 if(rnd()&1)RandomSet[i].set(j); 758 } 759 } 760 } 761 762 inline void AddArrayToFenwick() 763 { 764 for(int i = 0; i < n; i++) 765 { 766 int MyId = GetId(A[i]); 767 for(int j = 0; j < T; j++) 768 { 769 if(RandomSet[j][MyId])Fen[j].add(i+1, true); 770 } 771 } 772 } 773 774 inline void Query() 775 { 776 int index, l, r, k, x, type; 777 for(int i = 0; i < q; i++) 778 { 779 cin >> type; 780 if(type == 1) 781 { 782 cin >> index >> x; 783 index --; 784 int IdPre = GetId(A[index]); 785 int IdNew = GetId(x); 786 A[index] = x; 787 for(int j = 0; j < T; j++) 788 { 789 if(RandomSet[j][IdPre])Fen[j].add(index+1, false); 790 if(RandomSet[j][IdNew])Fen[j].add(index+1, true); 791 } 792 } 793 if(type == 2) 794 { 795 cin >> l >> r >> k; 796 l--; 797 if(k == 1){cout << "YES\n"; continue;} 798 else if((r-l)%k != 0){cout << "NO\n"; continue;} 799 bool answer = true; 800 for(int j = 0; j < T; j++) 801 { 802 if((Fen[j].get(r)-Fen[j].get(l))%k != 0){answer = false; break;} 803 } 804 cout << (answer?"YES":"NO") << '\n'; 805 } 806 } 807 } 808 809 int main() 810 { 811 ios::sync_with_stdio(false) , cin.tie(0); 812 ChooseRandomSets(); 813 cin >> n >> q; 814 for(int i = 0; i < n; i++) cin >> A[i]; 815 AddArrayToFenwick(); 816 Query(); 817 return 0; 818 } 819 ``` 820 821 [1746G - Olympiad Training](/contest/1746/problem/G "Codeforces Global Round 23") 822 823 problem idea: [SirShokoladina](/profile/SirShokoladina "International Grandmaster SirShokoladina") 824 825 problem development: [SomethingNew](/profile/SomethingNew "Grandmaster SomethingNew"), [pakhomovee](/profile/pakhomovee "Master pakhomovee"), [SirShokoladina](/profile/SirShokoladina "International Grandmaster SirShokoladina") 826 827 **single step solution** 828 829 Consider all subsets of the original set in which tasks can be performed in some order to satisfy the constraints on their completion, and also that the size of each of them does not exceed $a+b+c$. It is easy to show that this set is a weighted matroid. This means that the optimal set of tasks can be found using a greedy algorithm. 830 831 So, we can find a set of tasks with maximum total usefulness, which: 832 833 * satisfies all deadline constraints 834 * has no more than $a+b+c$ elements 835 836 For the given parameters $(x, y, z)$, we introduce the following transformation: 837 838 * Increase the usefulness of all tasks of the first type by $x$, the second type~--- by $y$, and the third type~--- by $z$. 839 840 Let's assume that the optimal solution after the transformation is described by the triple $[a',b',c']$~--- the number of problems of each type, respectively. We need to get a solution described by the triple $[a,b,c]$. For $[a,b,c] \neq [a',b',c']$, $a+b+c=a'+b'+c'$ holds. Then (without limitation of generality, since there are at least two inequalities among $a\vee a',b\vee b',c\vee c'$) we assume that $a' \gt a,b' \lt b$. 841 842 Consider the following coordinate system on a two-dimensional plane (modulo the addition of $\overrightarrow{(1;1;1)})$: 843 844  845 846 For the coordinates of the point, we take the value $\vec{x}\times x+\vec{y}\times y + \vec{z}\times z$$(\vec{x}+\vec{y}+\vec{z} =\vec{0})$. It is easy to understand that the coordinates of the point $(x; y)$ on the plane are uniquely set by the triple $(x; y; z)$ up to the addition of $\overrightarrow{(1;1;1)} \times k, k \in\mathbb{Z}$ 847 848 Let's assume that there are parameters $(x,y,z)$ for which the optimal solution is unique and equal to $[a,b,c]$ (see "But what if..?" to see what needs to be done to the input to make this hold). 849 850 Consider the solution $[a',b',c']$ for the "center" of the current polygon (initially it is a hexagon with infinitely distant coordinates). The "center" is the center of the triangle formed by the middle lines of our polygon. 851 852 On this plane, decreasing $z$ or $y$ does not increase $b'+c'$, therefore, it does not decrease $a'$. Thus, the red area in the picture below does not suit us. 853 854 Increasing $x$ or $z$ does not decrease $a'+c'$, therefore, it does not increase $b'$. Because of this, the blue area in the picture below does not suit us either. 855 856  857 858 So, we need to cut off one half-plane along the $z$ axis. It can be shown that the area of the polygon under consideration decreases by a constant time for every 2-3 iterations. 859 860 But what if the number of tasks of the desired color jumps from $a-1$ to $a+1$ at once? This is possible if and only if with the addition of some $x$ we get several pairs of elements of equal weight at the same time. To get rid of this, we can simply add a random number from $0$ to $\frac{1}{3}$ to each weight. The fact that such a change will fix the problem described above and will not change the optimal answer to the original problem remains to the reader as an exercise (the authors have proof). 861 862 After $O(\log C)$ iterations, our algorithm will converge to a point (a triple of real numbers). It remains only to check that the solution found is suitable for us. 863 864 $O(n\log n\log C)$ 865 866 **solution** 867 868 ``` 869 #include <bits/stdc++.h> 870 using namespace std; 871 872 #ifdef SG 873 #include <debug.h> 874 #else 875 template<typename T> struct outputer; 876 struct outputable {}; 877 #define PRINT(...) 878 #define OUTPUT(...) 879 #define show(...) 880 #define debug(...) 881 #define deepen(...) 882 #define timer(...) 883 #define fbegin(...) 884 #define fend 885 #define pbegin(...) 886 #define pend 887 #endif 888 889 #define ARG4(_1,_2,_3,_4,...) _4 890 891 #define forn3(i,l,r) for (int i = int(l); i < int(r); ++i) 892 #define forn2(i,n) forn3 (i, 0, n) 893 #define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__) 894 895 #define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i) 896 #define ford2(i,n) ford3 (i, 0, n) 897 #define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__) 898 899 #define ve vector 900 #define pa pair 901 #define tu tuple 902 #define mp make_pair 903 #define mt make_tuple 904 #define pb emplace_back 905 #define fs first 906 #define sc second 907 #define all(a) (a).begin(), (a).end() 908 #define sz(a) ((int)(a).size()) 909 910 typedef long double ld; 911 typedef signed __int128 lll; 912 typedef unsigned __int128 ulll; 913 typedef int64_t ll; 914 typedef uint64_t ull; 915 typedef uint32_t ui; 916 typedef uint16_t us; 917 typedef uint8_t uc; 918 typedef pa<int, int> pii; 919 typedef pa<int, ll> pil; 920 typedef pa<ll, int> pli; 921 typedef pa<ll, ll> pll; 922 typedef ve<int> vi; 923 924 template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;} 925 template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;} 926 template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;} 927 928 const int N = 100000; 929 const int X = 1000000000; 930 const int T = 3; 931 932 struct Input { 933 int n; 934 std::array<int, T> k; 935 int a[N], t[N], d[N]; 936 937 bool read() { 938 if (!(cin >> n)) { 939 return 0; 940 } 941 forn (i, T) { 942 cin >> k[i]; 943 } 944 forn (i, n) { 945 cin >> a[i] >> t[i] >> d[i]; 946 --t[i]; 947 --d[i]; 948 } 949 return 1; 950 } 951 952 void init(const Input& input) { 953 *this = input; 954 } 955 }; 956 957 struct Data: Input { 958 ll ans; 959 960 void write() { 961 cout << ans << endl; 962 } 963 }; 964 965 966 namespace Main { 967 const lll P = 2 * N + 1; 968 const lll Q = 2 * N + 2; 969 const lll R = 2 * N + 3; 970 const lll A[3] = {3 * P * Q, 3 * P * R, 3 * Q * R}; 971 const lll M = 3 * P * Q * R * N; 972 const lll inf = (X + 1) * M; 973 974 struct SNM { 975 int rnd = 0; 976 int n; 977 int pr[N]; 978 979 void init(int cnt) { 980 n = cnt; 981 forn (i, n) { 982 pr[i] = i; 983 } 984 } 985 986 int get_p(int v) { 987 if (v < 0 || pr[v] == v) { 988 return v; 989 } 990 return pr[v] = get_p(pr[v]); 991 } 992 993 bool add(int v) { 994 v = get_p(v); 995 if (v == -1) { 996 return 0; 997 } 998 pr[v] = v - 1; 999 return 1; 1000 } 1001 }; 1002 1003 struct Solution: Data { 1004 SNM snm; 1005 1006 int m; 1007 lll b[N], c[N]; 1008 vi ord[T]; 1009 1010 array<int, T> check(const array<lll, T>& adds) { 1011 forn (i, n) { 1012 c[i] = b[i] + adds[t[i]]; 1013 } 1014 auto cmp = [&](int lhs, int rhs) { 1015 return c[lhs] > c[rhs]; 1016 }; 1017 static vi q; 1018 q.clear(); 1019 forn (i, T) { 1020 static vi w; 1021 w.resize(sz(q) + sz(ord[i])); 1022 merge(all(q), all(ord[i]), w.begin(), cmp); 1023 q.swap(w); 1024 } 1025 1026 snm.init(n); 1027 array<int, T> cnt{}; 1028 int tot = 0; 1029 ll val = 0; 1030 for (int i : q) { 1031 if (tot >= m) { 1032 break; 1033 } 1034 if (snm.add(d[i])) { 1035 cnt[t[i]]++; 1036 tot++; 1037 val += a[i]; 1038 } 1039 } 1040 if (cnt == k) { 1041 ans = val; 1042 } 1043 return cnt; 1044 } 1045 1046 // x[i] == adds[(i + 1) % T] - adds[i] 1047 1048 array<lll, T> get_middle_point(const array<lll, T>& lb, const array<lll, T>& rb) { 1049 array<lll, T> x; 1050 forn (i, T) { 1051 x[i] = lb[i] + rb[i]; 1052 } 1053 lll sum = accumulate(all(x), lll(0)); 1054 forn (i, T) { 1055 x[i] = T * x[i] - sum; 1056 if (x[i] >= 0) { 1057 x[i] /= (2 * T); 1058 } else { 1059 x[i] = (x[i] - 2 * T + 1) / (2 * T); 1060 } 1061 } 1062 sum = accumulate(all(x), lll(0)); 1063 forn (i, T) { 1064 if (sum < 0 && x[i] < rb[i]) { 1065 x[i]++; 1066 sum++; 1067 } 1068 assert(x[i] >= lb[i]); 1069 assert(x[i] <= rb[i]); 1070 } 1071 assert(sum == 0); 1072 return x; 1073 } 1074 1075 bool search() { 1076 array<lll, T> lb, rb; 1077 forn (i, T) { 1078 lb[i] = -2 * inf; 1079 rb[i] = 2 * inf; 1080 } 1081 1082 while (true) { 1083 { 1084 lll sum_l = accumulate(all(lb), lll(0)); 1085 lll sum_r = accumulate(all(rb), lll(0)); 1086 forn (i, T) { 1087 lll sol = sum_l - lb[i]; 1088 lll sor = sum_r - rb[i]; 1089 umx(lb[i], -sor); 1090 umn(rb[i], -sol); 1091 if (lb[i] > rb[i]) { 1092 return 0; 1093 } 1094 } 1095 } 1096 array<lll, T> x = get_middle_point(lb, rb); 1097 array<lll, T> adds{}; 1098 forn (i, T - 1) { 1099 adds[i + 1] = adds[i] + x[i]; 1100 } 1101 array<int, T> cnt = check(adds); 1102 assert(accumulate(all(cnt), 0) == m); 1103 if (cnt == k) { 1104 return 1; 1105 } 1106 forn (i, T) { 1107 lll d1 = cnt[i] - k[i]; 1108 lll d2 = cnt[(i + 1) % T] - k[(i + 1) % T]; 1109 if (d1 > 0 && d2 < 0) { 1110 lb[i] = x[i] + 1; 1111 } 1112 if (d1 < 0 && d2 > 0) { 1113 rb[i] = x[i] - 1; 1114 } 1115 } 1116 } 1117 } 1118 1119 void solve() { 1120 forn (i, n) { 1121 b[i] = a[i] * M + i * A[t[i]]; 1122 } 1123 forn (i, n) { 1124 ord[t[i]].pb(i); 1125 } 1126 forn (i, T) { 1127 sort(all(ord[i]), [&](int lhs, int rhs) { 1128 return b[lhs] > b[rhs]; 1129 }); 1130 } 1131 m = accumulate(all(k), 0); 1132 1133 { 1134 array<int, T> r = check({}); 1135 if (accumulate(all(r), 0) != m) { 1136 ans = -1; 1137 return; 1138 } 1139 } 1140 forn (i, T) { 1141 array<lll, T> adds{}; 1142 adds[i] = inf; 1143 if (check(adds)[i] < k[i]) { 1144 ans = -1; 1145 return; 1146 } 1147 adds[i] = -inf; 1148 if (check(adds)[i] > k[i]) { 1149 ans = -1; 1150 return; 1151 } 1152 } 1153 assert(search()); 1154 } 1155 1156 void clear() { 1157 forn (i, T) { 1158 ord[i].clear(); 1159 } 1160 } 1161 }; 1162 } 1163 1164 1165 Main::Solution sol; 1166 1167 int main() { 1168 #ifdef SG 1169 freopen((problemname + ".in").c_str(), "r", stdin); 1170 // freopen((problemname + ".out").c_str(), "w", stdout); 1171 #endif 1172 1173 int t; 1174 cin >> t; 1175 forn (i, t) { 1176 sol.read(); 1177 sol.solve(); 1178 sol.write(); 1179 sol.clear(); 1180 } 1181 1182 return 0; 1183 } 1184 ```