Codeforces Round #355 (Div. 2) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Для каждого друга смотрим, будет ли его высота больше h. Если да, то его ширина — 2, иначе — 1.

Complexity O(n).

Code

#include <iostream>
using namespace std;
typedef long long ll;
ll i,n,h,ans,x;
int main()
{
	cin >> n >> h;
	ans = n;
	for (i = 0; i < n; i++)
	{
		cin >> x;
		ans += (x>h);
	}
	cout << ans << endl;
	return 0;
}

677B - Ваня и кухонный комбайн

Решение, которое просто делает то, что описано в условии, не пройдет, т.к. если высота каждой картофелины будет 10⁹, а скорость измельчения — 1, то на каждую картофелину будем тратить 10⁹ операций.

С каждой новой картофелиной высотой a_i будем измельчать картофель до высоты a_i MOD k, тогда мы будем тратить на это a[i] / k секунд. Если мы не можем засунуть после этого новую картофелину, то мы потратим еще 1 секунду, иначе просто положим эту картофелину. Мы получим такой же ответ, как бы если мы делали то, что описано в условии.

Асимптотика O(n).

Code

#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;
ll i,n,h,ans,x,cur_h,k;
int main()
{
	cin >> n >> h >> k;
	ans = 0;
	cur_h = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%I64d", &x);
		if (cur_h + x <= h)
		   cur_h += x;
		else
			ans++, cur_h = x;
		ans += cur_h/k;
		cur_h %= k;
	}
	ans += cur_h/k;
	cur_h %= k;
	ans += (cur_h>0);
	cout << ans << endl;
	return 0;
}

677C - Ваня и надпись

Переведем слово в 2-ичную систему счисления, это сделать легко, так как 64 — степень двойки. Проходимся по битах этого числа: если бит равен 0, то у нас может быть 3 различных варианта этого бита в нашей паре слов: 0&1, 1&0, 0&0, иначе только один вариант: 1&1. В таком случае результатом будет 3^nullbits, где nullbits — количество нулевых битов.

Асимптотика O(|s|).

Code

#include <iostream>
#include <stdio.h>
#include <string>
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll i,j,n,h,ans,x,cur_h,k;
string s;
string pattern;
ll symbol_val[305];
int main()
{
	cin >> s;
	for (char i = '0'; i <= '9'; i++)
		pattern.push_back(i);
	for (char i = 'A'; i <= 'Z'; i++)
		pattern.push_back(i);
	for (char i = 'a'; i <= 'z'; i++)
		pattern.push_back(i);
	pattern.push_back('-');
	pattern.push_back('_');
	for (i = 0; i < 64; i++)
		symbol_val[pattern[i]] = i;
	ll ans = 1;
	for (i = 0; i < s.size(); i++)
	{
		ll x = symbol_val[s[i]];
		for (j = 0; j < 6; j++)
			if ((x&(1<<j)) == 0)
			   ans = (ans*3)%MOD;
	}
	cout << ans << endl;
	return 0;
}

677D - Ваня и сокровище

Сделаем динамику dp[col][row], где dp[col][row] — минимальное время, которое нужно для того, чтобы открыть сундук в клетке (col, row). Для клеток цвета 1 dp[x][y] = x + y. Для каждого следующего цвета color будем перебирать все клетки цвета color - 1 и все клетки цвета color, тогда для каждой клетки цвета color с координатами (x1, y1) и клетки цвета color - 1 с координатами (x2, y2) dp[x1][y1] = dp[x2][y2] + abs(x1 - x2) + abs(y1 - y2).

Но этого решения будет недостаточно, так как его асимптотика — O(n²·m²)

Можем сделать такое улучшение: пусть cnt[x] — количество клеток цвета x, тогда когда cnt[color]·cnt[color - 1] ≥ n·m, можно сделать поиск в ширину от клеток цвета color - 1 к клеткам цвета color.

В таком случае будет асимптотика O(n·m·sqrt(n·m)).

Доказательство

Code

