codeforces-scrape

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

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 ```