1680.md (7502B)
1 Source: https://codeforces.com/blog/entry/102852 2 3 [1680A - Minimums and Maximums](/contest/1680/problem/A "Educational Codeforces Round 128 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 l1, r1, l2, r2 = map(int, input().split()) 17 if max(l1, l2) <= min(r1, r2): 18 print(max(l1, l2)) 19 else: 20 print(l1 + l2) 21 ``` 22 23 [1680B - Robots](/contest/1680/problem/B "Educational Codeforces Round 128 (Rated for Div. 2)") 24 25 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 26 27 **Tutorial** 28 29 Tutorial is loading... 30 31 **Solution (BledDest)** 32 33 ``` 34 t = int(input()) 35 for i in range(t): 36 n, m = map(int, input().split()) 37 s = [] 38 for j in range(n): 39 s.append(input()) 40 minx = 10 ** 9 41 miny = 10 ** 9 42 for x in range(n): 43 for y in range(m): 44 if s[x][y] == 'R': 45 minx = min(minx, x) 46 miny = min(miny, y) 47 print('YES' if s[minx][miny] == 'R' else 'NO') 48 ``` 49 50 [1680C - Binary String](/contest/1680/problem/C "Educational Codeforces Round 128 (Rated for Div. 2)") 51 52 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 53 54 **Tutorial** 55 56 Tutorial is loading... 57 58 **Solution (BledDest)** 59 60 ``` 61 def can(pos, m): 62 k = len(pos) 63 x = k - m 64 for i in range(m + 1): 65 l = pos[i] 66 r = pos[i + x - 1] 67 if r - l + 1 - x <= m: 68 return True 69 return False 70 71 t = int(input()) 72 for i in range(t): 73 s = input() 74 pos = [] 75 n = len(s) 76 for i in range(n): 77 if s[i] == '1': 78 pos.append(i) 79 lf = 0 80 rg = len(pos) 81 while rg - lf > 1: 82 mid = (lf + rg) // 2 83 if can(pos, mid): 84 rg = mid 85 else: 86 lf = mid 87 if len(pos) == 0 or pos[-1] - pos[0] == len(pos) - 1: 88 print(0) 89 else: 90 print(rg) 91 ``` 92 93 [1680D - Dog Walking](/contest/1680/problem/D "Educational Codeforces Round 128 (Rated for Div. 2)") 94 95 Idea: [vovuh](/profile/vovuh "Master vovuh") and [BledDest](/profile/BledDest "International Grandmaster BledDest") 96 97 **Tutorial** 98 99 Tutorial is loading... 100 101 **Solution (vovuh)** 102 103 ``` 104 #include <bits/stdc++.h> 105 106 using namespace std; 107 108 int main() { 109 #ifdef _DEBUG 110 freopen("input.txt", "r", stdin); 111 // freopen("output.txt", "w", stdout); 112 #endif 113 114 int n; 115 long long k; 116 cin >> n >> k; 117 vector<long long> a(n); 118 for (auto &it : a) { 119 cin >> it; 120 } 121 122 long long ans = 0; 123 for (int it = 0; it < n; ++it) { 124 vector<int> cnt(n); 125 for (int i = n - 1; i >= 0; --i) { 126 cnt[i] = (a[i] == 0); 127 if (i + 1 < n) { 128 cnt[i] += cnt[i + 1]; 129 } 130 } 131 vector<long long> b = a; 132 long long s = accumulate(b.begin(), b.end(), 0ll); 133 bool ok = true; 134 for (int i = 0; i < n; ++i) { 135 if (b[i] == 0) { 136 long long x = (i + 1 < n ? cnt[i + 1] : 0); 137 b[i] = min(k, x * k - s); 138 if (b[i] < -k) { 139 ok = false; 140 } 141 s += b[i]; 142 } 143 } 144 if (ok) { 145 long long pos = 0, mn = 0, mx = 0; 146 for (int i = 0; i < n; ++i) { 147 pos += b[i]; 148 mn = min(mn, pos); 149 mx = max(mx, pos); 150 } 151 if (pos == 0) { 152 ans = max(ans, mx - mn + 1); 153 } 154 } 155 rotate(a.begin(), a.begin() + 1, a.end()); 156 } 157 158 if (ans == 0) { 159 ans = -1; 160 } 161 162 cout << ans << endl; 163 164 return 0; 165 } 166 ``` 167 168 [1680E - Moving Chips](/contest/1680/problem/E "Educational Codeforces Round 128 (Rated for Div. 2)") 169 170 Idea: [vovuh](/profile/vovuh "Master vovuh") 171 172 **Tutorial** 173 174 Tutorial is loading... 175 176 **Solution (vovuh)** 177 178 ``` 179 #include <bits/stdc++.h> 180 181 using namespace std; 182 183 const int INF = 1e9; 184 185 int main() { 186 #ifdef _DEBUG 187 freopen("input.txt", "r", stdin); 188 // freopen("output.txt", "w", stdout); 189 #endif 190 191 int tc; 192 cin >> tc; 193 while (tc--) { 194 int n; 195 string s[2]; 196 cin >> n >> s[0] >> s[1]; 197 198 for (int it = 0; it < 2; ++it) { 199 while (s[0].back() == '.' && s[1].back() == '.') { 200 s[0].pop_back(); 201 s[1].pop_back(); 202 } 203 reverse(s[0].begin(), s[0].end()); 204 reverse(s[1].begin(), s[1].end()); 205 } 206 n = s[0].size(); 207 208 vector<vector<int>> cost(n, vector<int>(2)); 209 for (int i = 0; i < n; ++i) { 210 for (int j = 0; j < 2; ++j) { 211 cost[i][j] = (s[j][i] == '*'); 212 } 213 } 214 215 vector<vector<int>> dp(n, vector<int>(2, INF)); 216 dp[0][0] = cost[0][1]; 217 dp[0][1] = cost[0][0]; 218 for (int i = 0; i + 1 < n; ++i) { 219 dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + 1 + cost[i + 1][1]); 220 dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + 2); 221 dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1 + cost[i + 1][0]); 222 dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + 2); 223 } 224 225 cout << min(dp[n - 1][0], dp[n - 1][1]) << endl; 226 } 227 228 return 0; 229 } 230 ``` 231 232 [1680F - Lenient Vertex Cover](/contest/1680/problem/F "Educational Codeforces Round 128 (Rated for Div. 2)") 233 234 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 235 236 **Tutorial** 237 238 Tutorial is loading... 239 240 **Solution (awoo)** 241 242 ``` 243 #include <bits/stdc++.h> 244 245 #define forn(i, n) for (int i = 0; i < int(n); i++) 246 247 using namespace std; 248 249 vector<vector<int>> g, h; 250 vector<int> tin, tout, clr; 251 vector<vector<int>> sum(2); 252 int T; 253 254 int flip; 255 int cnt; 256 257 bool isp(int v, int u){ 258 return tin[v] <= tin[u] && tout[v] >= tout[u]; 259 } 260 261 void init(int v){ 262 tin[v] = T++; 263 for (int u : g[v]){ 264 if (clr[u] == -1){ 265 clr[u] = clr[v] ^ 1; 266 h[v].push_back(u); 267 init(u); 268 } 269 else if (tin[u] < tin[v]){ 270 int dif = clr[v] ^ clr[u]; 271 if (!dif){ 272 flip = clr[v] ^ 1; 273 ++cnt; 274 } 275 --sum[dif][u]; 276 ++sum[dif][v]; 277 } 278 } 279 tout[v] = T; 280 } 281 282 int sv; 283 284 void dfs(int v){ 285 for (int u : h[v]){ 286 dfs(u); 287 if (sum[0][u] == cnt && sum[1][u] == 1){ 288 sv = u; 289 flip = clr[v] ^ 1; 290 } 291 forn(i, 2) sum[i][v] += sum[i][u]; 292 } 293 } 294 295 int main() { 296 cin.tie(0); 297 iostream::sync_with_stdio(false); 298 int t; 299 cin >> t; 300 forn(_, t){ 301 int n, m; 302 cin >> n >> m; 303 g.assign(n, vector<int>()); 304 h.assign(n, vector<int>()); 305 forn(i, m){ 306 int v, u; 307 cin >> v >> u; 308 --v, --u; 309 g[v].push_back(u); 310 g[u].push_back(v); 311 } 312 tin.resize(n); 313 tout.resize(n); 314 forn(i, 2) sum[i].assign(n, 0); 315 clr.assign(n, -1); 316 cnt = 0; 317 T = 0; 318 clr[0] = 0; 319 init(0); 320 if (cnt <= 1){ 321 cout << "YES\n"; 322 forn(v, n) cout << (clr[v] ^ flip); 323 cout << "\n"; 324 continue; 325 } 326 sv = -1; 327 dfs(0); 328 if (sv == -1){ 329 cout << "NO\n"; 330 } 331 else{ 332 cout << "YES\n"; 333 forn(v, n) cout << (clr[v] ^ isp(sv, v) ^ flip); 334 cout << "\n"; 335 } 336 } 337 return 0; 338 } 339 ```