1902.md (7285B)
1 Source: https://codeforces.com/blog/entry/122951 2 3 [1902A - Binary Imbalance](/contest/1902/problem/A "Educational Codeforces Round 159 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 n = int(input()) 16 s = input() 17 print("NO" if s.count('1') == n else "YES") 18 ``` 19 20 [1902B - Getting Points](/contest/1902/problem/B "Educational Codeforces Round 159 (Rated for Div. 2)") 21 22 Idea: [adedalic](/profile/adedalic "International Master adedalic") 23 24 **Tutorial** 25 26 Tutorial is loading... 27 28 **Solution (adedalic)** 29 30 ``` 31 fun main(args: Array<String>) { 32 repeat(readln().toInt()) { 33 val (n, p, l, t) = readln().split(' ').map { it.toLong() } 34 val cntTasks = (n + 6) / 7 35 36 fun calc(k: Long) = k * l + minOf(2 * k, cntTasks) * t 37 var lf = 0L 38 var rg = n 39 while (rg - lf > 1) { 40 val mid = (lf + rg) / 2 41 if (calc(mid) >= p) 42 rg = mid 43 else 44 lf = mid 45 } 46 println(n - rg) 47 } 48 } 49 ``` 50 51 [1902C - Insert and Equalize](/contest/1902/problem/C "Educational Codeforces Round 159 (Rated for Div. 2)") 52 53 Idea: [Roms](/profile/Roms "Master Roms") и [BledDest](/profile/BledDest "International Grandmaster BledDest") 54 55 **Tutorial** 56 57 Tutorial is loading... 58 59 **Solution (awoo)** 60 61 ``` 62 from math import gcd 63 64 for _ in range(int(input())): 65 n = int(input()) 66 a = list(map(int, input().split())) 67 g = 0 68 for i in range(n - 1): 69 g = gcd(g, a[i + 1] - a[i]) 70 g = max(g, 1) 71 a.sort() 72 j = n - 1 73 res = a[-1] 74 while True: 75 while j >= 0 and a[j] > res: 76 j -= 1 77 if j < 0 or a[j] != res: 78 break 79 res -= g 80 print((a[-1] * (n + 1) - (sum(a) + res)) // g) 81 ``` 82 83 [1902D - Robot Queries](/contest/1902/problem/D "Educational Codeforces Round 159 (Rated for Div. 2)") 84 85 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 86 87 **Tutorial** 88 89 Tutorial is loading... 90 91 **Solution (Neon)** 92 93 ``` 94 #include <bits/stdc++.h> 95 96 using namespace std; 97 98 #define x first 99 #define y second 100 101 using pt = pair<int, int>; 102 103 int main() { 104 ios::sync_with_stdio(false); cin.tie(0); 105 int n, q; 106 cin >> n >> q; 107 string s; 108 cin >> s; 109 vector<pt> pos(n + 1); 110 for (int i = 0; i < n; ++i) { 111 pos[i + 1].x = pos[i].x + (s[i] == 'R') - (s[i] == 'L'); 112 pos[i + 1].y = pos[i].y + (s[i] == 'U') - (s[i] == 'D'); 113 } 114 map<pt, vector<int>> mp; 115 for (int i = 0; i <= n; ++i) mp[pos[i]].push_back(i); 116 auto check = [&](pt p, int l, int r) { 117 if (!mp.count(p)) return false; 118 auto it = lower_bound(mp[p].begin(), mp[p].end(), l); 119 return it != mp[p].end() && *it <= r; 120 }; 121 while (q--) { 122 int x, y, l, r; 123 cin >> x >> y >> l >> r; 124 int nx = pos[r].x + pos[l - 1].x - x, ny = pos[r].y + pos[l - 1].y - y; 125 bool f = check({x, y}, 0, l - 1) 126 | check({nx, ny}, l, r - 1) 127 | check({x, y}, r, n); 128 cout << (f ? "YES" : "NO") << '\n'; 129 } 130 } 131 ``` 132 133 [1902E - Collapsing Strings](/contest/1902/problem/E "Educational Codeforces Round 159 (Rated for Div. 2)") 134 135 Idea: [Roms](/profile/Roms "Master Roms") 136 137 **Tutorial** 138 139 Tutorial is loading... 140 141 **Solution (Roms)** 142 143 ``` 144 #include <bits/stdc++.h> 145 146 using namespace std; 147 148 const int N = int(1e6) + 99; 149 150 int nxt; 151 int to[N][26]; 152 int sum[N]; 153 long long res; 154 155 void add(const string& s) { 156 int v = 0; 157 ++sum[v]; 158 for (auto c : s) { 159 int i = c - 'a'; 160 if (to[v][i] == -1) 161 to[v][i] = nxt++; 162 v = to[v][i]; 163 ++sum[v]; 164 } 165 } 166 167 void upd(const string& s) { 168 int curLen = s.size(); 169 int v = 0; 170 171 for (auto c : s) { 172 int i = c - 'a'; 173 if (to[v][i] == -1) { 174 res += sum[v] * 1LL * curLen; 175 break; 176 } else { 177 int nxtV = to[v][i]; 178 res += (sum[v] - sum[nxtV]) * 1LL * curLen; 179 --curLen; 180 v = nxtV; 181 } 182 } 183 } 184 185 void solve(int n, vector <string> v) { 186 int sumSizes = 0; 187 for (int i = 0; i < n; ++i) 188 sumSizes += v[i].size(); 189 190 nxt = 1; 191 memset(sum, 0, sizeof sum); 192 memset(to, -1, sizeof to); 193 194 for(int i = 0; i < n; ++i) 195 add(v[i]); 196 for (int i = 0; i < n; ++i) { 197 reverse(v[i].begin(), v[i].end()); 198 upd(v[i]); 199 } 200 } 201 202 int main() { 203 ios_base::sync_with_stdio(false); 204 int n; 205 cin >> n; 206 vector <string> v(n); 207 for (int i = 0; i < n; ++i) 208 cin >> v[i]; 209 210 res = 0; 211 solve(n, v); 212 for(int i = 0; i < n; ++i) 213 reverse(v[i].end(), v[i].end()); 214 solve(n, v); 215 216 cout << res << endl; 217 218 return 0; 219 } 220 ``` 221 222 [1902F - Trees and XOR Queries Again](/contest/1902/problem/F "Educational Codeforces Round 159 (Rated for Div. 2)") 223 224 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 225 226 **Tutorial** 227 228 Tutorial is loading... 229 230 **Solution (BledDest)** 231 232 ``` 233 #include<bits/stdc++.h> 234 235 using namespace std; 236 237 const int N = 200043; 238 const int K = 20; 239 240 typedef array<int, K> base; 241 int a[N]; 242 vector<int> g[N]; 243 vector<int> path_up[N]; 244 int tin[N], tout[N]; 245 int T = 0; 246 int fup[N][K]; 247 248 base make_empty() 249 { 250 base b; 251 for(int i = 0; i < K; i++) 252 b[i] = 0; 253 return b; 254 } 255 256 int reduce(const base& b, int x) 257 { 258 for(int i = K - 1; i >= 0; i--) 259 if(x & (1 << i)) 260 x ^= b[i]; 261 return x; 262 } 263 264 bool add(base& b, int x) 265 { 266 x = reduce(b, x); 267 if(x != 0) 268 { 269 for(int i = K - 1; i >= 0; i--) 270 if(x & (1 << i)) 271 { 272 b[i] = x; 273 return true; 274 } 275 } 276 return false; 277 } 278 279 bool check(const base& b, int x) 280 { 281 return reduce(b, x) == 0; 282 } 283 284 vector<int> rebuild_path(const vector<int>& path, int v) 285 { 286 base b = make_empty(); 287 vector<int> ans; 288 if(add(b, a[v])) ans.push_back(v); 289 for(auto x : path) if(add(b, a[x])) ans.push_back(x); 290 return ans; 291 } 292 293 void dfs(int v, int u) 294 { 295 tin[v] = T++; 296 if(u == v) 297 path_up[v] = rebuild_path(vector<int>(0), v); 298 else 299 path_up[v] = rebuild_path(path_up[u], v); 300 fup[v][0] = u; 301 for(int i = 1; i < K; i++) 302 fup[v][i] = fup[fup[v][i - 1]][i - 1]; 303 for(auto y : g[v]) 304 if(y != u) 305 dfs(y, v); 306 tout[v] = T++; 307 } 308 309 bool is_ancestor(int u, int v) 310 { 311 return tin[u] <= tin[v] && tout[u] >= tout[v]; 312 } 313 314 int LCA(int x, int y) 315 { 316 if(is_ancestor(x, y)) return x; 317 for(int i = K - 1; i >= 0; i--) 318 if(!is_ancestor(fup[x][i], y)) 319 x = fup[x][i]; 320 return fup[x][0]; 321 } 322 323 bool query(int x, int y, int k) 324 { 325 base b = make_empty(); 326 int z = LCA(x, y); 327 for(auto v : path_up[x]) 328 if(!is_ancestor(v, y)) 329 add(b, a[v]); 330 for(auto v : path_up[y]) 331 if(!is_ancestor(v, x)) 332 add(b, a[v]); 333 add(b, a[z]); 334 return check(b, k); 335 } 336 337 int main() 338 { 339 int n; 340 scanf("%d", &n); 341 for(int i = 0; i < n; i++) scanf("%d", &a[i]); 342 for(int i = 0; i < n - 1; i++) 343 { 344 int x, y; 345 scanf("%d %d", &x, &y); 346 --x; 347 --y; 348 g[x].push_back(y); 349 g[y].push_back(x); 350 } 351 dfs(0, 0); 352 int q; 353 scanf("%d", &q); 354 for(int i = 0; i < q; i++) 355 { 356 int x, y, k; 357 scanf("%d %d %d", &x, &y, &k); 358 --x; 359 --y; 360 if(query(x, y, k)) puts("YES"); 361 else puts("NO"); 362 } 363 } 364 ```