codeforces-scrape

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

678.md (10011B)


      1 Source: https://codeforces.com/blog/entry/45405
      2 
      3 ### [678A - Johny Likes Numbers](/contest/678/problem/A "Educational Codeforces Round 13")
      4 
      5 The problem was suggested by Abdrakhman Ismail [bash](/profile/bash "Newbie bash").
      6 
      7 We should find minimal *x*, so *x*·*k* > *n*. Easy to see that ![](https://espresso.codeforces.com/546d523a9ebdd80a301c2b3002821a64fed4eb17.png). To learn more about floor/ceil functions I reccomend the book of authors Graham, Knuth, Patashnik "Concrete Mathematics". There is a chapter there about that functions and their properties.
      8 
      9 **С++ solution**
     10 
     11 ```
     12 li n, k;
     13 
     14 bool read() {
     15 	return !!(cin >> n >> k);
     16 }
     17 
     18 void solve() {
     19 	cout << (n / k + 1) * k << endl;
     20 }
     21 ```
     22 
     23 Complexity: *O*(1).
     24 
     25 ### [678B - The Same Calendar](/contest/678/problem/B "Educational Codeforces Round 13")
     26 
     27 The problem was suggested by Arthur Jaworski [KingArthur](/profile/KingArthur "Expert KingArthur").
     28 
     29 Two calendars are same if and only if they have the same number of days and starts with the same day of a week. So we should simply iterate over years and maintain the day of a week of January, 1st (for example). Easy to see that the day of a week increases by one each year except of the leap years, when it increases by two.
     30 
     31 **C++ solution**
     32 
     33 ```
     34 int y;
     35 
     36 bool read() {
     37 	return !!(cin >> y);
     38 }
     39 
     40 bool leap(int y) {
     41 	return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
     42 }
     43 
     44 void solve() {
     45 	bool is_leap = leap(y);
     46 	int d = 0;
     47 	do {
     48 		d++;
     49 		if (leap(y)) d++;
     50 		y++;
     51 		d %= 7;
     52 	} while (d || leap(y) != is_leap);
     53 	cout << y << endl;
     54 }
     55 ```
     56 
     57 Complexity: *O*(1) — easy to see that we will not iterate more than some small fixed constant times.
     58 
     59 ### [678C - Joty and Chocolate](/contest/678/problem/C "Educational Codeforces Round 13")
     60 
     61 The problem was suggested by Sheikh Monir [skmonir](/profile/skmonir "Specialist skmonir").
     62 
     63 Easy to see that we can paint with both colours only tiles with the numbers multiple of *lcm*(*a*, *b*). Obviously that tiles should be painted with more expensive colour. So the answer equals to ![](https://espresso.codeforces.com/933cf916e3cb993c6b57f5d6c430c6fd6e73b431.png).
     64 
     65 **C++ solution**
     66 
     67 ```
     68 li n, a, b, p, q;
     69 
     70 bool read() {
     71 	return !!(cin >> n >> a >> b >> p >> q);
     72 }
     73 
     74 li gcd(li a, li b) { return !a ? b : gcd(b % a, a); }
     75 li lcm(li a, li b) { return a / gcd(a, b) * b; }
     76 
     77 void solve() {
     78 	li ans = 0;
     79 	ans += (n / a) * p;
     80 	ans += (n / b) * q;
     81 	ans -= (n / lcm(a, b)) * min(p, q);
     82 	cout << ans << endl;
     83 }
     84 ```
     85 
     86 Complexity: *O*(*log*(*max*(*a*, *b*))).
     87 
     88 ### [678D - Iterated Linear Function](/contest/678/problem/D "Educational Codeforces Round 13")
     89 
     90 The problem was suggested by Zi Song Yeoh [zscoder](/profile/zscoder "Candidate Master zscoder").
     91 
     92 The problem can be solved using closed formula: it's need to calculate the sum of geometric progression. The formula can be calculated using binary exponentiation.
     93 
     94 I'll describe more complicated solution, but it's more general. If we have a set of variables and at each step all variables are recalculating from each other using linear function, we can use binary matrix exponentiation. There is only one variable *x* in our problem. The new variable *x*' is calculating using formula *A*·*x* + *B*. Consider the matrix *z* = [[*A*, *B*], [0, 1]] and the vector *v* = [0, 1]. Let's multiply *z* and *v*. Easy to see that we will get the vector *v*' = [*x*', 1]. So to make *n* iterations we should multiply *z* and *v* *n* times. We can do that using binary matrix exponentiation, because matrix multiplication is associative.
     95 
     96 As an exercise try to write down the matrix for the Fibonacci numbers and calculate the *n*-th Fibonacci number in *O*(*logn*) time. The matrix and the vector is under the spoiler.
     97 
     98 **The matrix and the vector for the Fibonacci numbers**
     99 
    100 z=[[0, 1], [1, 1]], v=[0, 1].
    101 
    102 **C++ solution**
    103 
    104 ```
    105 int A, B, x;
    106 li n;
    107 
    108 bool read() {
    109 	return !!(cin >> A >> B >> n >> x);
    110 }
    111 
    112 const int mod = 1000 * 1000 * 1000 + 7;
    113 
    114 inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
    115 inline int mul(int a, int b) { return int(a * 1ll * b % mod); }
    116 inline void inc(int& a, int b) { a = add(a, b); }
    117 
    118 void mul(int a[2][2], int b[2][2]) {
    119 	static int res[2][2];
    120 	forn(i, 2)
    121 		forn(j, 2) {
    122 			res[i][j] = 0;
    123 			forn(k, 2) inc(res[i][j], mul(a[i][k], b[k][j]));
    124 		}
    125 	forn(i, 2) forn(j, 2) a[i][j] = res[i][j];
    126 }
    127 
    128 void bin_pow(int a[2][2], li b) {
    129 	static int res[2][2];
    130 	forn(i, 2) forn(j, 2) res[i][j] = i == j;
    131 
    132 	while (b) {
    133 		if (b & 1) mul(res, a);
    134 		mul(a, a);
    135 		b >>= 1;
    136 	}
    137 
    138 	forn(i, 2) forn(j, 2) a[i][j] = res[i][j];
    139 }
    140 
    141 void solve() {
    142 	int z[2][2] = {
    143 		{ A, B },
    144 		{ 0, 1 }
    145 	};
    146 	bin_pow(z, n);
    147 	int result = add(mul(z[0][0], x), z[0][1]);
    148 	cout << result << endl;
    149 }
    150 ```
    151 
    152 Complexity: *O*(*logn*).
    153 
    154 ### [678E - Another Sith Tournament](/contest/678/problem/E "Educational Codeforces Round 13")
    155 
    156 The problem was suggested and prepared by Alexey Dergunov [dalex](/profile/dalex "Candidate Master dalex").
    157 
    158 Let's solve the problem using dynamic programming. *z**mask*, *i* — the maximal probability of Ivans victory if the siths from the *mask* already fought and the *i*-th sith left alive. To calculate that DP we should iterate over the next sith (he will fight against the *i*-th sith): ![](https://espresso.codeforces.com/e822e8c3114a3cf1c00bc7f303a4df78b5bf0bd4.png).
    159 
    160 **C++ solution**
    161 
    162 ```
    163 const int N = 20, EXPN = (1 << 18) + 3;
    164 
    165 int n;
    166 ld p[N][N];
    167 
    168 bool read() {
    169 	if (!(cin >> n)) return false;
    170 	forn(i, n) forn(j, n) assert(cin >> p[i][j]);
    171 	return true;
    172 }
    173 
    174 ld z[EXPN][N];
    175 
    176 ld solve(int mask, int i) {
    177 	ld& ans = z[mask][i];
    178 	if (ans > -0.5) return ans;
    179 	if (mask == (1 << n) - 1) return ans = !i;
    180 	ans = 0;
    181 	forn(j, n)
    182 		if (!(mask & (1 << j))) {
    183 			ld cur = 0;
    184 			cur += solve(mask | (1 << j), i) * p[i][j];
    185 			cur += solve(mask | (1 << j), j) * p[j][i];
    186 			ans = max(ans, cur);
    187 		}
    188 	return ans;
    189 }
    190 
    191 void solve() {
    192 	if (n == 1) {
    193 		puts("1");
    194 		return;
    195 	}
    196 
    197 	forn(i, 1 << n) forn(j, n) z[i][j] = -1;
    198 
    199 	ld ans = 0;
    200 	forn(i, n)
    201 		forn(j, i) {
    202 			int mask = (1 << i) | (1 << j);
    203 			ld cur = 0;
    204 			cur += solve(mask, i) * p[i][j];
    205 			cur += solve(mask, j) * p[j][i];
    206 			ans = max(ans, cur);
    207 		}
    208 	cout << ans << endl;
    209 }
    210 ```
    211 
    212 Time complexity: *O*(2*n**n*2).
    213 
    214 Memory complexity: *O*(2*n**n*).
    215 
    216 ### [678F - Lena and Queries](/contest/678/problem/F "Educational Codeforces Round 13")
    217 
    218 The problem was suggested by AmirMohammad Dehghan [PrinceOfPersia](/profile/PrinceOfPersia "International Master PrinceOfPersia").
    219 
    220 Let's interpret the problem geometrically: the pairs from the set are the lines and the problem to find to topmost intersection of the vertical line with the lines from the set.
    221 
    222 Let's split the queries to ![](https://espresso.codeforces.com/909ec83af66a546b3f5db58ea951d4a6289ac97d.png) blocks. Consider the lines added before the current block and that will not deleted in the current block. Let's build the lower envelope by that lines. Now to calculate the answer to the query we should get maximum over the lines from the envelope and the lines from the block before the current query that is not deleted yet. There are no more than ![](https://espresso.codeforces.com/909ec83af66a546b3f5db58ea951d4a6289ac97d.png) lines from the block, so we can iterate over them. Let's find the answers from the envelope for all queries of the third type from the block at once: we should sort them and iterate over envelope using *two pointers technique*.
    223 
    224 **C++ solution**
    225 
    226 ```
    227 const int N = 300300;
    228 
    229 int n;
    230 int t[N], a[N], b[N], id[N], q[N];
    231 
    232 bool read() {
    233 	if (!(cin >> n)) return false;
    234 	forn(i, n) {
    235 		assert(scanf("%d", &t[i]) == 1);
    236 		if (t[i] == 1) {
    237 			assert(scanf("%d%d", &a[i], &b[i]) == 2);
    238 		} else if (t[i] == 2) {
    239 			assert(scanf("%d", &id[i]) == 1);
    240 			id[i]--;
    241 		} else if (t[i] == 3) {
    242 			assert(scanf("%d", &q[i]) == 1);
    243 		} else throw;
    244 	}
    245 	return true;
    246 }
    247 
    248 bool in_set[N], deleted[N];
    249 vector<pair<pti, int>> lines;
    250 vector<pti> envelope;
    251 
    252 void build_envelope() {
    253 	envelope.clear();
    254 	envelope.reserve(n);
    255 
    256 	forn(ii, sz(lines)) {
    257 		int i = lines[ii].y;
    258 		if (in_set[i] && !deleted[i]) {
    259 			assert(t[i] == 1);
    260 			pti c(a[i], b[i]);
    261 			while (!envelope.empty()) {
    262 				pti b = envelope.back();
    263 				if (b.x == c.x) {
    264 					envelope.pop_back();
    265 					continue;
    266 				} else if (sz(envelope) > 1) {
    267 					pti a = envelope[sz(envelope) - 2];
    268 
    269 					ld xc = ld(c.y - a.y) / (a.x - c.x);
    270 					ld xb = ld(b.y - a.y) / (a.x - b.x);
    271 
    272 					if (xc < xb) {
    273 						envelope.pop_back();
    274 						continue;
    275 					}
    276 				}
    277 				break;
    278 			}
    279 			envelope.pb(c);
    280 		}
    281 	}
    282 }
    283 
    284 li ans[N];
    285 vector<pti> qs;
    286 
    287 void process_qs() {
    288 	sort(all(qs));
    289 
    290 	int p = 0;
    291 	forn(i, sz(qs)) {
    292 		li q = qs[i].x;
    293 		int id = qs[i].y;
    294 
    295 		while (p + 1 < sz(envelope)) {
    296 			li cval = envelope[p].x * q + envelope[p].y;
    297 			li nval = envelope[p + 1].x * q + envelope[p + 1].y;
    298 			if (cval > nval) break;
    299 			p++;
    300 		}
    301 
    302 		if (p < sz(envelope)) {
    303 			ans[id] = envelope[p].x * q + envelope[p].y;
    304 		}
    305 	}
    306 }
    307 
    308 void solve() {
    309 	lines.clear();
    310 	lines.reserve(n);
    311 	forn(i, n) if (t[i] == 1) lines.pb(mp(mp(a[i], b[i]), i));
    312 	sort(all(lines));
    313 
    314 	memset(in_set, false, sizeof(in_set));
    315 	memset(deleted, false, sizeof(deleted));
    316 	forn(i, n) ans[i] = LLONG_MIN;
    317 
    318 	int blen = int(sqrtl(n));
    319 	blen = 2500;
    320 	for (int l = 0; l < n; l += blen) {
    321 		int r = min(n, l + blen);
    322 
    323 		memset(deleted, false, sizeof(deleted));
    324 		fore(i, l, r) if (t[i] == 2) deleted[id[i]] = true;
    325 		build_envelope();
    326 
    327 		qs.clear();
    328 		qs.reserve(r - l);
    329 		fore(i, l, r) if (t[i] == 3) qs.pb(mp(q[i], i));
    330 		process_qs();
    331 
    332 		fore(i, l, r) {
    333 			if (t[i] == 1) in_set[i] = true;
    334 			else if (t[i] == 2) in_set[id[i]] = false;
    335 			else {
    336 				fore(j, l, r) {
    337 					if (t[j] == 1 && in_set[j])
    338 						ans[i] = max(ans[i], li(a[j]) * q[i] + b[j]);
    339 					else if (t[j] == 2 && in_set[id[j]])
    340 						ans[i] = max(ans[i], li(a[id[j]]) * q[i] + b[id[j]]);
    341 				}
    342 				if (ans[i] != LLONG_MIN) printf("%lldn", ans[i]);
    343 				else puts("EMPTY SET");
    344 			}
    345 		}
    346 	}
    347 }
    348 ```
    349 
    350 Complexity: ![](https://espresso.codeforces.com/9ca62661ea21b1ce54195f1d67b5981f402316e3.png).