codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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