#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#define MOD 1000000007
#define N 2005
#define mp make_pair
#define X first
#define Y second
using namespace std;
typedef int ll;
ll i,j,n,h,x,y,cur_h,k,m,p,fx,fy;
ll a[505][505], dp[505][505], d[505][505];
ll dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
vector<pair<ll,ll> > g[250505];
vector<pair<ll, pair<ll,ll> > > lst, bfs;
ll Abs(ll x)
{
	return x>0?x:-x;
}
ll find_dist(ll x1, ll y1, ll x2, ll y2)
{
	return Abs(x1-x2) + Abs(y1-y2);
}
bool in_range(ll x, ll y)
{
	return (x >= 0 && x < y);
}
int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin >> n >> m >> p;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			dp[i][j] = (ll)1e+9;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
		{
			scanf("%d", &a[i][j]);
			g[a[i][j]].push_back(mp(i,j));
			if (a[i][j] == 1)
			   dp[i][j] = i+j;
			if (a[i][j] == p)
			   fx = i, fy = j;
		}
	for (i = 2; i <= p; i++)
	{
		ll cur_size = g[i].size();
		ll last_size = g[i-1].size();
		if (cur_size*last_size <= n*m)
		{
			for (j = 0; j < cur_size; j++)
			{
				ll cur_x = g[i][j].X;
				ll cur_y = g[i][j].Y;
				for (k = 0; k < last_size; k++)
				{
					ll last_x = g[i-1][k].X;
					ll last_y = g[i-1][k].Y;
					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));
				}
			}
		} else
		{
			for (k = 0; k < n; k++)
				for (j = 0; j < m; j++)
					d[k][j] = -1;
			bfs.clear();
			lst.clear();
			for (j = 0; j < last_size; j++)
			{
				ll last_x = g[i-1][j].X;
				ll last_y = g[i-1][j].Y;
				lst.push_back(mp(dp[last_x][last_y], mp(last_x, last_y)));
			}
			sort(lst.begin(), lst.end());
			ll pointer = 1;
			j = 0;
			bfs.push_back(lst[0]);
			d[lst[0].Y.X][lst[0].Y.Y] = lst[0].X;
			while (j < bfs.size())
			{
				ll x = bfs[j].Y.X;
				ll y = bfs[j].Y.Y;
				ll val = bfs[j].X;
				j++;
				while (pointer < lst.size() && lst[pointer].X <= val)
					  bfs.push_back(lst[pointer++]);
				for (k = 0; k < 4; k++)
					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)
					{
						d[x+dir[k][0]][y+dir[k][1]] = val+1;
						bfs.push_back(mp(val+1, mp(x+dir[k][0], y+dir[k][1])));
					}
			}
			for (j = 0; j < cur_size; j++)
			{
				ll cur_x = g[i][j].X;
				ll cur_y = g[i][j].Y;
				dp[cur_x][cur_y] = d[cur_x][cur_y];
			}
		}
	}
	cout << dp[fx][fy] << endl;
	return 0;
}

Также есть решение с использованием двухмерного дерева отрезков:

Code

#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#define MOD 1000000007
#define N 512
#define mp make_pair
#define X first
#define Y second
using namespace std;
typedef int ll;
ll i,j,n,h,x,y,glob,k,m,p,fx,fy;
ll a[505][505], dp[505][505], d[505][505], t[4][2005][2005];
ll dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
vector<pair<ll,ll> > g[250505];
vector<pair<ll, pair<ll,ll> > > lst, bfs;
ll Abs(ll x)
{
	return x>0?x:-x;
}
ll find_dist(ll x1, ll y1, ll x2, ll y2)
{
	return Abs(x1-x2) + Abs(y1-y2);
}
bool in_range(ll x, ll y)
{
	return (x >= 0 && x < y);
}

int get (int lx, int rx, int ly, int ry) {
	rx++;
	ry++;
	int res = MOD;
	ll l = ly, r = ry;
  for (lx += N, rx += N; lx < rx; lx >>= 1, rx >>= 1) {
  	if (rx&1)
  	{
  		ly = l; ry = r;
	    rx--;
	    for (ly += N, ry += N; ly < ry; ly >>= 1, ry >>= 1) {

		    if (ly&1)
		    {
		       res = min(res, t[glob][rx][ly]);
		       ly++;
		    }
			if (ry&1)
			{
			    --ry;
			    res = min(res, t[glob][rx][ry]);
			}
		}
	}
    if (lx&1)
    {
    	ly = l; ry = r;
		for (ly += N, ry += N; ly < ry; ly >>= 1, ry >>= 1) {

		    if (ly&1)
		    {
		       res = min(res, t[glob][lx][ly]);
		       ly++;
		    }
			if (ry&1)
			{
			    --ry;
			    res = min(res, t[glob][lx][ry]);
			}
		}
	    lx++;
    }
  }
  return res;
}

void update (int x, int y, int val) {
	ll tmp = y;
	t[glob][x+N][tmp+N] = val;
	for (x += N; x > 1; x >>= 1)
	{
		y = tmp;
		for (y += N; y > 1; y >>= 1)
		{
			t[glob][x][y>>1] = min(t[glob][x][y], t[glob][x][y^1]);
			t[glob][x>>1][y] = min(t[glob][x][y], t[glob][x^1][y]);
		}
		t[glob][x>>1][y] = min(t[glob][x][y], t[glob][x^1][y]);
	}
}


