codeforces-scrape

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

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: ![](https://espresso.codeforces.com/e64d826b4cdfc09b354f5e0a3078a306e41d8a11.png), where the last equation can be solved by extended Euclid algorithm and *p* is any integral number. The variable *p* should satisfy two conditions: ![](https://espresso.codeforces.com/1c02ef9dd598fd49eafefdf4c7edbcabd5dd91f6.png) and ![](https://espresso.codeforces.com/ce3bb6fcb4fa001df5c0dd3ba507b10b48b1a628.png). 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.