University CodeSprint 3(to be filled in)

Chong Wang Lv6
  2017-10-04 22:23:10 2017-10-04 22:23:10 Created   2026-10-09 14:27:59 2026-10-09 14:27:59 Updated  

I competed in this contest during the October holiday. The first five problems felt easy, but I could not solve the sixth and only earned a few points with brute force.

After reading the editorial, I saw the sixth problem’s idea was something I had not considered. I learned from it, though it was not very difficult.

The seventh problem seemed to require a link-cut tree. I have not learned that yet, so I will return to it later.

Problem link

The first three problems were too straightforward to write about.

4.Bob’s Game

Given an $n * n$ grid with some unreachable cells and several kings, each king may move up, left, or up-left. It stops at the top-left corner. Determine the winner and the number of winning first moves.

Each king is independent, so compute every king’s Sprague–Grundy value and XOR them. Then check moves in $O(3n)$.

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
const int dx3[5] = { 0,-1,0,-1,0 };
const int dy3[5] = { 0,0,-1,-1,0 };
int sg(set<int>&v)
{
	repp(i, 0, 4)
	{
		if (v.find(i) == v.end())return i;
	}
	return -1;
}

int n;
char val[1005][1005];
int dp[1005][1005];

void solve()
{
	memset(dp, 0, sizeof(dp));
	sa(n);
	repp(i, 1, n)
	{
		scanf("%s", val[i] + 1);
		repp(j, 1, n)
		{
			if (i == 1 && j == 1)
			{
				dp[i][j] = 0;
				continue;
			}
			set<int>s;
			repp(k, 1, 3)
			{
				int nx = i + dx3[k];
				int ny = j + dy3[k];
				if (nx<1 || ny<1 || val[nx][ny] == 'X')continue;
				s.insert(dp[nx][ny]);
			}
			dp[i][j] = sg(s);
		}
	}
	int ans = 0;
	repp(i, 1, n)
	{
		repp(j, 1, n)
		{
			if (val[i][j] == 'K')ans ^= dp[i][j];
		}
	}
	if (ans)
	{
		printf("WIN ");
		int res = 0;
		repp(i, 1, n)
		{
			repp(j, 1, n)
			{
				if (val[i][j] == 'K')
				{
					int tmp = ans;
					tmp ^= dp[i][j];
					repp(k, 1, 3)
					{
						int nx = i + dx3[k];
						int ny = j + dy3[k];
						if (nx<1 || ny<1 || val[nx][ny] == 'X')continue;
						int t = tmp ^ dp[nx][ny];
						if (t == 0)res++;
					}
				}
			}
		}
		printf("%d\n", res);
	}
	else
	{
		puts("LOSE");
	}
}

5.Black White Tree

Given a black-and-white tree, cut a subtree so that the absolute difference between black and white vertices is maximised. Return that maximum and the possible root choices.

Assign black vertices 1 and white vertices -1; a subtree’s sum is the difference.

dp[x][1] is the largest difference when selecting this vertex; dp[x][0] is the largest difference when not selecting it.

After finding the branch with the largest difference, reroot there, search again, and select greedily.

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
int n;
int col[maxn];
vector<int> edge[maxn];
int dp[maxn][2], dp2[maxn][2];

vector<int>res1;
vector<int>res2;
void dfs(int x, int fa)
{
	dp[x][1] = col[x];

	dp2[x][1] = (col[x] == 1 ? -1 : 1);
	for (int i = 0; i<edge[x].size(); i++)
	{
		int nxt = edge[x][i];
		if (nxt == fa)continue;
		dfs(nxt, x);
		dp[x][1] += (dp[nxt][1]>0 ? dp[nxt][1] : 0);
		dp[x][0] = max(dp[x][0], dp[nxt][1]);
		dp[x][0] = max(dp[x][0], dp[nxt][0]);

		dp2[x][1] += (dp2[nxt][1]>0 ? dp2[nxt][1] : 0);
		dp2[x][0] = max(dp2[x][0], dp2[nxt][1]);
		dp2[x][0] = max(dp2[x][0], dp2[nxt][0]);
	}
	//if(dp[x][1]>0)res1.push_back(x);
	//if(dp2[x][1]>0)res2.push_back(x);
}

void dfs21(int x, int fa)
{
	res1.push_back(x);
	for (int i = 0; i<edge[x].size(); i++)
	{
		int nxt = edge[x][i];
		if (nxt == fa)continue;
		if (dp[nxt][1] <= 0)continue;
		dfs21(nxt, x);
	}
	//if(dp[x][1]>0)res1.push_back(x);
	//if(dp2[x][1]>0)res2.push_back(x);
}

void dfs22(int x, int fa)
{
	res2.push_back(x);
	for (int i = 0; i<edge[x].size(); i++)
	{
		int nxt = edge[x][i];
		if (nxt == fa)continue;
		if (dp2[nxt][1] <= 0)continue;
		dfs22(nxt, x);
	}
	//if(dp[x][1]>0)res1.push_back(x);
	//if(dp2[x][1]>0)res2.push_back(x);
}

void solve()
{
	sa(n);
	repp(i, 1, n)
	{
		sa(col[i]);
		if (col[i] == 0)col[i]--;
	}
	repp(i, 1, n - 1)
	{
		int x; int y;
		sa(x), sa(y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	int ans1 = 0, ans2 = 0;
	int p1 = 1, p2 = 1;
	dfs(1, -1);
	repp(i, 1, n)
	{
		if (dp[i][1]>ans1)
		{
			ans1 = dp[i][1];
			p1 = i;
		}
		if (dp2[i][1]>ans2)
		{
			ans2 = dp2[i][1];
			p2 = i;
		}
	}
	//DE(ans1)
	//DE(ans2)
	memset(dp, 0, sizeof(dp));
	memset(dp2, 0, sizeof(dp2));
	if (ans1>ans2)
	{
		dfs(p1, -1);
		dfs21(p1, -1);
		cout << ans1 << endl;
		cout << res1.size() << endl;
		rep(i, 0, res1.size())
		{
			if (i)cout << " ";
			cout << res1[i];
		}
		cout << endl;
	}
	else
	{
		dfs(p2, -1);
		dfs22(p2, -1);
		cout << ans2 << endl;
		cout << res2.size() << endl;
		rep(i, 0, res2.size())
		{
			if (i)cout << " ";
			cout << res2[i];
		}
		cout << endl;
	}
}

6.March of the King

On an $8 * 8$ chessboard, find a string of length 11 without revisiting any cell. Count the solutions.

$7^{11}$ is too large.

I had discussed this with others before: use meet-in-the-middle, hash the recorded paths, then apply inclusion–exclusion when counting.

7. Simple Tree Counting (to be added)

On this page
University CodeSprint 3(to be filled in)
  1. 4.Bob’s Game
  2. 5.Black White Tree
  3. 6.March of the King
  4. 7. Simple Tree Counting (to be added)