int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin >> n >> m >> p;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			dp[i][j] = MOD;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
		{
			scanf("%d", &a[i][j]);
			g[a[i][j]].push_back(mp(i,j));
			if (a[i][j] == 1)
			   dp[i][j] = i+j;
			if (a[i][j] == p)
			   fx = i, fy = j;
		}
	for (i = 0; i <= N*2; i++)
		for (j = 0; j <= N*2; j++)
			for (k = 0; k < 4; k++)
				t[k][i][j] = MOD;
	//UR - dp[x2][y2] = dp[x1][y1] + x2-x1+y2-y1 = dp[x1][y1]-x1-y1+(x2+y2)
	//UL - dp[x2][y2] = dp[x1][y1] + x2-x1+y1-y2 = dp[x1][y1]-x1+y1+(x2-y2)
	//DR - dp[x2][y2] = dp[x1][y1] + x1-x2+y2-y1 = dp[x1][y1]-y1+x1+(y2-x1)
	//DL - dp[x2][y2] = dp[x1][y1] + x1-x2+y1-y2 = dp[x1][y1]+x1+y1+(-x2-y2)
	for (i = 2; i <= p; i++)
	{
		ll last_sz = g[i-1].size();
		for (j = 0; j < last_sz; j++)
		{
			ll x = g[i-1][j].X;
			ll y = g[i-1][j].Y;
			glob = 0;
			//cout << x << " " << y << " " << get( 0, x, 0, y) << "g" << endl;
			update(x,y,dp[x][y]-x-y);
			//cout << get( 0, x, 0, y) << "f" << endl;
			glob = 1;
			update(x,y,dp[x][y]-x+y);
			glob = 2;
			update(x,y,dp[x][y]+x-y);
			glob = 3;
			update(x,y,dp[x][y]+x+y);
		}
		ll cur_sz = g[i].size();
		for (j = 0; j < cur_sz; j++)
		{
			ll x = g[i][j].X;
			ll y = g[i][j].Y;
			glob = 0;
			//cout << get( 0, x, 0, y) << endl;
			dp[x][y] = min(dp[x][y], get( 0, x, 0, y)+x+y);
			glob = 1;
			dp[x][y] = min(dp[x][y], get(0, x, y, m-1)+x-y);
			glob = 2;
			dp[x][y] = min(dp[x][y], get(x, n-1, 0, y)-x+y);
			glob = 3;
			dp[x][y] = min(dp[x][y], get(x, n-1, y, m-1)-x-y);
		}
		for (j = 0; j < last_sz; j++)
		{
			ll x = g[i-1][j].X;
			ll y = g[i-1][j].Y;
			glob = 0;
			update(x,y,MOD);
			glob = 1;
			update(x,y,MOD);
			glob = 2;
			update(x,y,MOD);
			glob = 3;
			update(x,y,MOD);
		}
	}
	/*for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
			cout << dp[i][j] << " ";
		cout << endl;
	}*/
	cout << dp[fx][fy] << endl;
	return 0;
}

677E - Ваня и шарики

Для каждой клетки (x, y) в таблице возьмем максимально возможный крест, в котором не присутствуют нули. Чтобы сделать это быстро, сохраним массивы частичных сумм для всех возможных 8 направлений, где каждая клетка будет обозначать количество ненулевых шариков в каждом из направлений. Например для того, чтобы узнать, сколько ненулевых шариков находится справа от клетки (x, y), создадим массив p[x][y], в котором p[x][y] = p[x][y - 1] + 1 если a[x][y]! = 0 иначе p[x][y] = 0

Таким образом для каждой клетки (x, y) мы можем найти крест максимального размера, в котором не будет нулей.

Мы можем сравнить значения произведений для крестов в координатах (x, y) и с радиусом r, воспользовавшись логарифмированием. К примеру, если нам нужно сравнить кресты с значениями x₁·x₂·...·x_n и y₁·y₂·...·y_m, мы можем сравнить log(x₁·x₂·...·x_n) и log(y₁·y₂·...·y_n), что будет эквивалентно сравнению log(x₁) + log(x₂) + ... + log(x_n) и log(y₁) + log(y₂) + ... + log(y_m).

Таким образом для нахождения значения log(x₁) + log(x₂) + ... + log(x_n) для каждого креста мы можем аналогично хранить массивы частичных сумм для каждого с направлений и для каждой клетки (x, y) искать максимальное значение креста с центром в ней за O(1).

