Codeforces 416 Div2

Chong Wang Lv6
  2017-05-30 13:06:20 2017-05-30 13:06:20 Created   2026-10-09 14:29:21 2026-10-09 14:29:21 Updated

How did Codeforces get to Round 416 already? That was fast.

A short record of this Div. 2 round.

Problem link

A. Vladik and Courtesy

A direct simulation of the statement is enough.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int a,b;
void solve()
{
	cin>>a>>b;

	int cnt=1;
	int sum=1;
	while(true)
	{
		if(cnt)
		{
			if(a>=sum)
			{
				a-=sum;
			}
			else
			{
				puts("Vladik");
				return;
			}
		}
		else
		{
			if(b>=sum)
			{
				b-=sum;
			}
			else
			{
				puts("Valera");
				return;
			}
		}
		sum++;
		cnt=1-cnt;
	}
}

B.Vladik and Complicated Book

Given $10^4$ numbers and $10^4$ queries, each query asks whether the value at a specified position changes after sorting a given interval.

A normal sort times out; use counting sort or compare relative order instead.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int n, m;
int val[maxn];
int cnt[maxn];
int v[maxn];

void solve()
{
	sa(n), sa(m);
	repp(i, 1, n)
	{
		sa(val[i]);
	}
	repp(i, 1, m)
	{
		int le, ri, x;
		sa(le), sa(ri), sa(x);

		int minn = 1e5, maxx = 0;
		repp(k, le, ri)
		{
			cnt[val[k]]++;
			maxx = max(maxx, val[k]);
			minn = min(minn, val[k]);
		}
		int st = minn;
		repp(i, le, ri)
		{
			while (cnt[st] == 0)st++;
			cnt[st]--;
			v[i] = st;
		}
		if (v[x] == val[x])
		{
			puts("Yes");
		}
		else
		{
			puts("No");
		}
	}
}

C.Vladik and Memorable Trip

Given $n$ numbers ($n < 5000$), choosing a value requires choosing the entire interval that contains that value. Find the maximum XOR sum over all chosen intervals.

Compute the interval for each value, then use DP.

1
2
dp[ri] = max(dp[ri], dp[le - 1] + sum);
dp[i] = max(dp[i], dp[i - 1]);

To compute each value’s interval, keep extending it until it no longer grows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
int n;
int val[maxn];
int vis[maxn];
ll dp[maxn];

int rig[maxn], lef[maxn];

void solve()
{
	sa(n);
	repp(i, 1, n)
	{
		sa(val[i]);
	}
	repp(i, 1, n)
	{
		int le = i;
		int ri = i;
		repp(k, 1, n)
		{
			if (val[i] == val[k])
			{
				le = min(le, k);
				ri = max(ri, k);
			}
		}
		rig[val[i]] = ri;
		lef[val[i]] = le;
	}

	repp(i, 1, n)
	{
		int le = lef[val[i]];
		int ri = rig[val[i]];

		int newle = le;
		int newri = ri;
		repp(k, le, ri)
		{
			newle = min(newle, lef[val[k]]);
			newri = max(newri, rig[val[k]]);
		}
		if (newle == le&&newle == ri)
		{

		}
		else
		{
			while (true)
			{
				int ple = le, pri = ri;
				le = newle, ri = newri;
				repp(k, newle, ple)
				{
					newle = min(newle, lef[val[k]]);
					newri = max(newri, rig[val[k]]);
				}

				repp(k, pri, newri)
				{
					newle = min(newle, lef[val[k]]);
					newri = max(newri, rig[val[k]]);
				}
				if (newle == le&&newri == ri)
				{
					break;
				}
				else
				{
					le = newle;
					ri = newri;
				}
			}
		}

		int sum = 0;
		repp(k, le, ri)
		{
			if (vis[val[k]])continue;
			sum ^= val[k];
			vis[val[k]] = 1;
		}
		dp[ri] = max(dp[ri], dp[le - 1] + sum);
		dp[i] = max(dp[i], dp[i - 1]);
		repp(k, le, ri)
		{
			vis[val[k]] = 0;
		}
	}
	ll ans = 0;
	repp(i, 1, n)
	{
		ans = max(ans, dp[i]);
	}
	printf("%lld\n", ans);
}

D. Vladik and Favorite Game

An interactive problem. Starting at $(1,1)$, navigate a robot to a given target. The “Up” and “Down” controls may be reversed, as may “Left” and “Right”. The board contains traps, and landing on one loses the game.

Because $(1,1)$ is the upper-left corner, one control mapping can be determined immediately. While moving along the boundary, the other can also be determined. Then a straightforward BFS/DFS works.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
int n, m;
char val[maxn][maxn];
int step[maxn][maxn];
char v[5] = { ' ','U','R','D','L' };

void bfs(int x,int y)
{
	memset(step, -1, sizeof(step));
	queue< pair<int, int> > que;
	que.push(mp(x, y));
	step[x][y] = n*m;
	while (!que.empty())
	{
		pair<int, int> now = que.front();
		que.pop();

		int x = now.first;
		int y = now.second;

		repp(k, 1, 4)
		{
			int nx = x + dx4[k];
			int ny = y + dy4[k];
			if ((val[nx][ny] == '.')&& step[nx][ny] == -1)
			{
				step[nx][ny] = step[x][y] - 1;
				que.push(mp(nx, ny));
			}
		}
	}
}

