Codeforces 418 Div2

Chong Wang Lv6
  2017-06-16 09:24:32 2017-06-16 09:24:32 Created   2026-10-09 09:10:07 2026-10-09 09:10:07 Updated

Problem link

A An abandoned sentiment from past

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
int n,k;
int val[maxn],b[maxn];
void solve()
{
	sa(n),sa(k);
	if(k>1)
	{
		puts("Yes");
		return;
	}
	repp(i,1,n)
	{
		sa(val[i]);
	}
	repp(i,1,k)
	{
		sa(b[i]);
	}

	int left=-1,right=205;
	val[0]=-1;
	val[n+1]=205;
	int pre=-1;
	repp(i,1,n)
	{
		if(val[i]==0)
		{
			left=val[i-1];
			right=val[i+1];
			continue;
		}
		if(val[i]<=pre)
		{
			puts("Yes");
			return;
		}
		pre=val[i];
	}
	if(left<b[1]&&b[1]<right)
	{
		puts("No");
	}
	else
	{
		puts("Yes");
	}
}

B An express train to reveries

Given two sequences $(n<1000)$, find a sequence that differs from each of them in exactly one element.

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
int n;
int a[maxn], b[maxn];
int ans[maxn];
int vis[maxn];

void solve()
{
	sa(n);
	repp(i, 1, n)sa(a[i]);
	repp(i, 1, n)sa(b[i]);

	repp(i, 1, n)ans[i] = a[i];

	int p[2] = { 0,0 };
	repp(i, 1, n)
	{
		if (vis[a[i]] == 0)
		{
			vis[a[i]] = i;
		}
		else
		{
			p[0] = vis[a[i]];
			p[1] = i;
		}
	}

	repp(i, 0, 1)
	{
		int f = 0;
		repp(k, 1, n)
		{
			ans[p[i]] = k;
			memset(vis, 0, sizeof(vis));
			int flag = 0;
			repp(g, 1, n)
			{
				if (vis[ans[g]] == 0)
				{
					vis[ans[g]] = g;
				}
				else
				{
					flag = 1;
					break;
				}
			}
			if (flag)continue;
			repp(g, 1, n)
			{
				flag += (ans[g] != b[g]);
			}
			if (flag == 1)
			{
				f = 1;
				break;
			}
		}
		if (f)break;
		ans[p[i]] = a[p[i]];
	}
	repp(i, 1, n)
	{
		if (i>1)printf(" ");
		printf("%d", ans[i]);
	}
}

C An impassioned circulation of affection

Given a string of length $n<1500$ and $q<200000$ queries $(m_i,c_i)$, each query allows changing $m_i$ characters. Find the longest contiguous segment of character $c_i$.

Since $n * q$ is around $10^8$, there is a brute-force solution.

I used preprocessing plus DP and spent a long time debugging it. So silly.

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
int n;
char val[maxn];
int res[26][2000];
int dp[1501][1501];
int num[2000], pre[2000];

void solve()
{
	sa(n);
	scanf("%s", val + 1);
	repp(i, 2, n)
	{
		if (val[i] == val[i - 1])num[i] = num[i - 1] + 1;
		else num[i] = 1;
	}
	repp(v, 0, 25)
	{
		int va = 'a' + v;
		memset(dp, 0, sizeof(dp));//dp[pos][k] max_value

		repp(g, 1, n)
		{
			if (val[g] == va)
			{
				if (val[g - 1] == va)
				{
					dp[g][0] = dp[g - 1][0] + 1;
				}
				else
				{
					dp[g][0] = 1;
				}
			}
		}

		repp(k, 1, n)//number
		{
			res[v][k] = k;

			memset(pre, 0, sizeof(pre));

			int p = -1;
			repp(g, 1, n)
			{
				if (val[g] == va)
				{
					pre[g] = p;
					p = g;
				}
				else
				{
					pre[g] = p;
				}
			}
			repp(pos, 1, n)
			{
				dp[pos][k] = min(pos, k);
				res[v][k] = max(res[v][k], dp[pos][k]);
			}
			repp(pos, k + 1, n)
			{
				int dis = 0;
				if (pre[pos] == -1)
				{
					if (val[pos] == va)
					{
						dp[pos][k] = max(dp[pos][k], dp[pos - 1][k] + 1);
					}
					res[v][k] = max(res[v][k], dp[pos][k]);
					continue;
				}
				else
				{
					dis = pos - pre[pos];
					if (val[pos] == va)
					{
						dp[pos][k] = max(dp[pos][k], dp[pos - 1][k] + 1);
					}
					else
					{

						dp[pos][k] = max(dp[pos][k], dp[pos - 1][k - 1] + 1);
					}
				}
				res[v][k] = max(res[v][k], dp[pos][k]);
	
			}
		}
	}

	int q;
	sa(q);
	char x[5];
	repp(i, 1, q)
	{
		int tmp;
		scanf("%d%s", &tmp, x);
		//if(tmp>n)tmp=n;
		printf("%d\n", res[x[0] - 'a'][tmp]);
	}
}