Итоговая асимптотика O(n²).

Code

#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#define MOD 1000000007
#define N 2005
using namespace std;
typedef unsigned int ll;
ll i,j,n,h,x,y,cur_h,k,dir;
ll pre[8][N][N];
double sums[8][N][N],ans,logs[N][N],lg2,lg3;
ll ansx,ansy,anssize,ansdir;
ll total;
ll directions[8][2] = {{-1,-1},{-1,1},{1,-1},{1,1},{1,0},{0,1},{-1,0},{0,-1}};
char a[N][N];
bool in_range(ll x)
{
	return (x >= 0 && x < n);
}
int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	lg2 = log(2);
	lg3 = log(3);
	cin >> n;
	for (i = 0; i < n; i++)
		scanf("%s",a[i]);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (a[i][j] == '3')
			   logs[i][j] = lg3;
			else if (a[i][j] == '2')
		 		 logs[i][j] = lg2;
	for (dir = 0; dir < 8; dir++)
	{
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				if (!in_range(i-directions[dir][0]) || !in_range(j-directions[dir][1]))
				{
					k = 0;
					ll d1 = directions[dir][0], d2 = directions[dir][1];
					for (x = i, y = j; in_range(x) && in_range(y); x += d1, y += d2)
					{
						if (a[x][y] != '0')
						{
						   k++;
						   if (x == i && y == j)
							  sums[dir][x][y] = logs[i][j];
						   else
							   sums[dir][x][y] = sums[dir][x-d1][y-d2] + logs[x][y];
			   			}
						else
						{
							sums[dir][x][y] = 0;
							k = 0;
						}
						pre[dir][x][y] = k;
					}
				}
	}
	ans = -1;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
		if (a[i][j] != '0')
		{
			ll tmp = n+5;
			for (k = 0; k < 4; k++)
				tmp = min(tmp, pre[k][i][j]);
			double val = logs[i][j];
			for (k = 0; k < 4; k++)
				val += sums[k][i+directions[k][0]*(tmp-1)][j+directions[k][1]*(tmp-1)] - sums[k][i][j];
			if (val > ans)
			{
				ans = val;
				ansx = i;
				ansy = j;
				anssize = tmp;
				ansdir = 0;
			}
			
			tmp = n+5;
			for (k = 4; k < 8; k++)
				tmp = min(tmp, pre[k][i][j]);
			val = logs[i][j];
			for (k = 4; k < 8; k++)
				val += sums[k][i+directions[k][0]*(tmp-1)][j+directions[k][1]*(tmp-1)] - sums[k][i][j];
			if (val > ans)
			{
				ans = val;
				ansx = i;
				ansy = j;
				anssize = tmp;
				ansdir = 4;
			}
		}
	total = a[ansx][ansy]-'0';
	for (k = ansdir; k < ansdir+4; k++)
	{
		for (i = 1; i < anssize; i++)
			total = (total*(a[ansx+directions[k][0]*i][ansy+directions[k][1]*i]-'0'))%MOD;
	}
	cout << total << endl;
	return 0;
}

Rev.	By	When	Δ	Comment
en9	Wild_Hamster	2016-06-01 22:49:36	111
ru6	Wild_Hamster	2016-06-01 22:47:18	133
en8	Wild_Hamster	2016-06-01 22:22:10	196
ru5	Wild_Hamster	2016-06-01 22:20:00	194
ru4	Wild_Hamster	2016-06-01 22:16:49	4042	Мелкая правка: 'oiler/spoiler
en7	Wild_Hamster	2016-06-01 22:14:18	4026
ru3	Wild_Hamster	2016-06-01 22:07:19	11918
en6	Wild_Hamster	2016-06-01 22:03:29	11650
en5	Wild_Hamster	2016-06-01 21:50:43	95
ru2	Wild_Hamster	2016-06-01 21:48:47	11	Мелкая правка: 'высоты$a_i%k$, тогда ' -
en4	Wild_Hamster	2016-06-01 21:47:02	4	Tiny change: 'till $a[i] MOD k$, so we ' -> 'till $a[i]$ $MOD$ $k$, so we '
en3	Wild_Hamster	2016-06-01 21:44:36	10
ru1	Wild_Hamster	2016-06-01 21:43:50	3370	Первая редакция перевода на Русский
en2	Wild_Hamster	2016-06-01 21:40:41	97
en1	Wild_Hamster	2016-06-01 21:39:09	3178	Initial revision (published)

History