710.md (11148B)
1 Source: https://codeforces.com/blog/entry/46761 2 3 ### [710A - King Moves](/contest/710/problem/A "Educational Codeforces Round 16") 4 5 Easy to see that there are only three cases in this problem. If the king is in the corner of the board the answer is 3. If the king is on the border of the board but not in a corner then the answer is 5. Otherwise the answer is 8. 6 7 **С++ solution** 8 9 ``` 10 char c, d; 11 12 bool read() { 13 return !!(cin >> c >> d); 14 } 15 16 void solve() { 17 int cnt = 0; 18 if (c == 'a' || c == 'h') cnt++; 19 if (d == '1' || d == '8') cnt++; 20 if (cnt == 0) puts("8"); 21 else if (cnt == 1) puts("5"); 22 else if (cnt == 2) puts("3"); 23 else throw; 24 } 25 ``` 26 27 Complexity: *O*(1). 28 29 ### [710B - Optimal Point on a Line](/contest/710/problem/B "Educational Codeforces Round 16") 30 31 The function of the total distance is monotonic between any pair of adjacent points from the input, so the answer is always in some of the given points. We can use that observation to solve the problem by calculating the total distance for each point from the input and finding the optimal point. 32 33 The other solution uses the observation that the answer is always is the middle point (by index) in the sorted list of the given points. The last fact is also can be easily proven. 34 35 **C++ solution** 36 37 ``` 38 const int N = 300300; 39 40 int n, a[N]; 41 42 bool read() { 43 if (!(cin >> n)) return false; 44 forn(i, n) assert(scanf("%d", &a[i]) == 1); 45 return true; 46 } 47 48 void solve() { 49 sort(a, a + n); 50 51 li suml = 0, sumr = accumulate(a, a + n, 0ll); 52 li ansv = LLONG_MAX, ansp = LLONG_MIN; 53 forn(i, n) { 54 li curv = li(i) * a[i] - suml; 55 curv += sumr - li(n - i) * a[i]; 56 if (ansv > curv) { 57 ansv = curv; 58 ansp = a[i]; 59 } 60 suml += a[i]; 61 sumr -= a[i]; 62 } 63 assert(sumr == 0); 64 65 assert(ansv != LLONG_MAX); 66 cerr << "ansv: " << ansv << endl; 67 cout << ansp << endl; 68 } 69 ``` 70 71 Complexity: *O*(*nlogn*). 72 73 ### [710C - Magic Odd Square](/contest/710/problem/C "Educational Codeforces Round 16") 74 75 The problem was suggested by Resul Hangeldiyev [Resul](/profile/Resul "Expert Resul"). 76 77 The solution can be got from the second sample testcase. Easy to see that if we place all odd numbers in the center in form of rhombus we will get a magic square. 78 79 **C++ solution** 80 81 ``` 82 int n; 83 84 bool read() { 85 return !!(cin >> n); 86 } 87 88 const int N = 101; 89 90 int a[N][N]; 91 92 void solve() { 93 memset(a, 0, sizeof(a)); 94 95 forn(i, n / 2) { 96 int len = n / 2 - i; 97 forn(j, len) { 98 int x1 = i, x2 = n - 1 - i; 99 int y1 = j, y2 = n - 1 - j; 100 a[x1][y1] = 1; 101 a[x1][y2] = 1; 102 a[x2][y1] = 1; 103 a[x2][y2] = 1; 104 } 105 } 106 107 int odd = 1, even = 2; 108 forn(i, n) 109 forn(j, n) 110 if (a[i][j]) a[i][j] = even, even += 2; 111 else a[i][j] = odd, odd += 2; 112 113 forn(i, n) { 114 forn(j, n) { 115 if (j) putchar(' '); 116 printf("%d", a[i][j]); 117 } 118 puts(""); 119 } 120 } 121 ``` 122 123 Complexity: *O*(*n*2). 124 125 ### [710D - Two Arithmetic Progressions](/contest/710/problem/D "Educational Codeforces Round 16") 126 127 I wanted to give this problem a lot of time ago. I thought it is very standard problem, but I underestimated its difficulty. 128 129 Let's write down the equation describing the problem: *a*1*k* + *b*1 = *a*2*l* + *b*2 → *a*1*k* - *a*2*l* = *b*2 - *b*1. So we have linear Diofant equation with two variables: *Ax* + *By* = *C*, *A* = *a*1, *B* = - *a*2, *C* = *b*2 - *b*1. The solution has the form: , where the last equation can be solved by extended Euclid algorithm and *p* is any integral number. The variable *p* should satisfy two conditions:  and . The values *A* and *B* are fixed, so we can get the segment of possible values for the values *p*. The length of the segment is the answer for the problem. 130 131 **C++ solution** 132 133 ``` 134 li a1, b1, a2, b2, l, r; 135 136 bool read() { 137 return !!(cin >> a1 >> b1 >> a2 >> b2 >> l >> r); 138 } 139 140 li _ceil(li, li); 141 li _floor(li a, li b) { return b < 0 ? _floor(-a, -b) : a < 0 ? -_ceil(-a, b) : a / b; } 142 li _ceil(li a, li b) { return b < 0 ? _ceil(-a, -b) : a < 0 ? -_floor(-a, b) : (a + b - 1) / b; } 143 144 li gcd(li a, li b, li& x, li& y) { 145 if (!a) { 146 x = 0, y = 1; 147 return b; 148 } 149 li xx, yy, g = gcd(b % a, a, xx, yy); 150 x = yy - b / a * xx; 151 y = xx; 152 return g; 153 } 154 155 void solve() { 156 l = max(0ll, _ceil(l - b1, a1)); 157 r = _floor(r - b1, a1); 158 if (l > r) { 159 puts("0"); 160 return; 161 } 162 163 li A = a1, B = -a2, C = b2 - b1; 164 li x0, y0; 165 li g = gcd(A, B, x0, y0); 166 if (C % g) { 167 puts("0"); 168 return; 169 } 170 171 if (g < 0) { 172 g = -g; 173 x0 = -x0; 174 y0 = -y0; 175 } 176 177 li L = _ceil(r * g - x0 * C, B); 178 li R = _floor(l * g - x0 * C, B); 179 R = min(R, _floor(y0 * C, A)); 180 181 li ans = max(0ll, R - L + 1); 182 cout << ans << endl; 183 } 184 ``` 185 186 Complexity: *O*(*log*(*max*(*a*1, *a*2))). 187 188 ### [710E - Generate a String](/contest/710/problem/E "Educational Codeforces Round 16") 189 190 The problem was suggested by Zi Song Yeoh [zscoder](/profile/zscoder "Candidate Master zscoder"). 191 192 This problem has a simple solution described by participants in the comments. 193 194 My solution is a little harder. Let's solve it using dynamic programming. Let *z**n* be the smallest amount of time needed to get *n* letters 'a'. Let's consider transitions: the transition for adding one letter 'a' can be simply done. Let's process transitions for multiplying by two and subtraction by one simultaneously: let's decrease the number 2·*i* *i* times by one right after getting it. Easy to see that such updates never include each other, so we can store them in queue by adding the new update at the tail of the queue and taking the best update from the head. 195 196 The solution is hard to describe, but it is very simple in the code, so please check it to understand the idea :-) 197 198 **C++ solution** 199 200 ``` 201 int n; 202 li x, y; 203 204 bool read() { 205 return !!(cin >> n >> x >> y); 206 } 207 208 const int N = 20 * 1000 * 1000 + 13; 209 210 li z[N]; 211 212 void solve() { 213 forn(i, N) z[i] = LLONG_MAX; 214 215 list<pair<li, int>> q; 216 217 z[0] = 0; 218 forn(i, n + 1) { 219 while (!q.empty() && q.front().y < i) q.pop_front(); 220 221 if (!q.empty()) z[i] = min(z[i], q.front().x - i * x); 222 assert(z[i] != LLONG_MAX); 223 224 pair<li, int> cur(z[i] + y + 2 * i * x, 2 * i); 225 while (!q.empty() && q.back().x > cur.x) q.pop_back(); 226 q.pb(cur); 227 228 z[i + 1] = min(z[i + 1], z[i] + x); 229 } 230 231 cout << z[n] << endl; 232 } 233 ``` 234 235 Complexity: *O*(*n*). 236 237 ### [710F - String Set Queries](/contest/710/problem/F "Educational Codeforces Round 16") 238 239 The problem was suggested by Alexandr Kulkov [adamant](/profile/adamant "Master adamant"). 240 241 Let's get rid of the queries for deleting a string. There are no strings that will be added two times, so we can calculate the answer for the added (but not deleted strings) and for the deleted separately and subtract the second from the first to get the answer. So we can consider that there are no queries of deletion. 242 243 Now let's use Aho-Corasik algorithm. The only difficulty is that the strings are adding in online mode, but Aho-Corasik algorithm works only after adding all the strings. Note that the answer for the given set of strings equal to the answer for any part of the set plus the answer for the remaining part. Let's use the trick with converting the static data structure (Aho-Corasik in this case) to the dynamic one. 244 245 For the set of *n* strings let's maintain a set of no more than *logn* sets of the strings with sizes of different powers of two. After adding new string we should move the sets from the lowest powers of two to the largest until we got an invariant set of sets. 246 247 Easy to see that each string will be moved no more than *logm* times, so we can process each query in *O*(*logn*) time. 248 249 **C++ solution** 250 251 ``` 252 const int N = 4 * 300300, A = 26, LOGN = 20; 253 254 struct node { 255 char c; 256 int parent, link, output; 257 int next[A], automata[A]; 258 int cnt; 259 260 node(char c = -1, int parent = -1, int link = -1, int output = -1, int cnt = -1): 261 c(c), parent(parent), link(link), output(output), cnt(cnt) { 262 memset(next, -1, sizeof(next)); 263 memset(automata, -1, sizeof(automata)); 264 } 265 }; 266 node t[N]; 267 268 vector<int> ids; 269 inline int get_idx() { 270 assert(!ids.empty()); 271 int ans = ids.back(); 272 ids.pop_back(); 273 t[ans] = node(); 274 return ans; 275 } 276 inline void return_idx(int idx) { 277 ids.pb(idx); 278 } 279 280 inline int add(const string& s, int root) { 281 int v = root; 282 forn(i, sz(s)) { 283 if (t[v].next[s[i] - 'a'] == -1) { 284 int idx = get_idx(); 285 t[v].next[s[i] - 'a'] = idx; 286 t[idx] = node(s[i], v, -1, -1); 287 } 288 v = t[v].next[s[i] - 'a']; 289 } 290 t[v].output = v; 291 return v; 292 } 293 int link(int v, int root) { 294 int& ans = t[v].link; 295 if (ans != -1) return ans; 296 if (v == root || t[v].parent == root) return ans = root; 297 char c = t[v].c; 298 int vv = link(t[v].parent, root); 299 while (vv != root && t[vv].next[c - 'a'] == -1) 300 vv = link(vv, root); 301 return ans = (t[vv].next[c - 'a'] == -1? root: t[vv].next[c - 'a']); 302 } 303 int output(int v, int root) { 304 int& ans = t[v].output; 305 if (ans != -1) return ans; 306 return ans = (v == root? root: output(link(v, root), root)); 307 } 308 int cnt(int v, int root) { 309 int& ans = t[v].cnt; 310 if (ans != -1) return ans; 311 v = output(v, root); 312 if (v == root) return ans = 0; 313 return ans = 1 + cnt(link(v, root), root); 314 } 315 int next(int v, char c, int root) { 316 int& ans = t[v].automata[c - 'a']; 317 if (ans != -1) return ans; 318 if (t[v].next[c - 'a'] != -1) 319 return ans = t[v].next[c - 'a']; 320 return ans = (v == root? root: next(link(v, root), c, root)); 321 } 322 323 void dfs_clear(int v) { 324 forn(i, A) if (t[v].next[i] != -1) dfs_clear(t[v].next[i]); 325 return_idx(v); 326 } 327 328 string a[N]; 329 330 int build(int root, const vector<int>& ids) { 331 dfs_clear(root); 332 root = get_idx(); 333 forn(i, sz(ids)) add(a[ids[i]], root); 334 return root; 335 } 336 337 int calc(int root, int idx) { 338 int ans = 0; 339 const string& s = a[idx]; 340 int v = root; 341 forn(i, sz(s)) { 342 v = next(v, s[i], root); 343 ans += cnt(v, root); 344 } 345 return ans; 346 } 347 348 int m; 349 350 bool read() { 351 return !!(cin >> m); 352 } 353 354 struct blocks { 355 int root[LOGN]; 356 vector<int> block[LOGN]; 357 358 void clear() { 359 forn(i, LOGN) { 360 block[i].clear(); 361 root[i] = get_idx(); 362 } 363 } 364 365 void insert(int i) { 366 vector<int> cur(1, i); 367 forn(i, LOGN) 368 if (sz(block[i]) == sz(cur)) { 369 cur.insert(cur.end(), all(block[i])); 370 block[i].clear(); 371 root[i] = build(root[i], block[i]); 372 } else { 373 block[i] = cur; 374 root[i] = build(root[i], block[i]); 375 break; 376 } 377 } 378 379 li calc2(int idx) { 380 li ans = 0; 381 forn(i, LOGN) { 382 ans += calc(root[i], idx); 383 } 384 return ans; 385 } 386 }; 387 388 char buf[N]; 389 blocks z1, z2; 390 391 void solve() { 392 ids.clear(); 393 nfor(i, N) ids.pb(i); 394 395 z1.clear(); 396 z2.clear(); 397 398 forn(i, m) { 399 int type; 400 assert(scanf("%d%s", &type, buf) == 2); 401 a[i] = buf; 402 403 if (type == 1) { 404 z1.insert(i); 405 } else if (type == 2) { 406 z2.insert(i); 407 } else if (type == 3) { 408 li ans = z1.calc2(i) - z2.calc2(i); 409 printf("%lld\n", ans); 410 fflush(stdout); 411 } else throw; 412 } 413 } 414 ``` 415 416 Complexity: *O*((*slen* + *m*)*logm*), where *slen* is the total length of the string from the input.