In fact, preprocessing can be done directly as follows.

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
scanf("%d%s", &n, s + 1);
memset(ans, 0, sizeof(ans));
for(char ch = 'a'; ch <= 'z'; ch++)
{
  for(int i = 1; i <= n; i++)
  {
    int now = 0;
    for(int j = i; j <= n; j++)
    {
      now += (s[j] != ch);
      ans[ch - 'a'][now] = max(ans[ch - 'a'][now], j - i + 1);
    }
  }
  for(int i = 1; i <= n; i++)
    ans[ch - 'a'][i] = max(ans[ch - 'a'][i], ans[ch - 'a'][i - 1]);
}
inputnum(q);
int m;
char ch;
for(int i = 1; i <= q; i++)
{
  inputnum(m);
  ch = inputchar();
  while(ch < 'a' || ch > 'z')
    ch = inputchar();
  printf("%d\n", ans[ch - 'a'][m]);
}

D An overnight dance in discotheque

Divide $n$ circles into two groups. If a circle is contained an even number of times within a group, subtract its area. Find the maximum total area.

Apply greediness starting with the circle of greatest area.

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
int n;
struct no
{
	int x, y, r;
	int id;
}node[maxn];

bool cmp(no &a, no &b)
{
	return a.r>b.r;
}
int c1, c2;
int val1[maxn], val2[maxn];

bool in(int a, int b)
{
	double dis = sqrt((1.0*node[a].x - node[b].x)*(1.0*node[a].x - node[b].x) + (1.0*node[a].y - node[b].y)*(1.0*node[a].y - node[b].y));
	double d = node[a].r;
	return d >= dis;
}

void solve()
{
	sa(n);
	repp(i, 1, n)
	{
		int x, y, r;
		sa(node[i].x);
		sa(node[i].y);
		sa(node[i].r);
		node[i].id = i;
	}
	sort(node + 1, node + n + 1, cmp);
	for (int i = 1; i <= n; i++)
	{
		int flag = 0;
		repp(k1, 1, c1)
		{
			if (in(val1[k1], i))
			{
				flag = 1;
			}
		}
		if (flag == 0)
		{
			c1++;
			val1[c1] = i;
			continue;
		}

		flag = 0;
		repp(k1, 1, c2)
		{
			if (in(val2[k1], i))
			{
				flag = 1;
			}
		}
		if (flag == 0)
		{
			c2++;
			val2[c2] = i;
		}
		else
		{
			c1++;
			val1[c1] = i;
		}
	}


	double ans = 0;
	repp(k, 1, c1)
	{
		int cnt = 0;
		for (int j = 1; j<k; j++)
		{
			if (in(val1[j], val1[k]))
			{
				cnt++;
			}
		}
		if (cnt & 1)ans -= PI*node[val1[k]].r*node[val1[k]].r;
		else ans += PI*node[val1[k]].r*node[val1[k]].r;
	}

	repp(k, 1, c2)
	{
		int cnt = 0;
		for (int j = 1; j<k; j++)
		{
			if (in(val2[j], val2[k]))
			{
				cnt++;
			}
		}
		if (cnt & 1)ans -= PI*node[val2[k]].r*node[val2[k]].r;
		else ans += PI*node[val2[k]].r*node[val2[k]].r;
	}
	printf("%.8lf\n", ans);
}

E An unavoidable detour for home

Given $n<50$ vertices with prescribed degrees of 2 or 3, construct a tree rooted at 1 such that:

  1. Every vertex’s shortest distance $len_i$ from 1 is fixed, and that path is unique.

  2. For $i>2$, $len_i > len_{i-1}$.

Because every vertex’s distance to the root is fixed and unique, enumerate possibilities by level.

dp[a][b][c][d] represents a state in which the previous level has a vertices with one free edge and b with two, while this level has c with one free edge and d with two. The rest is state transition.

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
int n;
int d[55];
ll dp[2][55][55][55][55];

