578.md (12872B)
1 Source: https://codeforces.com/blog/entry/20368 2 3 ## [Problm 1 : Raising Bacteria](//codeforces.com/problemset/problem/579/A) 4 5 Write down *x* into its binary form. If the *i**th* least significant bit is 1 and *x* contains *n* bits, we put one bacteria into this box in the morning of (*n* + 1 - *i*)*th* day. Then at the noon of the *n**th* day, the box will contain *x* bacteria. So the answer is the number of ones in the binary form of *x*. 6 7 [code of author's friend: this](//codeforces.com/contest/579/submission/13053439) 8 9 ## [Problem 2 : Finding Team Member](//codeforces.com/problemset/problem/579/B) 10 11 Sort all possible combinations from high strength to low strength. Then iterator all combinations. If two people in a combination still are not contained in any team. then we make these two people as a team. 12 13 [author's code: this](//codeforces.com/contest/579/submission/13053526) 14 15 ## [Problem 3 : A Problem about Polyline](//codeforces.com/problemset/problem/578/A) 16 17 If point (*a*,*b*) is located on the up slope/ down slope of this polyline. Then the polyline will pass the point (*a* - *b*,0)/(*a* + *b*,0).(we call (*a* - *b*) or (*a* + *b*) as *c* afterwards) And we can derive that *c* / (2 * *x*) should be a positive integer. Another condition we need to satisfy is that *x* must be larger than or equal to *b*. It’s easy to show that when those two conditions are satisfied, then the polyline will pass the point (*a*,*b*). 18 19 Formally speaking in math : Let *c* / (2 * *x*) = *y* Then we have *x* = *c* / (2 * *y*) ≥ *b* and we want to find the maximum integer *y*. After some more math derivation, we can get the answer is . Besides, the only case of no solution is when *a* < *b*. 20 21 In fact,  always dosn't exist or larger than . 22 23 author's code: 24 25 ``` 26 #include <bits/stdc++.h> 27 typedef long long LL; 28 using namespace std; 29 int main(){ 30 LL a,b; 31 cin>>a>>b; 32 if(a<b)puts("-1"); 33 else printf("%.12f\n",(a+b)/(2.*((a+b)/(2*b)))); 34 return 0; 35 } 36 ``` 37 38 ## [Problem 4 : Or Game](//codeforces.com/problemset/problem/578/B) 39 40 We can describe a strategy as multiplying *a**i* by *x* *t**i* times so *a**i* will become *b**i* = *a**i* * *x**t**i* and sum of all *t**i* will be equals to *k*. The fact is there must be a *t**i* equal to *k* and all other *t**i* equals to 0. If not, we can choose the largest number *b**j* in sequence *b*, and change the strategy so that *t**j* = *k* and all other *t**j* = 0. The change will make the highest bit 1 of *b**j* become higher so the *or*-ed result would be higher. 41 42 After knowing the fact, We can iterator all number in sequence a and multiply it by *x**k* and find the maximum value of our target between them. There are several method to do it in lower time complexity. You can check the sample code we provide.(I believe you can understand it quickly.) 43 44 author's code: 45 46 ``` 47 #include<cstdio> 48 #include<algorithm> 49 using namespace std; 50 const int SIZE = 2e5+2; 51 long long a[SIZE],prefix[SIZE],suffix[SIZE]; 52 int main(){ 53 int n,k,x; 54 scanf("%d%d%d", &n, &k, &x); 55 long long mul=1; 56 while(k--) 57 mul *= x; 58 for(int i = 1; i <= n; i++) 59 scanf("%I64d", &a[i]); 60 for(int i = 1; i <= n; i++) 61 prefix[i] = prefix[i-1] | a[i]; 62 for(int i = n; i > 0; i--) 63 suffix[i] = suffix[i+1] | a[i]; 64 long long ans = 0; 65 for(int i= 1; i <= n; i++) 66 ans = max(ans, prefix[i-1] | (a[i] * mul) | suffix[i+1]); 67 printf("%I64d\n",ans); 68 } 69 ``` 70 71 ## [Problem 5 : Weakness and Poorness](//codeforces.com/problemset/problem/578/C) 72 73 Let , we can write down the definition of poorness formally as 74 75  76 77 . It's easy to see that *A* is a strictly decreasing function of *x*, and *B* is a strictly increasing function of x. Thus the minimum of *max*(*A*, *B*) can be found using binary or ternary search. The time complexity is , 78 79 Now here give people geometry viewpoint of this problem: 80 81 let  82 83 We plot *n* + 1 straight line *y* = *i* * *x* + *b**i* in the plane for *i* from 0 to *n*. 84 85 We can discover when you are given *x*. The **weakness** will be (y coordinator of highest line at x) — (y coordinator of lowest line at x). 86 87 So we only need to consider the upper convex hull and the lower convex hull of all lines. And the target x value will be one of the intersection of these convex hull. 88 89 Because you can get these line in order of their slope value. we can use stack to get the convex hulls in O(n). 90 91 [author's code : this (using binary search)](//codeforces.com/contest/578/submission/13053708) 92 93 [code of author's friend (using stack to handle convexhull with O(n), have more precision)](//codeforces.com/contest/578/submission/13053614) 94 95 ## [Problem 6 : LCS again](//codeforces.com/problemset/problem/578/D) 96 97 Followings are solution in short. Considering the LCS dp table *lcs*[*x*][*y*] which denotes the LCS value of first *x* characters of *S* and first *y* characters of *T*. If we know *lcs*[*n*][*n*] = *n* - 1, then we only concern values in the table which *abs*(*x* - *y*) ≤ 1 and all value of *lcs*[*x*][*y*] must be *min*(*x*, *y*) or *min*(*x*, *y*) - 1. So each row contains only 8 states(In fact,three states among these states will never be used), we can do dp on it row by row with time complexity *O*(*n*). 98 99 There is another not dp method. [You can refer this comment.](//codeforces.com/blog/entry/20368#comment-251453) 100 101 author's code: 102 103 ``` 104 #include <bits/stdc++.h> 105 #define SZ(X) ((int)(X).size()) 106 #define ALL(X) (X).begin(), (X).end() 107 #define REP(I, N) for (int I = 0; I < (N); ++I) 108 #define REPP(I, A, B) for (int I = (A); I < (B); ++I) 109 #define RI(X) scanf("%d", &(X)) 110 #define RII(X, Y) scanf("%d%d", &(X), &(Y)) 111 #define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z)) 112 #define DRI(X) int (X); scanf("%d", &X) 113 #define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y) 114 #define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z) 115 #define RS(X) scanf("%s", (X)) 116 #define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0) 117 #define MP make_pair 118 #define PB push_back 119 #define MS0(X) memset((X), 0, sizeof((X))) 120 #define MS1(X) memset((X), -1, sizeof((X))) 121 #define LEN(X) strlen(X) 122 #define PII pair<int,int> 123 #define VPII vector<pair<int,int> > 124 #define PLL pair<long long,long long> 125 #define F first 126 #define S second 127 typedef long long LL; 128 using namespace std; 129 const int MOD = 1e9+7; 130 const int SIZE = 1e5+10; 131 // template end here 132 LL dp[SIZE][8]; 133 char s[SIZE]; 134 int get_bit(int x,int v){return (x>>v)&1;} 135 int main(){ 136 DRII(n,m); 137 RS(s+1); 138 REPP(i,1,n+1)s[i]-='a'; 139 s[n+1]=-1; 140 REP(i,m){ 141 int state=1; 142 if(i==s[1])state|=2; 143 if(i==s[1]||i==s[2])state|=4; 144 dp[1][state]++; 145 } 146 REPP(i,2,n+1){ 147 REP(j,8){ 148 int d[4]={i-3+get_bit(j,0),i-2+get_bit(j,1),i-2+get_bit(j,2)}; 149 REP(k,m){ 150 int d2[4]={}; 151 REPP(l,1,4){ 152 if(s[i-2+l]==k)d2[l]=d[l-1]+1; 153 else d2[l]=max(d2[l-1],d[l]); 154 } 155 if(d2[1]>=i-2&&min(d2[2],d2[3])>=i-1)dp[i][(d2[1]-(i-2))|((d2[2]-(i-1))<<1)|((d2[3]-(i-1))<<2)]+=dp[i-1][j]; 156 } 157 } 158 } 159 printf("%lld\n",dp[n][0]+dp[n][1]+dp[n][4]+dp[n][5]); 160 return 0; 161 } 162 ``` 163 164 ## [Problem 7 : Walking!](//codeforces.com/problemset/problem/578/E) 165 166 Since there is only one person, it’s not hard to show the difference between the number of left footprints and the number of right footprints is at most one. 167 168 For a particular possible time order of a sequence of footprints, if there are *k* backward steps, we can easily divide all footprints into at most *k* + 1 subsequences without backward steps. Then you might guess that another direction of the induction is also true.That is, we can combine any *k* + 1 subsequence without backward steps into a whole sequence contains at most *k* backward steps. Your guess is correct ! 169 170 Now we demostrate the process of combining those subsequences. 171 172 We only concern the first step and the last step of a divided subsequence. There are four possible combinations, we denote them as *LL*/*LR*/*RL*/*RR* subsequence separately(the first character is the type of the first step and the second character is the type of the second step). 173 174 Suppose the number of four types of subseueqnce(*LL*/*LR*/*RL*/*RR*) are *A*, *B*, *C*, *D* separately. We have *abs*(*A* - *D*) ≤ 1. 175 176 We can combine all *RR*, *LL* subsequeces in turn into one subsequenceswith at most *A* + *D* - 1 backward steps(the result may be of any of the four subsquence types). Now we have at most one *LL* or *RR* type subsequence. 177 178 Then we can combine all *RL* subsequence into only one *RL* subsequence with at most *A* - 1 backward steps easily. And so do *LR* subsequences. Now we want to combine the final *RL* and *LR* subsequences together. We could pick the last footprint among two subsequences, exclude it from the original subsequcne and append it at the tail of another subsequence. The move will not increase the number of backward step and the types of the two subsequences would become *RR* and *LL* ! We can easily combine them into one *LR* or *RL* subsequence now. If there is still a *LL* or *RR* type subsequence reamained. We can easily combine them, too. 179 180 So if we can divide all footprints into the least number of subsequences without backward steps. Then we have solved the problem. And this part can be done with greedy method. 181 182 Now we provide one possible greedy method: 183 184 Firstly, we translate this problem to a maximum matching problem on bipartite graph as following: 185 186 Take "RLLRRL" as example: 187 188   189 190 We split each footprint into two vertices which on is in left part and another is in right part. 191 192 If two footprints is next to each other in resulted subsequnces, we will connect the left vertex of the former to right vertex of the latter in the corresponded matching. So the matching described in above left graph is subsequences: "RL-R--" and "--L-RL" and in above right graph is "RL-R-L" and "--L-R-". we can find that the number of subsequences is (number of footprints) — (value of matching). 193 194 Due to the graphs produced by this problem is very special, we can solve this bipartite matching as following: 195 196 Iterate each vertex in left part from top to bottom and find the uppermost vertex which is able to be matched in right part and connect them. 197 198 If we process this algorithm in "RLLRRL", the resulted matching is the above right graph. 199 200 Why the greedy method is correct? we can prove it by adjusting any maximum matching to our intended matching step by step. In each step, you can find the uppermost vertex the state of which is different to what we intend and change its state. I guess the mission of adjusting is not too hard for you to think out! Please solve it by yourself >_< 201 202 By the way, I believe there are also many other greedy methods will work. If your greedy method is different to author's. Don't feel strange. 203 204 [author's code: this](//codeforces.com/contest/578/submission/13053747) 205 206 ## [Problem 8 : The Mirror Box](//codeforces.com/problemset/problem/578/F) 207 208 If we view the grid intersections alternatively colored by blue and red like this: 209 210  211 212 Then we know that the two conditions in the description are equivalent to a spanning tree in either entire red intersections or entire blue dots. So we can consider a red spanning tree and blue spanning tree one at a time. 213 214 We can use disjoint-sets to merge connected components. Each component should be a tree, otherwise some grid edges will be enclosed inside some mirrors. So for the contracted graph, we would like to know how many spanning trees are there. This can be done by [Kirchhoff’s theorem](https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem). 215 216 Since there are at most 200 broken mirrors, the number of vertices in the contracted graph should be no more than 401. Hence a *O*(|*V*|3) determinant calculation algorithm may be applied onto the matrix. 217 218 [author's code: this](//codeforces.com/contest/578/submission/13053777)