void dfs(int x, int y)
{
	if (val[x][y] == 'F')return;
	int dir = 1;
	int px, py;
	repp(k, 1, 4)
	{
		int nx = x + dx4[k];
		int ny = y + dy4[k];
		if (step[nx][ny] == step[x][y] + 1)
		{
			px = nx;
			py = ny;
			dir = k;
			break;
		}
	}
	printf("%c\n", v[dir]);
	fflush(stdout);

	int newx, newy;
	sa(newx), sa(newy);
	if (newx == px && newy == py)
	{
		dfs(newx, newy);
	}
	else
	{
		if (dir == 1 || dir == 3)
		{
			swap(v[1], v[3]);
		}
		else
		{
			swap(v[2], v[4]);
		}
		dfs(x, y);
	}
}

void solve()
{
	sa(n), sa(m);
	repp(i, 1, n)
	{
		scanf("%s", val[i] + 1);
	}
	int px = 1, py = 1;
	repp(i, 1, n)
	{
		repp(j, 1, m)
		{
			if (val[i][j] == 'F')
			{
				px = i;
				py = j;
			}
		}
	}
	bfs(px, py);
	dfs(1, 1);
}

E.Vladik and Entertaining Flags

Given an $n \times m$ grid ($n < 10$, $m < 10^5$) of numbers and $q$ queries, each query covers a vertical slice of the grid and asks for the number of connected regions of equal numbers.

I could not solve this one at the time.

The solution is a segment tree containing disjoint-set structures. Since $n < 10$, each segment can record the component memberships of values on both boundaries; when merging, unite equal colors on the right boundary of the left segment and the left boundary of the right segment.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
int n, m, q;
int val[15][maxn];

struct DSU
{
	int fa[maxn];
	void init(int n)
	{
		for (int i = 0; i <= n; i++)
		{
			fa[i] = i;
		}
	}
	int find(int x)
	{
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}
	int uni(int x, int y)
	{
		x = find(x);
		y = find(y);
		if (x == y)return 0;
		if (x<y)swap(x, y);
		fa[x] = y;
		return 1;
	}
}dsu;
vector<int>tmp[42];
struct node
{
	int le, ri;
	int ans;
	int col[55];
	void init()
	{
		ans = 2 * n;
		dsu.init(2 * n);
		for (int i = 1; i <= n; i++)
		{
			ans -= dsu.uni(i, i + n);
		}
		for (int i = 2; i <= n; i++)
		{
			if (val[i][le] == val[i-1][le])
			{
				ans -= dsu.uni(i, i - 1);
			}
		}
		for (int i = 1; i <= n; i++)
		{
			col[i] = col[i + n] = dsu.find(i);
		}
	}
	node operator +(const node &other)
	{
		node res;
		res.le = le;
		res.ri = other.ri;

		res.ans = ans + other.ans;

		for (int i = 1; i <= n; i++)
		{
			dsu.fa[i] = col[i];
			dsu.fa[i + n] = col[i + n];
			dsu.fa[i + 2 * n] = other.col[i] + 2 * n;
			dsu.fa[i + 3 * n] = other.col[i + n] + 2 * n;
		}

		for (int i = 1; i <= n; i++)
		{
			if (val[i][ri] == val[i][other.le])
			{
				res.ans -= dsu.uni(i + n, i + 2 * n);
			}
		}
		for (int i = 0; i <= 40; i++)
		{
			tmp[i].clear();
		}
		for (int i = 1; i <= n; i++)
		{
			tmp[dsu.find(i)].push_back(i);
			tmp[dsu.find(i + 3 * n)].push_back(i + n);
		}
		for (int i = 0; i <= 40; i++)
		{
			for (int k = 0; k < tmp[i].size(); k++)
			{
				res.col[tmp[i][k]] = tmp[i][0];
			}
		}
		return res;
	}
}no[4 * maxn];

void build(int root, int le, int ri)
{
	if (le == ri)
	{
		no[root].le = no[root].ri = le;
		no[root].init();
		return;
	}
	int mid = (ri + le) / 2;
	build(root << 1, le, mid);
	build(root << 1 | 1, mid + 1, ri);
	no[root] = no[root << 1] + no[root << 1 | 1];
}

node query(int root, int le, int ri)
{
	if (no[root].le == le&&no[root].ri == ri)
	{
		return no[root];
	}
	int mid = (no[root].le + no[root].ri) / 2;
	if (ri <= mid)return query(root << 1, le, ri);
	if (le > mid)return query(root << 1 | 1, le, ri);
	return query(root << 1, le, mid) + query(root << 1 | 1, mid + 1, ri);
}


void solve()
{
	sa(n), sa(m), sa(q);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			scanf("%d", &val[i][j]);
		}
	}
	build(1, 1, m);
	repp(i, 1, q)
	{
		int x, y;
		sa(x), sa(y);
		node res = query(1, x, y);
		printf("%d\n", res.ans);
	}
}

int main()
{

	solve();
	//system("pause");
	return 0;
}
On this page
Codeforces 416 Div2
  1. A. Vladik and Courtesy
  2. B.Vladik and Complicated Book
  3. C.Vladik and Memorable Trip
  4. D. Vladik and Favorite Game
  5. E.Vladik and Entertaining Flags