void solve()
{
	sa(n);
	repp(i, 1, n)
	{
		sa(d[i]);
	}
	dp[0][d[1] == 2][d[1] == 3][d[2] == 2][d[2] == 3] = 1;
	int now = 0, nxt = 1;
	for (int i = 2; i < n; i++)
	{
		for (int h = 0; h <= i; h++)
		{
			for (int j = 0; j + h <= i; j++)
			{
				for (int k = 0; k + j + h <= i; k++)
				{
					for (int le = 0; le + k + j + h <= i; le++)
					{
						if (dp[now][h][j][k][le] == 0)continue;
						if (h == 0 && j == 0)
						{
							if (k || le)
							{
								dp[now][k][le][0][0] += dp[now][h][j][k][le];
								dp[now][k][le][0][0] %= mod;
							}
							continue;
						}
						if (d[i + 1] == 2)
						{
							if (h)
							{
								dp[nxt][h - 1][j][k + 1][le] += dp[now][h][j][k][le] * h;
								dp[nxt][h - 1][j][k + 1][le] %= mod;

								if (k)
								{
									dp[nxt][h - 1][j][k - 1][le] += dp[now][h][j][k][le] * h*k%mod;
									dp[nxt][h - 1][j][k - 1][le] %= mod;
								}
								if (le)
								{
									dp[nxt][h - 1][j][k+1][le - 1] += dp[now][h][j][k][le] * h*le%mod;
									dp[nxt][h - 1][j][k+1][le - 1] %= mod;
								}
							}
							if (j)
							{
								dp[nxt][h + 1][j - 1][k + 1][le] += dp[now][h][j][k][le] * j;
								dp[nxt][h + 1][j - 1][k + 1][le] %= mod;

								if (k)
								{
									dp[nxt][h + 1][j - 1][k - 1][le] += dp[now][h][j][k][le] * j*k%mod;
									dp[nxt][h + 1][j - 1][k - 1][le] %= mod;
								}
								if (le)
								{
									dp[nxt][h + 1][j - 1][k + 1][le - 1] += dp[now][h][j][k][le] * j*le%mod;
									dp[nxt][h + 1][j - 1][k + 1][le - 1] %= mod;
								}
							}
						}
						else
						{
							if (h)
							{
								dp[nxt][h - 1][j][k][le + 1] += dp[now][h][j][k][le] * h%mod;
								dp[nxt][h - 1][j][k][le + 1] %= mod;

								if (k)
								{
									dp[nxt][h - 1][j][k][le] += dp[now][h][j][k][le] * h*k;
									dp[nxt][h - 1][j][k][le] %= mod;
								}
								if (le)
								{
									dp[nxt][h - 1][j][k + 2][le - 1] += dp[now][h][j][k][le] * h*le%mod;
									dp[nxt][h - 1][j][k + 2][le - 1] %= mod;
								}
								if (k >= 2)
								{
									dp[nxt][h - 1][j][k - 2][le] += dp[now][h][j][k][le] * h*k*(k - 1) / 2 % mod;
									dp[nxt][h - 1][j][k - 2][le] %= mod;
								}
								if (le >= 2)
								{
									dp[nxt][h - 1][j][k + 2][le - 2] += dp[now][h][j][k][le] * h*le*(le - 1) / 2 % mod;
									dp[nxt][h - 1][j][k + 2][le - 2] %= mod;
								}
								if (k&&le)
								{
									dp[nxt][h - 1][j][k][le - 1] += dp[now][h][j][k][le] * h*k*le;
									dp[nxt][h - 1][j][k][le - 1] %= mod;
								}
							}
							if (j)
							{
								dp[nxt][h+1][j - 1][k][le + 1] += dp[now][h][j][k][le] * j%mod;
								dp[nxt][h+1][j - 1][k][le + 1] %= mod;

								if (k)
								{
									dp[nxt][h+1][j - 1][k][le] += dp[now][h][j][k][le] * j*k%mod;
									dp[nxt][h+1][j-1][k][le] %= mod;
								}
								if (le)
								{
									dp[nxt][h+1][j - 1][k + 2][le - 1] += dp[now][h][j][k][le] * j*le%mod;
									dp[nxt][h+1][j-1][k + 2][le - 1] %= mod;
								}
								if (k >= 2)
								{
									dp[nxt][h+1][j - 1][k - 2][le] += dp[now][h][j][k][le] * j*k*(k - 1) / 2 % mod;
									dp[nxt][h+1][j - 1][k - 2][le] %= mod;
								}
								if (le >= 2)
								{
									dp[nxt][h + 1][j - 1][k + 2][le - 2] += dp[now][h][j][k][le] * j*le*(le - 1) / 2 % mod;
									dp[nxt][h + 1][j - 1][k + 2][le - 2] %= mod;
								}
								if (k&&le)
								{
									dp[nxt][h + 1][j - 1][k][le - 1] += dp[now][h][j][k][le] * j*k*le;
									dp[nxt][h + 1][j - 1][k][le - 1] %= mod;
								}
							}
						}
					}
				}
			}
		}
		swap(now, nxt);
		memset(dp[nxt], 0, sizeof(dp[nxt]));
	}

	printf("%lld\n", dp[now][0][0][0][0]);
}

On this page
Codeforces 418 Div2
  1. A An abandoned sentiment from past
  2. B An express train to reveries
  3. C An impassioned circulation of affection
  4. D An overnight dance in discotheque
  5. E An unavoidable detour for home