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 . 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 . 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): . 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  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  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: .