codeforces-scrape

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

2146.md (13462B)


      1 Source: https://codeforces.com/blog/entry/146648
      2 
      3 [2146A - Equal Occurrences](/contest/2146/problem/A "Codeforces Round 1052 (Div. 2)")
      4 
      5 **Hint 1**
      6 
      7 Let's focus on the number of occurrences of each element: let $c_i$ be the number of time that element $i$ occurs in the array. To keep a subsequence is to decrease each $c_i$ by a non-negative integer. We need to make all the non-zero elements in $c$ the same while maximizing the sum of $c$.
      8 
      9 **Hint 2**
     10 
     11 For each integer $x$: suppose the value of all non-zero elements in $c$ is $x$, what is the length of the longest subsequence?
     12 
     13 **Answer**
     14 
     15 For those $c_i \lt x$, we decrease it to $0$; for those $c_i\ge x$, we decrease it to $x$.
     16 
     17 **Tutorial**
     18 
     19 Tutorial is loading...
     20 
     21 **Implementation**
     22 
     23 By [Caylex](/profile/Caylex "Master Caylex").
     24 
     25 ```
     26 def solve():
     27     n = int(input())
     28     ls = list(map(int, input().split()))
     29     a = [0] * n
     30     for x in ls:
     31         a[x - 1] += 1
     32     a = sorted(a)
     33     s = sum(a)
     34     ans = s
     35     for i in range(n):
     36         ans = min(ans, s - (n - i) * a[i])
     37     print(n - ans)
     38     return
     39  
     40  
     41 t = int(input())
     42 for _ in range(t):
     43     solve()
     44 ```
     45 
     46 [2146B - Merging the Sets](/contest/2146/problem/B "Codeforces Round 1052 (Div. 2)")
     47 
     48 **Hint 1**
     49 
     50 How to check if there is at least one way to choose the sets?
     51 
     52 **Answer**
     53 
     54 Obviously, we should choose all the sets.
     55 
     56 **Hint 2**
     57 
     58 How to greedily find two more solutions to choose the sets?
     59 
     60 **Answer**
     61 
     62 We should choose all the sets but one.
     63 
     64 **Tutorial**
     65 
     66 Tutorial is loading...
     67 
     68 **Implementation**
     69 
     70 By [Caylex](/profile/Caylex "Master Caylex").
     71 
     72 ```
     73 def solve():
     74     n, m = map(int, input().split())
     75     cnt = [0] * m
     76     t = 0
     77     v = []
     78     for i in range(n):
     79         v.append([])
     80         inp = list(map(int, input().split()))
     81         l = inp[0]
     82         for j in range(1, l + 1):
     83             x = inp[j]
     84             x -= 1
     85             t += not cnt[x]
     86             cnt[x] += 1
     87             v[i].append(x)
     88     ans = t == m
     89     for i in range(n):
     90         for x in v[i]:
     91             cnt[x] -= 1
     92             t -= not cnt[x]
     93         ans += t == m
     94         for x in v[i]:
     95             t += not cnt[x]
     96             cnt[x] += 1
     97     print("YES" if ans >= 3 else "NO")
     98     return
     99 
    100 t = int(input())
    101 for _ in range(t):
    102     solve()
    103 ```
    104 
    105 [2146C - Wrong Binary Search](/contest/2146/problem/C "Codeforces Round 1052 (Div. 2)")
    106 
    107 **Hint 1**
    108 
    109 How to check if an element $x$ is stable? For an element $p_i$, we only care about whether $p_i \lt x$, $p_i=x$ or $p_i \gt x$.
    110 
    111 **Hint 2**
    112 
    113 If an element is not stable, we can choose $m$ correctly in the first step to exclude $x$ from interval $[l,r]$.
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Implementation**
    120 
    121 By [Caylex](/profile/Caylex "Master Caylex").
    122 
    123 ```
    124 def solve():
    125     n = int(input())
    126     s = str(input())
    127     l = 0
    128     p = []
    129     for i in range(n):
    130         p.append(i + 1)
    131     while l < n:
    132         if s[l] == "1":
    133             l += 1
    134             continue
    135         r = l
    136         while r + 1 < n and s[r + 1] == "0":
    137             r += 1
    138         if r - l + 1 == 1:
    139             print("NO")
    140             return
    141         ok = 1
    142         for i in range(l, r):
    143             p[i] = i + 2
    144         p[r] = l + 1
    145         l = r + 1
    146     print("YES")
    147     for i in range(n):
    148         print(p[i], end=" ")
    149     print()
    150     return
    151 
    152 t = int(input())
    153 for _ in range(t):
    154     solve()
    155 ```
    156 
    157 [2146D1 - Max Sum OR (Easy Version)](/contest/2146/problem/D1 "Codeforces Round 1052 (Div. 2)")
    158 
    159 **Hint 1**
    160 
    161 Try a few cases by hand or guess by the samples, what's the maximized answer for $l=0,r=n$?
    162 
    163 **Answer**
    164 
    165 The answer is $n(n+1)$. Actually, as $x\mid y\le x+y$, so the upper bound for the answer is $\sum (a_i+b_i)=n(n+1)$. And we are going to reach the upper bound.
    166 
    167 **Hint 2**
    168 
    169 We need to make the bitwise AND of $a_i$ and $b_i$ all equal to $0$. Let's remind you that the bitwise AND of $x$ and $2^k-1-x$ is $0$ for $0\le x \lt 2^k$. We can try to pair integers $x$ and $y$ by letting $a_x=y,a_y=x$.
    170 
    171 **Hint 3**
    172 
    173 Construct from the back.
    174 
    175 **Tutorial**
    176 
    177 Tutorial is loading...
    178 
    179 **Implementation**
    180 
    181 By [Caylex](/profile/Caylex "Master Caylex").
    182 
    183 ```
    184 def solve():
    185     l, r = map(int, input().split())
    186     pw = 1
    187     ans = 0
    188     while pw < r:
    189         pw = pw << 1 | 1
    190     s = set()
    191     for i in range(l, r + 1):
    192         s.add(i)
    193     a = [0] * (r + 1)
    194     for i in range(r, l - 1, -1):
    195         while pw - i not in s:
    196             pw >>= 1
    197         a[i] = pw - i
    198         ans += i | a[i]
    199         s.remove(pw - i)
    200     print(ans)
    201     print(*a[l : r + 1])
    202     return
    203 
    204 t = int(input())
    205 for _ in range(t):
    206     solve()
    207 ```
    208 
    209 [2146D2 - Max Sum OR (Hard Version)](/contest/2146/problem/D2 "Codeforces Round 1052 (Div. 2)")
    210 
    211 **Hint 1**
    212 
    213 Let's consider from the highest bits to the lowest bits. If the highest bits of $l$ and $r$ are the same, we can just ignore this bit and go on to a lower bit. We can still try to pair integers $x$ and $y$ by letting $a_x=y,a_y=x$.
    214 
    215 **Hint 2**
    216 
    217 Consider the highest bit that $l$ and $r$ differs. There exist an integer $t$ that this bit of $l\ldots t-1$ are $0$ and this bit of $t\ldots r$ are $1$. We need to pair a $0$ with a $1$ as more as possible while keeping the bitwise AND of lower bits small. Can we turn it into a smaller subproblem?
    218 
    219 **Hint 3**
    220 
    221 In D1, it is optimal to pair $x$ with $2^k-1-x$. Here, for interval $[l,r]$ and integer $t$ defined in Hint2, it is optimal to pair $x$ with $2t-1-x$.
    222 
    223 **Tutorial**
    224 
    225 Tutorial is loading...
    226 
    227 **Implementation**
    228 
    229 By [Caylex](/profile/Caylex "Master Caylex").
    230 
    231 ```
    232 def g(x, j):
    233     return x >> j & 1
    234 
    235 def solve():
    236     L, R = map(int, input().split())
    237     a = [0] * (R - L + 1)
    238 
    239     def solve(l, r, j):
    240         if l > r:
    241             return
    242         if l == r:
    243             a[l - L] = r
    244             return
    245         mid = l
    246         while mid + 1 <= r and g(mid + 1, j) == g(l, j):
    247             mid += 1
    248         if mid == r:
    249             solve(l, r, j - 1)
    250             return
    251         tl = mid + 1
    252         tr = mid
    253         while tl - 1 >= l and tr + 1 <= r:
    254             tl -= 1
    255             tr += 1
    256             a[tl - L] = tr
    257             a[tr - L] = tl
    258         solve(l, tl - 1, j - 1)
    259         solve(tr + 1, r, j - 1)
    260         return
    261 
    262     solve(L, R, 29)
    263     ans = 0
    264     for i in range(L, R + 1):
    265         ans += a[i - L] | i
    266     print(ans)
    267     print(*a)
    268     return
    269 
    270 t = int(input())
    271 for _ in range(t):
    272     solve()
    273 ```
    274 
    275 **Another solution using greedy on trie**
    276 
    277 It turns out that we can solve it greedily from the lowest bit to the highest bit. For each element in $[l,r]$, let's reverse its binary representation and insert it into a 01-trie. Then for each index $i$, we can do `dfs` on the trie while trying to keep every bit different with $i$. Formally, each step we try to go to the opposite side of each bit of $i$, and go on the other side if that subtree is empty.
    278 
    279 We can prove that this gives the same construction with the other method constructing from the higher bits. You can read the implementation for better understanding.
    280 
    281 **Implementation**
    282 
    283 ```
    284 #include<bits/stdc++.h>
    285 using namespace std;
    286 #define int         long long
    287 #define pb          push_back
    288 #define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
    289 int l,r;
    290 int tot;
    291 int son[6000005][2],cnt[6000005];
    292 void Main() {
    293 	cin>>l>>r;
    294 	tot=1;
    295 	son[0][0]=son[0][1]=-1;
    296 	REP(i,l,r+1){
    297 		int x=0;
    298 		REP(j,0,30){
    299 			int &p=son[x][(i>>j)&1];
    300 			if(p==-1)p=tot++,cnt[p]=0,son[p][0]=son[p][1]=-1;
    301 			x=p;++cnt[x];
    302 		}
    303 	}
    304 	int ans=0;
    305 	vector<int>res;
    306 	REP(i,l,r+1){
    307 		int x=0,t=0;
    308 		REP(j,0,30){
    309 			int o=!((i>>j)&1);
    310 			if(son[x][o]==-1||!cnt[son[x][o]])o=!o;
    311 			t|=o<<j;
    312 			x=son[x][o];--cnt[x];
    313 		}
    314 		res.pb(t);ans+=i|t;
    315 	}
    316 	cout<<ans<<'\n';
    317 	for(auto i:res)cout<<i<<' ';
    318 	cout<<'\n';
    319 }
    320 void TC() {
    321     int tc=1;
    322     cin>>tc;
    323 	while(tc--){
    324 		Main();
    325 	}
    326 }
    327 signed main() {
    328 	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
    329 }
    330 /*
    331 1. CLEAR the arrays (ESPECIALLY multitests)
    332 2. DELETE useless output
    333  */
    334 ```
    335 
    336 [2146E - Yet Another MEX Problem](/contest/2146/problem/E "Codeforces Round 1052 (Div. 2)")
    337 
    338 **Hint 1**
    339 
    340 For an array $b$ and an integer $x$ that **does not appear in** $b$, let $g(b,x)$ be the number of elements in $b$ that is greater than $x$. Then the weight of $b$ equals to $g(b,\rm{mex}(b))$. However, when $x\neq \rm{mex}(b)$, what will happen to $g(b,x)$?
    341 
    342 **Answer**
    343 
    344 The value of $g(b,x)$ is always smaller than or equal to $g(b,\rm{mex}(b))$, because when $x$ **does not appear in** $b$, letting $x=\rm{mex}(b)$ is optimal to maximize $g(b,x)$.
    345 
    346 **Hint 2**
    347 
    348 For a fixed right endpoint $r$, let's enumerate over all the $x$ and maximize $g(a[l\dots r],x)$ while keeping $x$ no occurred in $a[l\dots r]$. It's clear that the value is maximized for $x$ if $l$ equals the last occurrence of $x$ plus $1$.
    349 
    350 **Hint 3**
    351 
    352 Use a segment tree to maintain the answer for each $x$.
    353 
    354 **Tutorial**
    355 
    356 Tutorial is loading...
    357 
    358 **Implementation**
    359 
    360 By [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225").
    361 
    362 ```
    363 #include<bits/stdc++.h>
    364 using namespace std;
    365 #define all(v)      v.begin(),v.end()
    366 #define pb          push_back
    367 #define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
    368 int n;
    369 int a[300005];
    370 struct ds{
    371 	int seg[1200005],tag[1200005];
    372 	void build(int l,int r,int p){
    373 		seg[p]=tag[p]=0;
    374 		if(l==r)return;
    375 		int m=(l+r)>>1;
    376 		build(l,m,p*2+1);build(m+1,r,p*2+2);
    377 	}
    378 	void update(int l,int r,int s,int t,int p){
    379 		if(l<=s&&t<=r){
    380 			++seg[p];++tag[p];
    381 			return;
    382 		}
    383 		int m=(s+t)>>1;
    384 		if(m>=l)update(l,r,s,m,p*2+1);
    385 		if(m<r)update(l,r,m+1,t,p*2+2);
    386 		seg[p]=max(seg[p*2+1],seg[p*2+2])+tag[p];
    387 	}
    388 	void point(int pos,int l,int r,int p,int val=0){
    389 		if(l==r)return seg[p]=-val,void();
    390 		int m=(l+r)>>1;
    391 		val+=tag[p];
    392 		if(m>=pos)point(pos,l,m,p*2+1,val);
    393 		else point(pos,m+1,r,p*2+2,val);
    394 		seg[p]=max(seg[p*2+1],seg[p*2+2])+tag[p];
    395 	}
    396 }seg;
    397 void Main() {
    398 	cin>>n;
    399 	REP(i,0,n)cin>>a[i];
    400 	seg.build(0,n,0);
    401 	REP(i,0,n){
    402 		seg.update(0,a[i],0,n,0);
    403 		seg.point(a[i],0,n,0);
    404 		cout<<seg.seg[0]<<' ';
    405 	}
    406 	cout<<'\n';
    407 }
    408 void TC() {
    409     int tc=1;
    410     cin>>tc;
    411 	while(tc--){
    412 		Main();
    413 		cout.flush();
    414 	}
    415 }
    416 signed main() {
    417 	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
    418 }
    419 /*
    420 1. CLEAR the arrays (ESPECIALLY multitests)
    421 2. DELETE useless output
    422  */
    423 ```
    424 
    425 **Bonus**
    426 
    427 There's a harder version of the problem. Can you solve it?
    428 
    429 There're $q$ queries: $x,y$. Find $\max_{x\le l\le r\le y}w(l,r)$. $n,q\le 3\cdot 10^5$.
    430 
    431 [2146F - Bubble Sort](/contest/2146/problem/F "Codeforces Round 1052 (Div. 2)")
    432 
    433 **Hint 1**
    434 
    435 Let's focus on bubble sort first. For an element $p_x$, how many rounds does it take to make all the numbers before the position small than $p_x$?
    436 
    437 **Answer**
    438 
    439 Count the number of integers $i$ such that $i \lt x$ and $p_i \gt p_x$. In one round of bubble sort, exactly one of that sort of element will be moved to the right of $p_x$.
    440 
    441 **Hint 2**
    442 
    443 Try to count something else instead of permutations $p$. Can you come up with an $O(n^2)$ dynamic programming method?
    444 
    445 **Hint 3**
    446 
    447 The number of restrictions is small ($m\le 1000$). Can we decrease the number of states from $O(n^2)$ to $O(nm)$ and $O(m^2)$? How to calculate the coefficients then?
    448 
    449 **Tutorial**
    450 
    451 Tutorial is loading...
    452 
    453 **Implementation**
    454 
    455 By [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225").
    456 
    457 ```
    458 #include<bits/stdc++.h>
    459 using namespace std;
    460 #define MOD         998244353
    461 #define speMOD      2933256077ll
    462 #define int         long long
    463 #define pii         pair<int,int>
    464 #define all(v)      v.begin(),v.end()
    465 #define pb          push_back
    466 #define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
    467 #define over(x)     {cout<<(x)<<endl;return;}
    468 #define lowbit(x)   ((x)&(-(x)))
    469 #define cntbit(x)   __builtin_popcount(x)
    470 #define rf(v)       shuffle(all(v),sd);
    471 #define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
    472 #define lbound(v,x) lower_bound(all(v),x)-v.begin()
    473 int qpow(int a,int b,int m=MOD,int res=1){
    474 	a%=m;
    475 	while(b>0)res=(b&1)?(res*a%m):(res),a=a*a%m,b>>=1;
    476 	return res;
    477 }
    478 int fac[2000005],inv[2000005];
    479 void init(int n){
    480 	fac[0]=inv[0]=1;
    481 	REP(i,1,n+1)fac[i]=fac[i-1]*i%MOD;
    482 	inv[n]=qpow(fac[n],MOD-2);
    483 	for(int i=n-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%MOD;
    484 }
    485 int binom(int x,int y){
    486 	return x<y||y<0? 0:fac[x]*inv[y]%MOD*inv[x-y]%MOD;
    487 }
    488 struct restr{
    489 	int l,r,k;
    490 };
    491 int n,m;
    492 int r1[1000005],r2[1000005];
    493 int dp[10005],sum[10005];
    494 int qry1(int l,int r,int k){
    495 	if(k<l)return qpow(k+1,r-l+1);
    496 	if(k>r)return fac[r+1]*inv[l]%MOD;
    497 	return fac[k+1]*inv[l]%MOD*qpow(k+1,r-k)%MOD;
    498 }
    499 int qry2(int l,int r,int k,int x){
    500 	return (qry1(l,r,k)+MOD-qry1(l,r,x))%MOD;
    501 }
    502 void Main() {
    503 	cin>>n>>m;
    504 	vector<int>v;vector<restr>a;
    505 	vector<int>t;
    506 	REP(i,0,m){
    507 		int k,l,r;
    508 		cin>>k>>l>>r;
    509 		--l;
    510 		if(l>=0)v.pb(l);
    511 		if(r<n)v.pb(r);
    512 		t.pb(k);
    513 		a.pb({l,r,k});
    514 	}
    515 	v.pb(n-1);t.pb(-1);t.pb(n-1);
    516 	deal(v);deal(t);
    517 	for(auto i:v)r1[i]=t.size()-1,r2[i]=0;
    518 	for(auto i:a){
    519 		if(i.k==n-1&&i.r<n-1)over(0)
    520 		if(i.l>=0)r1[i.l]=min(r1[i.l],lbound(t,i.k));
    521 		if(i.r<n)r2[i.r]=max(r2[i.r],lbound(t,i.k));
    522 	}
    523 	int lst=0,m=t.size();dp[1]=1;REP(i,2,m+1)dp[i]=0;
    524 	for(auto i:v){
    525 		REP(j,1,m)sum[j]=dp[j];
    526 		REP(j,2,m)(sum[j]+=sum[j-1])%=MOD;
    527 		REP(j,1,m)if(j>r2[i]&&j<=r1[i]){
    528 			dp[j]=(dp[j]*qry1(lst,i,t[j])+sum[j-1]*qry2(lst,i,t[j],t[j-1]))%MOD;
    529 		}else dp[j]=0;
    530 		lst=i+1;
    531 	}
    532 	int res=0;
    533 	REP(j,1,m+1)(res+=dp[j])%=MOD;
    534 	cout<<res<<endl;
    535 }
    536 void TC() {
    537 	init(1000000);
    538     int tc=1;
    539     cin>>tc;
    540 	while(tc--){
    541 		Main();
    542 		cout.flush();
    543 	}
    544 }
    545 signed main() {
    546 	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
    547 }
    548 /*
    549 1. CLEAR the arrays (ESPECIALLY multitests)
    550 2. DELETE useless output
    551  */
    552 ```