677.md (13908B)
1 Source: https://codeforces.com/blog/entry/45181 2 3 [677A - Vanya and Fence](/contest/677/problem/A "Codeforces Round 355 (Div. 2)") 4 5 For each friend we can check, if his height is more than *h*. If it is, then his width is 2, else 1. 6 7 Complexity *O*(*n*). 8 9 **Code** 10 11 ``` 12 #include <iostream> 13 using namespace std; 14 typedef long long ll; 15 ll i,n,h,ans,x; 16 int main() 17 { 18 cin >> n >> h; 19 ans = n; 20 for (i = 0; i < n; i++) 21 { 22 cin >> x; 23 ans += (x>h); 24 } 25 cout << ans << endl; 26 return 0; 27 } 28 ``` 29 30 [677B - Vanya and Food Processor](/contest/677/problem/B "Codeforces Round 355 (Div. 2)") 31 32 The solution, that does same thing, as in the problem statement will fail with TL, because if the height of each piece of potato will be 109 and smashing speed will be 1, then for each piece we will do 109 operations. 33 34 With each new piece of potato *a**i* we will smash the potato till *a*[*i*] *MOD* *k*, so we will waste *a*[*i*] / *k* seconds on it. If we can not put this piece of potato after that, we will waste 1 more second to smash everything, that inside, else just put this piece. We will get an answer same as we could get with actions from the statement. 35 36 Complexity *O*(*n*). 37 38 **Code** 39 40 ``` 41 #include <iostream> 42 #include <stdio.h> 43 using namespace std; 44 typedef long long ll; 45 ll i,n,h,ans,x,cur_h,k; 46 int main() 47 { 48 cin >> n >> h >> k; 49 ans = 0; 50 cur_h = 0; 51 for (i = 0; i < n; i++) 52 { 53 scanf("%I64d", &x); 54 if (cur_h + x <= h) 55 cur_h += x; 56 else 57 ans++, cur_h = x; 58 ans += cur_h/k; 59 cur_h %= k; 60 } 61 ans += cur_h/k; 62 cur_h %= k; 63 ans += (cur_h>0); 64 cout << ans << endl; 65 return 0; 66 } 67 ``` 68 69 [677C - Vanya and Label](/contest/677/problem/C "Codeforces Round 355 (Div. 2)") 70 71 We can transform our word in binary notation, we can do it easily, because 64 = 26. Move through the bits of this number: if bit is equal to 0, then we can have 3 different optinos of this bit in our pair of words: 0&1, 1&0, 0&0, else we can have only one option: 1&1. So the result will be 3*nullbits*, where *nullbits* — is amount of zero bits. 72 73 Complexity *O*(|*s*|). 74 75 **Code** 76 77 ``` 78 #include <iostream> 79 #include <stdio.h> 80 #include <string> 81 #define MOD 1000000007 82 using namespace std; 83 typedef long long ll; 84 ll i,j,n,h,ans,x,cur_h,k; 85 string s; 86 string pattern; 87 ll symbol_val[305]; 88 int main() 89 { 90 cin >> s; 91 for (char i = '0'; i <= '9'; i++) 92 pattern.push_back(i); 93 for (char i = 'A'; i <= 'Z'; i++) 94 pattern.push_back(i); 95 for (char i = 'a'; i <= 'z'; i++) 96 pattern.push_back(i); 97 pattern.push_back('-'); 98 pattern.push_back('_'); 99 for (i = 0; i < 64; i++) 100 symbol_val[pattern[i]] = i; 101 ll ans = 1; 102 for (i = 0; i < s.size(); i++) 103 { 104 ll x = symbol_val[s[i]]; 105 for (j = 0; j < 6; j++) 106 if ((x&(1<<j)) == 0) 107 ans = (ans*3)%MOD; 108 } 109 cout << ans << endl; 110 return 0; 111 } 112 ``` 113 114 [677D - Vanya and Treasure](/contest/677/problem/D "Codeforces Round 355 (Div. 2)") 115 116 We can make dynamic programming *dp*[*col*][*row*], where *dp*[*col*][*row*] is minimal time, that we have waste to open the chest in the cell (*col*, *row*). For the cells of color 1: *dp*[*x*][*y*] = *x* + *y*. For each next color *color* we can look over all cells of color *color* - 1 and all cells of color *color*, then for each cell of color *color* with coordinates (*x*1, *y*1) and for each cell with color *color* - 1 and coordinates (*x*2, *y*2) *dp*[*x*1][*y*1] = *dp*[*x*2][*y*2] + *abs*(*x*1 - *x*2) + *abs*(*y*1 - *y*2). 117 118 But complexity of this solution is *O*(*n*2·*m*2), what is not enough. 119 120 We can do such improvement: let *cnt*[*x*] be the amount of cells of color *x*, then when *cnt*[*color*]·*cnt*[*color* - 1] ≥ *n*·*m*, we can do bfs from cells of color *color* - 1 to cells of color *color*. 121 122 Then we will have complexity *O*(*n*·*m*·*sqrt*(*n*·*m*)). 123 124 [Proof](//codeforces.com/blog/entry/45181?#comment-297475) 125 126 **Code** 127 128 ``` 129 #include <iostream> 130 #include <stdio.h> 131 #include <string> 132 #include <cmath> 133 #include <vector> 134 #include <algorithm> 135 #define MOD 1000000007 136 #define N 2005 137 #define mp make_pair 138 #define X first 139 #define Y second 140 using namespace std; 141 typedef int ll; 142 ll i,j,n,h,x,y,cur_h,k,m,p,fx,fy; 143 ll a[505][505], dp[505][505], d[505][505]; 144 ll dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; 145 vector<pair<ll,ll> > g[250505]; 146 vector<pair<ll, pair<ll,ll> > > lst, bfs; 147 ll Abs(ll x) 148 { 149 return x>0?x:-x; 150 } 151 ll find_dist(ll x1, ll y1, ll x2, ll y2) 152 { 153 return Abs(x1-x2) + Abs(y1-y2); 154 } 155 bool in_range(ll x, ll y) 156 { 157 return (x >= 0 && x < y); 158 } 159 int main() 160 { 161 //freopen("input.txt","r",stdin); 162 //freopen("output.txt","w",stdout); 163 cin >> n >> m >> p; 164 for (i = 0; i < n; i++) 165 for (j = 0; j < m; j++) 166 dp[i][j] = (ll)1e+9; 167 for (i = 0; i < n; i++) 168 for (j = 0; j < m; j++) 169 { 170 scanf("%d", &a[i][j]); 171 g[a[i][j]].push_back(mp(i,j)); 172 if (a[i][j] == 1) 173 dp[i][j] = i+j; 174 if (a[i][j] == p) 175 fx = i, fy = j; 176 } 177 for (i = 2; i <= p; i++) 178 { 179 ll cur_size = g[i].size(); 180 ll last_size = g[i-1].size(); 181 if (cur_size * last_size <= n * m) 182 { 183 for (j = 0; j < cur_size; j++) 184 { 185 ll cur_x = g[i][j].X; 186 ll cur_y = g[i][j].Y; 187 for (k = 0; k < last_size; k++) 188 { 189 ll last_x = g[i-1][k].X; 190 ll last_y = g[i-1][k].Y; 191 dp[cur_x][cur_y] = min(dp[cur_x][cur_y], dp[last_x][last_y] + find_dist(cur_x,cur_y,last_x,last_y)); 192 } 193 } 194 } else 195 { 196 for (k = 0; k < n; k++) 197 for (j = 0; j < m; j++) 198 d[k][j] = -1; 199 bfs.clear(); 200 lst.clear(); 201 for (j = 0; j < last_size; j++) 202 { 203 ll last_x = g[i-1][j].X; 204 ll last_y = g[i-1][j].Y; 205 lst.push_back(mp(dp[last_x][last_y], mp(last_x, last_y))); 206 } 207 sort(lst.begin(), lst.end()); 208 ll pointer = 1; 209 j = 0; 210 bfs.push_back(lst[0]); 211 d[lst[0].Y.X][lst[0].Y.Y] = lst[0].X; 212 while (j < bfs.size()) 213 { 214 ll x = bfs[j].Y.X; 215 ll y = bfs[j].Y.Y; 216 ll val = bfs[j].X; 217 j++; 218 while (pointer < lst.size() && lst[pointer].X <= val) 219 bfs.push_back(lst[pointer++]); 220 for (k = 0; k < 4; k++) 221 if (in_range(x+dir[k][0], n) && in_range(y+dir[k][1], m) && d[x+dir[k][0]][y+dir[k][1]] == -1) 222 { 223 d[x+dir[k][0]][y+dir[k][1]] = val+1; 224 bfs.push_back(mp(val+1, mp(x+dir[k][0], y+dir[k][1]))); 225 } 226 } 227 for (j = 0; j < cur_size; j++) 228 { 229 ll cur_x = g[i][j].X; 230 ll cur_y = g[i][j].Y; 231 dp[cur_x][cur_y] = d[cur_x][cur_y]; 232 } 233 } 234 } 235 cout << dp[fx][fy] << endl; 236 return 0; 237 } 238 ``` 239 240 There also exists solution with 2D segment tree: 241 242 **Code** 243 244 ``` 245 #include <iostream> 246 #include <stdio.h> 247 #include <string> 248 #include <cmath> 249 #include <vector> 250 #include <algorithm> 251 #define MOD 1000000007 252 #define N 512 253 #define mp make_pair 254 #define X first 255 #define Y second 256 using namespace std; 257 typedef int ll; 258 ll i,j,n,h,x,y,glob,k,m,p,fx,fy; 259 ll a[505][505], dp[505][505], d[505][505], t[4][2005][2005]; 260 ll dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; 261 vector<pair<ll,ll> > g[250505]; 262 vector<pair<ll, pair<ll,ll> > > lst, bfs; 263 ll Abs(ll x) 264 { 265 return x>0?x:-x; 266 } 267 ll find_dist(ll x1, ll y1, ll x2, ll y2) 268 { 269 return Abs(x1-x2) + Abs(y1-y2); 270 } 271 bool in_range(ll x, ll y) 272 { 273 return (x >= 0 && x < y); 274 } 275 276 int get (int lx, int rx, int ly, int ry) { 277 rx++; 278 ry++; 279 int res = MOD; 280 ll l = ly, r = ry; 281 for (lx += N, rx += N; lx < rx; lx >>= 1, rx >>= 1) { 282 if (rx&1) 283 { 284 ly = l; ry = r; 285 rx--; 286 for (ly += N, ry += N; ly < ry; ly >>= 1, ry >>= 1) { 287 288 if (ly&1) 289 { 290 res = min(res, t[glob][rx][ly]); 291 ly++; 292 } 293 if (ry&1) 294 { 295 --ry; 296 res = min(res, t[glob][rx][ry]); 297 } 298 } 299 } 300 if (lx&1) 301 { 302 ly = l; ry = r; 303 for (ly += N, ry += N; ly < ry; ly >>= 1, ry >>= 1) { 304 305 if (ly&1) 306 { 307 res = min(res, t[glob][lx][ly]); 308 ly++; 309 } 310 if (ry&1) 311 { 312 --ry; 313 res = min(res, t[glob][lx][ry]); 314 } 315 } 316 lx++; 317 } 318 } 319 return res; 320 } 321 322 void update (int x, int y, int val) { 323 ll tmp = y; 324 t[glob][x+N][tmp+N] = val; 325 for (x += N; x > 1; x >>= 1) 326 { 327 y = tmp; 328 for (y += N; y > 1; y >>= 1) 329 { 330 t[glob][x][y>>1] = min(t[glob][x][y], t[glob][x][y^1]); 331 t[glob][x>>1][y] = min(t[glob][x][y], t[glob][x^1][y]); 332 } 333 t[glob][x>>1][y] = min(t[glob][x][y], t[glob][x^1][y]); 334 } 335 } 336 337 int main() 338 { 339 //freopen("input.txt","r",stdin); 340 //freopen("output.txt","w",stdout); 341 cin >> n >> m >> p; 342 for (i = 0; i < n; i++) 343 for (j = 0; j < m; j++) 344 dp[i][j] = MOD; 345 for (i = 0; i < n; i++) 346 for (j = 0; j < m; j++) 347 { 348 scanf("%d", &a[i][j]); 349 g[a[i][j]].push_back(mp(i,j)); 350 if (a[i][j] == 1) 351 dp[i][j] = i+j; 352 if (a[i][j] == p) 353 fx = i, fy = j; 354 } 355 for (i = 0; i <= N*2; i++) 356 for (j = 0; j <= N*2; j++) 357 for (k = 0; k < 4; k++) 358 t[k][i][j] = MOD; 359 //UR - dp[x2][y2] = dp[x1][y1] + x2-x1+y2-y1 = dp[x1][y1]-x1-y1+(x2+y2) 360 //UL - dp[x2][y2] = dp[x1][y1] + x2-x1+y1-y2 = dp[x1][y1]-x1+y1+(x2-y2) 361 //DR - dp[x2][y2] = dp[x1][y1] + x1-x2+y2-y1 = dp[x1][y1]-y1+x1+(y2-x1) 362 //DL - dp[x2][y2] = dp[x1][y1] + x1-x2+y1-y2 = dp[x1][y1]+x1+y1+(-x2-y2) 363 for (i = 2; i <= p; i++) 364 { 365 ll last_sz = g[i-1].size(); 366 for (j = 0; j < last_sz; j++) 367 { 368 ll x = g[i-1][j].X; 369 ll y = g[i-1][j].Y; 370 glob = 0; 371 //cout << x << " " << y << " " << get( 0, x, 0, y) << "g" << endl; 372 update(x,y,dp[x][y]-x-y); 373 //cout << get( 0, x, 0, y) << "f" << endl; 374 glob = 1; 375 update(x,y,dp[x][y]-x+y); 376 glob = 2; 377 update(x,y,dp[x][y]+x-y); 378 glob = 3; 379 update(x,y,dp[x][y]+x+y); 380 } 381 ll cur_sz = g[i].size(); 382 for (j = 0; j < cur_sz; j++) 383 { 384 ll x = g[i][j].X; 385 ll y = g[i][j].Y; 386 glob = 0; 387 //cout << get( 0, x, 0, y) << endl; 388 dp[x][y] = min(dp[x][y], get( 0, x, 0, y)+x+y); 389 glob = 1; 390 dp[x][y] = min(dp[x][y], get(0, x, y, m-1)+x-y); 391 glob = 2; 392 dp[x][y] = min(dp[x][y], get(x, n-1, 0, y)-x+y); 393 glob = 3; 394 dp[x][y] = min(dp[x][y], get(x, n-1, y, m-1)-x-y); 395 } 396 for (j = 0; j < last_sz; j++) 397 { 398 ll x = g[i-1][j].X; 399 ll y = g[i-1][j].Y; 400 glob = 0; 401 update(x,y,MOD); 402 glob = 1; 403 update(x,y,MOD); 404 glob = 2; 405 update(x,y,MOD); 406 glob = 3; 407 update(x,y,MOD); 408 } 409 } 410 /*for (i = 0; i < n; i++) 411 { 412 for (j = 0; j < m; j++) 413 cout << dp[i][j] << " "; 414 cout << endl; 415 }*/ 416 cout << dp[fx][fy] << endl; 417 return 0; 418 } 419 ``` 420 421 [677E - Vanya and Balloons](/contest/677/problem/E "Codeforces Round 355 (Div. 2)") 422 423 For each cell (*x*, *y*) take the maximum possible cross with center in this cell, that doesn't contains zeros. To do it fast, we can make arrays of partial sums for all possible 8 directions, in which each cell will contain the number of non-zero balloons in each direction. For example, if we want to know, how many non-zero balloons are right to cell (*x*, *y*), we can create an array *p*[*x*][*y*], where *p*[*x*][*y*] = *p*[*x*][*y* - 1] + 1 if *a*[*x*][*y*]! = 0 else *p*[*x*][*y*] = 0 424 425 So now we can for each cell (*x*, *y*) we can find the maximum size of cross with the centre in this cell, that will not contain zeros. 426 427 We can compare product for crosses with centers in the cells (*x*, *y*) and radius *r* using logarythms. For example, if we need to compare 2 crosses with values *x*1·*x*2·...·*x**n* and *y*1·*y*2·...·*y**m*, we can compare *log*(*x*1·*x*2·...·*x**n*) and *log*(*y*1·*y*2·...·*y**n*), what will be equivalent to comparing *log*(*x*1) + *log*(*x*2) + ... + *log*(*x**n*) and *log*(*y*1) + *log*(*y*2) + ... + *log*(*y**m*). 428 429 We can also use partial sum arrays to find value *log*(*x*1) + *log*(*x*2) + ... + *log*(*x**n*) for each cross, so we can find the product of the values in each cross for *O*(1) time. 430 431 Complexity *O*(*n*2). 432 433 **Code** 434 435 ``` 436 #include <iostream> 437 #include <stdio.h> 438 #include <string> 439 #include <cmath> 440 #define MOD 1000000007 441 #define N 2005 442 using namespace std; 443 typedef unsigned int ll; 444 ll i,j,n,h,x,y,cur_h,k,dir; 445 ll pre[8][N][N]; 446 double sums[8][N][N],ans,logs[N][N],lg2,lg3; 447 ll ansx,ansy,anssize,ansdir; 448 ll total; 449 ll directions[8][2] = {{-1,-1},{-1,1},{1,-1},{1,1},{1,0},{0,1},{-1,0},{0,-1}}; 450 char a[N][N]; 451 bool in_range(ll x) 452 { 453 return (x >= 0 && x < n); 454 } 455 int main() 456 { 457 //freopen("input.txt","r",stdin); 458 //freopen("output.txt","w",stdout); 459 lg2 = log(2); 460 lg3 = log(3); 461 cin >> n; 462 for (i = 0; i < n; i++) 463 scanf("%s",a[i]); 464 for (i = 0; i < n; i++) 465 for (j = 0; j < n; j++) 466 if (a[i][j] == '3') 467 logs[i][j] = lg3; 468 else if (a[i][j] == '2') 469 logs[i][j] = lg2; 470 for (dir = 0; dir < 8; dir++) 471 { 472 for (i = 0; i < n; i++) 473 for (j = 0; j < n; j++) 474 if (!in_range(i-directions[dir][0]) || !in_range(j-directions[dir][1])) 475 { 476 k = 0; 477 ll d1 = directions[dir][0], d2 = directions[dir][1]; 478 for (x = i, y = j; in_range(x) && in_range(y); x += d1, y += d2) 479 { 480 if (a[x][y] != '0') 481 { 482 k++; 483 if (x == i && y == j) 484 sums[dir][x][y] = logs[i][j]; 485 else 486 sums[dir][x][y] = sums[dir][x-d1][y-d2] + logs[x][y]; 487 } 488 else 489 { 490 sums[dir][x][y] = 0; 491 k = 0; 492 } 493 pre[dir][x][y] = k; 494 } 495 } 496 } 497 ans = -1; 498 for (i = 0; i < n; i++) 499 for (j = 0; j < n; j++) 500 if (a[i][j] != '0') 501 { 502 ll tmp = n+5; 503 for (k = 0; k < 4; k++) 504 tmp = min(tmp, pre[k][i][j]); 505 double val = logs[i][j]; 506 for (k = 0; k < 4; k++) 507 val += sums[k][i+directions[k][0]*(tmp-1)][j+directions[k][1]*(tmp-1)] - sums[k][i][j]; 508 if (val > ans) 509 { 510 ans = val; 511 ansx = i; 512 ansy = j; 513 anssize = tmp; 514 ansdir = 0; 515 } 516 517 tmp = n+5; 518 for (k = 4; k < 8; k++) 519 tmp = min(tmp, pre[k][i][j]); 520 val = logs[i][j]; 521 for (k = 4; k < 8; k++) 522 val += sums[k][i+directions[k][0]*(tmp-1)][j+directions[k][1]*(tmp-1)] - sums[k][i][j]; 523 if (val > ans) 524 { 525 ans = val; 526 ansx = i; 527 ansy = j; 528 anssize = tmp; 529 ansdir = 4; 530 } 531 } 532 total = a[ansx][ansy]-'0'; 533 for (k = ansdir; k < ansdir+4; k++) 534 { 535 for (i = 1; i < anssize; i++) 536 total = (total*(a[ansx+directions[k][0]*i][ansy+directions[k][1]*i]-'0'))%MOD; 537 } 538 cout << total << endl; 539 return 0; 540 } 541 ```