2208.md (16407B)
1 Source: https://codeforces.com/blog/entry/152073 2 3 We hope that you have enjoyed our problems! 4 5 [2208A - Bingo Candies](/contest/2208/problem/A "Codeforces Round 1086 (Div. 2)") 6 7 Idea by [Mindeveloped](/profile/Mindeveloped "Grandmaster Mindeveloped"), prepared by [Mindeveloped](/profile/Mindeveloped "Grandmaster Mindeveloped") 8 9 **Hint 1** 10 11 It is always possible to rearrange the candies, unless candies of one specific color appears too often. 12 13 **Solution** 14 15 Let $x$ be the color with the highest number of candies. In case of ties, $x$ could be any of the candidates. Denote the number of candies with color $x$ as $a$. 16 17 Conclusion: The answer to the problem is `YES` if and only if there are no more than $n^2 - n$ candies of color $x$; — in other words, $a\le n^2 - n$ holds. 18 19 Proof of necessity: If there are more than $n^2 - n$ candies of color $x$, then there are less than $n$ candies not of color $x$. Since there are $n$ rows, at least one row will have no candies not of color $x$; therefore, such a row will be filled with candies of color $x$, violating the restrictions. 20 21 Proof of sufficiency: If there are no more than $n^2 - n$ candies of color $x$, we can always construct a solution with the method below. 22 23 First, if $a \lt n$ holds, then we can arrange the candies arbitrarily because no color has enough candies to fill a row or a column. 24 25 Otherwise, $n\le a\le n^2 - n$ holds. 26 27 We can put candies of color $x$ in $a_{1,1},a_{2,2},\ldots,a_{n,n}$. This will take $n$ candies of color $x$. Next, we choose $n$ candies not of color $x$ arbitrarily. We will put them at $a_{1,2},a_{2,3},\ldots,a_{n-1,n},a_{n,1}$. Lastly, we arrange other candies that have not yet been arranged arbitrarily. Since in the first step we put a candy of color $x$ in each row and column, and in the second step we put a candy not of color $x$ in each row and column, each row and column contains at least candies of two colors, satisfying the constraints. 28 29 **Code** 30 31 ``` 32 #include<bits/stdc++.h> 33 #define F(i,x,y) for (int i=(x);i<=(y);i++) 34 #define R(i,x,y) for (int i=(x);i>=(y);i--) 35 #define p2i pair<int,int> 36 #define ll long long 37 #define fi first 38 #define se second 39 #define nb(x) (1<<((x)-1)) 40 #define x1 __melody1 41 #define x2 __melody2 42 #define y1 __melody3 43 #define y2 __melody4 44 #define iosoptim ios::sync_with_stdio(0);cin.tie(0); 45 using namespace std; 46 47 const bool MT = 1; 48 int n,cnt[10005]; 49 void ygg(){ 50 cin>>n; 51 int tmp; 52 bool flag=1; 53 F(i,1,n*n) { 54 cin>>tmp; 55 ++cnt[tmp]; 56 if (cnt[tmp]>n*(n-1)) flag=0; 57 } 58 if (flag) cout<<"YES\n"; 59 else cout<<"NO\n"; 60 } 61 void mark() { 62 F(i,1,n*n) cnt[i]=0; 63 } 64 int main (){ 65 #ifdef ONLINE_JUDGE 66 iosoptim 67 #endif 68 int testcases=1; 69 if(MT) cin>>testcases; 70 while(testcases--){ 71 ygg(); 72 mark(); 73 } 74 return 0; 75 } 76 ``` 77 78 **Rate the problem!** 79 80 good 81 82 mid 83 84 bad 85 86 didn't solve 87 88 [2208B - Cyclists](/contest/2208/problem/B "Codeforces Round 1086 (Div. 2)") 89 90 Idea by [Mindeveloped](/profile/Mindeveloped "Grandmaster Mindeveloped"), prepared by [Mindeveloped](/profile/Mindeveloped "Grandmaster Mindeveloped") 91 92 **Solution** 93 94 For the sake of simplicity, let's assume all cards have different costs. If multiple cards have the same cost, we break ties by their initial position in the deck (the earlier card is considered to have a lower cost for the purpose of the strategy). 95 96 The optimal strategy: If the win-condition is among the first $k$ cards, then we play it. Otherwise, we play the card in the first $k$ places with the lowest cost. Proof of optimality is shown below. 97 98 Lemma: If at any time, the win-condition is placed at position $x \gt k$, the cost used before the win-condition is played again is at least the sum of the costs of $x-k$ cards with the lowest costs out of all the $x-1$ cards placed before the win-condition. Our strategy reaches this minimum value. 99 100 Proof: 101 102 Since playing any card in front of the win-condition moves the win-condition 1 place toward the front, we need to play $x-k$ normal cards before the win-condition is playable. 103 104 Before the win-condition moves to position $k$ and becomes playable, every card placed before the win-condition can be played at most once, and every card placed at the back of the win-condition cannot be played. Therefore, the cost used is at least the sum of the first $x-k$ lowest costs of the cards initially placed before the win-condition. We mark the $x-k$ cards placed before the win-condition with the lowest costs. 105 106 Among all the $x-1$ cards placed before the win-condition, exactly $k-1$ cards are not marked, so whenever before the win-condition is played the first time, at least one marked card will be in the first $k$ places. Therefore, our strategy will always play a marked card in the first $x-k$ plays since their costs are always lower than not marked ones. Since each marked card can be only played for at most once, after $x-k$ plays we will play each marked card once, which achieves the lower bound described above. 107 108 Therefore, the lemma is proven. 109 110 Now, let $A$ be the sum of the costs of $p-k$ cards with the lowest costs placed before the win-condition. Let $B$ be the sum of the costs of $n-k$ cards with the lowest costs, without considering the win-condition. 111 112 By the above lemma, the cost spent before playing the win-condition the first time is at least $A$. After it is played each time, it always gets placed at position $n$, so the cost spent before playing the win-condition another time is at least $B$. Our strategy achieves the minimum. 113 114 Therefore, the cost used to play the win-condition any non-negative number of times is minimized, which proves the optimality of the strategy. 115 116 The answer is $\lfloor \dfrac{m-A-a_p}{B+a_p}\rfloor + 1$ if $m-A-a_p\ge 0$. Otherwise, the answer is $0$. 117 118 The value of $A$ and $B$ can be calculated with a priority queue in $O(n\log n)$. Therefore, the overall time complexity is $O(n\log n)$. 119 120 Alternatively, you may simulate the strategy above directly; the time complexity will be $O(nm)$, which is also sufficient to pass. 121 122 **Code** 123 124 ``` 125 #include<bits/stdc++.h> 126 #define F(i,x,y) for (int i=(x);i<=(y);i++) 127 #define R(i,x,y) for (int i=(x);i>=(y);i--) 128 #define p2i pair<int,int> 129 #define ll long long 130 #define fi first 131 #define se second 132 #define nb(x) (1<<((x)-1)) 133 #define x1 __melody1 134 #define x2 __melody2 135 #define y1 __melody3 136 #define y2 __melody4 137 #define iosoptim ios::sync_with_stdio(0);cin.tie(0); 138 using namespace std; 139 140 const bool MT = 1; 141 int n,k,p,a[100005]; 142 ll m; 143 void ygg(){ 144 cin>>n>>k>>p>>m; 145 F(i,1,n) cin>>a[i]; 146 multiset<int> opt; 147 F(i,1,k-1) opt.insert (a[i]); 148 F(i,k,p-1) { 149 opt.insert (a[i]); 150 m-=*opt.begin (); 151 opt.erase (opt.begin ()); 152 } 153 m-=a[p]; 154 if (m<0) { 155 cout<<0<<"\n"; 156 return; 157 } 158 ll sum=a[p]; 159 opt.clear (); 160 F(i,1,n) { 161 if (i!=p) opt.insert (a[i]); 162 } 163 F(i,1,n-k) { 164 sum+=*opt.begin (); 165 opt.erase (opt.begin ()); 166 } 167 cout<<1+m/sum<<"\n"; 168 } 169 void mark() { 170 171 } 172 int main (){ 173 #ifdef ONLINE_JUDGE 174 iosoptim 175 #endif 176 int testcases=1; 177 if(MT) cin>>testcases; 178 while(testcases--){ 179 ygg(); 180 mark(); 181 } 182 return 0; 183 } 184 ``` 185 186 **Rate the problem!** 187 188 good 189 190 mid 191 192 bad 193 194 didn't solve 195 196 [2208C - Stamina and Tasks](/contest/2208/problem/C "Codeforces Round 1086 (Div. 2)") 197 198 Idea by [tybbs](/profile/tybbs "Expert tybbs"), prepared by [tybbs](/profile/tybbs "Expert tybbs") 199 200 **Solution** 201 202 Notice that the value of $S$ does not affect your decision. This meant for integer $i\in[1,n-1]$ the decision of tasks $[1,i]$ does not affect the decision of tasks $[i+1,n]$. 203 204 Let $f_i$ be the answer for considering tasks $[i,n]$ only and assuming that $S=1$. It holds that $f_i=\max(f_{i+1},f_{i+1}\cdot(1-\frac{p_i}{100})+c_i)$, and $f_1$ is the answer needed. 205 206 **Code** 207 208 ``` 209 #include<bits/stdc++.h> 210 #define ld long double 211 using namespace std; 212 const int N=1e5+5; 213 ld c[N],p[N]; 214 void solve(){ 215 int n; 216 cin>>n; 217 for(int i=1;i<=n;i++){ 218 int cv,pv; 219 cin>>cv>>pv; 220 c[i]=cv,p[i]=pv/100.0; 221 } 222 ld ans=0; 223 for(int i=n;i>=1;i--){ 224 ans=max(ans,ans*(1-p[i])+c[i]); 225 } 226 cout<<fixed<<setprecision(10)<<ans<<"\n"; 227 } 228 int main(){ 229 ios::sync_with_stdio(0); 230 cin.tie(0); 231 int T; 232 cin>>T; 233 for(int i=1;i<=T;i++) solve(); 234 } 235 ``` 236 237 **Rate the problem!** 238 239 good 240 241 mid 242 243 bad 244 245 didn't solve 246 247 [2208D2 - Tree Orientation (Hard Version)](/contest/2208/problem/D2 "Codeforces Round 1086 (Div. 2)") 248 249 Idea by [tybbs](/profile/tybbs "Expert tybbs"), prepared by [tybbs](/profile/tybbs "Expert tybbs") 250 251 **Hint 1** 252 253 If a solution exists, it must be unique. 254 255 **Hint 2** 256 257 Assume a solution exists, construct the graph accordingly, and verify afterward that it satisfies all given conditions. 258 259 **Hint 3** 260 261 Consider the necessary and sufficient condition for the existence of a directed edge $ u \to v $. 262 263 **Answer to Hint 3 (Solution for D1)** 264 265 Two conditions must hold: 266 1. Node $ v $ must be reachable from $ u $. 267 2. There must be no intermediate node $ w $ such that $ u $ can reach $ w $ and $ w $ can reach $ v $. 268 269 Implementing this directly yields an $ O(n^3) $ solution, which is sufficient for D1. One can further optimize it to $ O\left(\frac{n^3}{\omega}\right) $ using bitsets, though this is not required for this subtask. 270 271 **Hint 4** 272 273 Let $ R_u $ denote the set of nodes reachable from $ u $, excluding $ u $ itself. 274 275 Let $ s_u $ denote the number of nodes reachable from $ u $. Among all nodes in $ R_u $, let $ v $ be the one with the largest $ s_v $. What can we infer? 276 277 **Answer to Hint 4** 278 279 It can be proven that the edge $ u \to v $ must exist in the solution. 280 281 **Solution** 282 283 We iteratively apply the idea from Hint 4: 284 285 * Find the node $ v \in R_u $ with the largest $ s_v $, and add the edge $ u \to v $. 286 * Then remove all nodes in $ R_v $ from $ R_u $, since they are already reachable from $ u $ indirectly via $ v $, and therefore cannot have a direct edge from $ u $. 287 * Repeat this process until $ R_u $ becomes empty. At that point, all outgoing edges from $ u $ have been determined. 288 289 Since the final graph is a tree with exactly $ n - 1 $ edges, the total number of such removal operations across all nodes is $ O(n) $. Each operation involves scanning or updating a set of size at most $ n $, leading to an overall time complexity of $ O(n^2) $. 290 291 **Code** 292 293 ``` 294 #include <bits/stdc++.h> 295 using namespace std; 296 constexpr int N = 1e4+5; 297 int n, id[N], cnt[N]; 298 bool vs[N], e[N][N]; 299 struct Dsu { 300 int fa[N]; 301 void init(int n) { 302 for (int i = 1; i <= n; i++) fa[i] = i; 303 } 304 int find(int x) { 305 if (x == fa[x]) return x; 306 return fa[x] = find(fa[x]); 307 } 308 void merge(int x, int y) { 309 fa[find(x)] = find(y); 310 } 311 } dsu; 312 bool reach[N]; 313 vector<int> tree[N]; 314 void search(int u) { 315 reach[u] = 1; 316 for (int v : tree[u]) { 317 search(v); 318 } 319 } 320 void solve(int tid) { 321 cin >> n; 322 for (int i = 1; i <= n; i++) cnt[i] = 0, tree[i].clear(); 323 for (int u = 1; u <= n; u++) { 324 id[u] = u; 325 string s; 326 cin >> s; 327 for (int v = 1; v <= n; v++) { 328 e[u][v] = s[v-1]-'0'; 329 cnt[u] += e[u][v]; 330 } 331 } 332 sort(id + 1, id + n + 1, [&](int u, int v) { 333 return cnt[u] > cnt[v]; 334 }); 335 vector<pair<int, int >> edges; 336 for (int u = 1; u <= n; u++) { 337 for(int i = 1; i <= n; i++) { 338 vs[i] = false; 339 } 340 vs[u] = true; 341 for (int i = 1; i <= n; i++) { 342 int v = id[i]; 343 if (!vs[v] && e[u][v]) { 344 edges.push_back({u, v}); 345 if(edges.size() >= n) { 346 cout << "No" << "\n"; 347 return ; 348 } 349 for (int w = 1; w <= n; w++) { 350 if (e[v][w]) { 351 vs[w] = true; 352 } 353 } 354 } 355 } 356 } 357 if (edges.size() != n - 1) { 358 cout << "No" << "\n"; 359 return ; 360 } 361 sort(edges.begin(), edges.end()); 362 dsu.init(n); 363 for (auto [u, v] : edges) { 364 dsu.merge(u, v); 365 tree[u].push_back(v); 366 } 367 int flag = 1; 368 for (int i = 1; i <= n; i++) flag &= (dsu.find(i) == dsu.find(1)); 369 if (!flag) { 370 cout << "No" << "\n"; 371 return ; 372 } 373 for (int i = 1; i <= n; i++) { 374 for (int j = 1; j <= n; j++) reach[j] = 0; 375 search(i); 376 for (int j = 1; j <= n; j++) { 377 if (reach[j] != e[i][j]) { 378 cout << "No" << "\n"; 379 return ; 380 } 381 } 382 } 383 cout<< "Yes\n"; 384 for (auto [u, v] : edges) { 385 cout << u << ' ' << v << '\n'; 386 } 387 } 388 int main() { 389 ios::sync_with_stdio(0), cin.tie(0); 390 int T; 391 cin >> T; 392 for (int i = 1; i <= T; i++) solve(i); 393 return 0; 394 } 395 ``` 396 397 **Rate the problem!** 398 399 good 400 401 mid 402 403 bad 404 405 didn't solve 406 407 [2208E - Counting Cute Arrays](/contest/2208/problem/E "Codeforces Round 1086 (Div. 2)") 408 409 Idea by [tybbs](/profile/tybbs "Expert tybbs") and [Mini_PEKKA](/profile/Mini_PEKKA "Candidate Master Mini_PEKKA"), prepared by [tybbs](/profile/tybbs "Expert tybbs") 410 411 **Hint 1** 412 413 Find a straightforward criterion to determine whether an array is "cute". 414 415 **Answer to Hint 1** 416 417 First, consider a necessary condition: If $X_i \ge i$ for any $i$, the array $X$ cannot be cute. 418 419 It is well-known that the structure of $X$ relates to a **monotonic stack**. We can verify whether an array $X$ of length $n$ is cute using the following simulation procedure: 420 421 1. Maintain a stack $S$, initialized with a single sentinel element $0$. 422 2. Iterate $i$ from $1$ to $n$: 423 * Check if the value $X_i$ exists in $S$. 424 * If $X_i$ is **not** in $S$, then $X$ is not a cute array. 425 * If $X_i$ **is** in $S$, pop elements from $S$ until $X_i$ becomes the top element. Then, push $i$ onto the stack. 426 3. If the loop completes without violating the conditions above, $X$ is a cute array. 427 428 **Hint 2** 429 430 Solve the problem for the following special case: For all $i$, $X_i$ is either $-1$ or $i-1$. 431 432 **Answer to Hint 2** 433 434 We can use dynamic programming to solve this special case. Let $f_{i,k}$ denote the number of ways to fill the $-1$s in the prefix $X_1 \dots X_i$ such that the array remains potentially cute and the current stack size is $k$. 435 436 The transition is straightforward: * If $X_i = -1$, we can pop an arbitrary number of elements. Thus, $f_{i,k} = \sum_{j=k-1}^{i} f_{i-1,j}$. * If $X_i = i-1$, we cannot pop any elements (the previous index must be the nearest greater element). Thus, $f_{i,k} = f_{i-1,k-1}$. 437 438 **Hint 3** 439 440 Analyze the failure condition of the stack procedure further. 441 442 **Answer to Hint 3** 443 444 If $X_i$ is not found in $S$ during the simulation, it implies that $X_i$ was previously popped from the stack while processing some earlier index $j$. This indicates the existence of a pair $(j, i)$ such that $X_j \lt X_i \lt j \lt i$. 445 446 Consequently, an array $X$ is cute if and only if **no** such pair $(j, i)$ exists that satisfies this condition. 447 448 **Solution** 449 450 First, check if all fixed values (where $X_i, X_j \neq -1$) satisfy the condition that no pair $(j, i)$ with $j \lt i$ exists such that $X_j \lt X_i \lt j \lt i$. Additionally, ensure $X_i \lt i$ for all $i$. If these conditions are not met, the answer is $0$. 451 452 Consider each fixed $X_i \neq -1$ as defining an interval $[X_i, i]$. By sorting these intervals by length from smallest to largest, we can process them hierarchically. Once all $X_k$ within a specific interval are determined, the interval effectively behaves like the base case $[i-1, i]$ mentioned in Hint 2. 453 454 This reduction transforms the general problem into the special case solved in Hint 2. We can compute the final answer using the DP approach with prefix sum optimization, resulting in an overall time complexity of $O(n^2)$. 455 456 **Code** 457 458 ``` 459 #include<bits/stdc++.h> 460 using namespace std; 461 const int N=5e3+5,mod=998244353; 462 inline void add(int &x,int v){ x=(x+v)%mod; } 463 int T,n,ans,a[N],id[N],mx[N],f[N],sf[N]; 464 void calc(int l,int r){ 465 int tp=0,cnt=0; 466 f[0]=1,sf[0]=1; 467 while(1){ 468 if(mx[l]==0) l++,tp=0; 469 else l=mx[l],tp=1; 470 if(l>r) break; 471 cnt++; 472 if(tp==0){ 473 for(int i=1;i<=cnt;i++) f[i]=sf[i-1]; 474 f[0]=0; 475 } 476 else{ 477 for(int i=cnt;i>=1;i--) f[i]=f[i-1]; 478 f[0]=0; 479 } 480 sf[cnt+1]=0; 481 for(int i=cnt;i>=0;i--) sf[i]=(sf[i+1]+f[i])%mod; 482 } 483 ans=1ll*ans*sf[0]%mod; 484 } 485 void solve(){ 486 cin>>n; 487 for(int i=0;i<=n;i++) mx[i]=0; 488 for(int i=1;i<=n;i++){ 489 cin>>a[i]; 490 } 491 for(int i=1;i<=n;i++){ 492 if(a[i]>=i) return void(cout<<0<<"\n"); 493 } 494 for(int i=1;i<=n;i++){ 495 for(int j=i+1;j<=n;j++){ 496 if(a[i]!=-1 && a[j]!=-1){ 497 if(a[i]<a[j] && a[j]<i) return void(cout<<0<<"\n"); 498 } 499 } 500 } 501 int cnt=0; 502 for(int i=1;i<=n;i++){ 503 if(a[i]!=-1) id[++cnt]=i; 504 } 505 sort(id+1,id+cnt+1,[](int x,int y){ return x-a[x]<y-a[y]; }); 506 ans=1; 507 for(int i=1;i<=cnt;i++){ 508 calc(a[id[i]],id[i]-1); 509 mx[a[id[i]]]=id[i]; 510 } 511 calc(0,n); 512 cout<<ans<<"\n"; 513 } 514 int main(){ 515 ios::sync_with_stdio(0); 516 cin.tie(0); 517 cin>>T; 518 for(int i=1;i<=T;i++) solve(); 519 } 520 ``` 521 522 **Rate the problem!** 523 524 good 525 526 mid 527 528 bad 529 530 didn't solve