Codeforces 417 Div2

Chong Wang Lv6
  2017-06-16 08:27:37 2017-06-16 08:27:37 Created   2026-10-09 09:09:56 2026-10-09 09:09:56 Updated

Problem link

A Sagheer and Crossroads

Every intersection has traffic lights and crossings. Determine whether a traffic accident can occur in the given configuration.

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
int val[50][50];
void solve()
{
	sa(val[1][4]);
	sa(val[1][3]);
	sa(val[1][2]);
	sa(val[1][1]);

	sa(val[2][1]);
	sa(val[2][4]);
	sa(val[2][3]);
	sa(val[2][2]);


	sa(val[3][2]);
	sa(val[3][1]);
	sa(val[3][4]);
	sa(val[3][3]);


	sa(val[4][3]);
	sa(val[4][2]);
	sa(val[4][1]);
	sa(val[4][4]);


	repp(i,1,4)
	{
		if(val[i][i])
		{
			repp(k,1,4)
			{
				if(i==k)continue;
				if(val[i][k])
				{
					puts("YES");
					return;
				}
			}
			repp(j,1,4)
			{
				if(i==j)continue;
				if(val[j][i])
				{
					//DE(j)
					//DE(i)
					puts("YES");
					return;
				}
			}
		}
	}
	puts("NO");
}

B Sagheer, the Hausmeister

A building has stairs on the left and right, with rooms in between. A person begins at the left staircase on the first floor and must switch off every room light. Find the minimum distance travelled, where $N<15$ floors and $M<100$ rooms per floor.

Dynamic programming is a little awkward because the final position is not necessarily on the top floor. The editorial simply brute-forces choices in $O(2^n * n)$.

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
int n, m;
char val[150][150];
int dp[150][2];

void solve()
{
	sa(n), sa(m);
	repp(i, 1, n)
	{
		scanf("%s", val[i] + 1);
	}
	//memset(dp,-1,sizeof(dp));
	int up = 0;
	repp(i, 1, n)
	{
		int flag = 0;
		for (int k = 1; k <= m + 2; k++)
		{
			if (val[i][k] == '1')
			{
				flag = 1;
			}
		}
		if (flag)
		{
			up = i;
			break;
		}
	}
	if (up == 0)
	{
		puts("0");
		return;
	}
	for (int i = n; i >= up; i--)
	{
		if (i == up)
		{
			int left = -1, right = -1;
			int cnt = 0;
			for (int k = 1; k <= m + 2; k++)
			{
				if (val[i][k] == '1')
				{
					right = k;
				}
			}
			for (int k = m + 2; k >= 1; k--)
			{
				if (val[i][k] == '1')
				{
					left = k;
				}
			}
			left = m + 2 - left;
			int res = dp[i + 1][0] + (right-1) + (up!=n);
			if(up!=n)res = min(res, dp[i + 1][1] + (left) + 1);
			printf("%d\n", res);
			return;
		}
		else if (i == n)
		{
			int p = 0;
			for (int k = 1; k <= m + 2; k++)
			{
				if (val[i][k] == '1')
				{
					p = k;
				}
			}
			if (p != 0)
			{
				dp[i][0] = (p - 1) * 2;
			}
			dp[i][1] = m + 1;
		}
		else
		{

			int left = -1, right = -1;
			int cnt = 0;
			for (int k = 1; k <= m + 2; k++)
			{
				if (val[i][k] == '1')
				{
					right = k;
				}
			}
			if (right == -1)
			{
				dp[i][0] = dp[i + 1][0] + 1;
				dp[i][0] = min(dp[i][0], dp[i + 1][1] + m + 2);
				dp[i][1] = dp[i + 1][1] + 1;
				dp[i][1] = min(dp[i][1], dp[i + 1][0] + m + 2);
				continue;
			}
			for (int k = m + 2; k >= 1; k--)
			{
				if (val[i][k] == '1')
				{
					left = k;
				}
			}
			left = m + 2 - left;
			dp[i][0] = dp[i + 1][0] + (right-1) * 2 + 1;
			dp[i][0] = min(dp[i][0], dp[i + 1][1] + m + 1 + 1);

			dp[i][1] = dp[i + 1][1] + (left) * 2 + 1;
			dp[i][1] = min(dp[i][1], dp[i + 1][0] + m + 1 + 1);
		}
	}
	puts("0");
}

C Sagheer and Nubian Market

Given $n$ items and total money $S$, each item’s price depends on the final number of items bought. Find the maximum number you can purchase.

Binary search.

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
ll n, S;
ll val[maxn];
ll v[maxn];
bool check(ll num)
{
	repp(i, 1, n)
	{
		v[i] = 1LL * val[i] + 1LL * i*num;
	}
	sort(v + 1, v + n + 1);

	int cnt = 0;
	ll sum = S;
	repp(i, 1, n)
	{
		if (sum >= v[i])
		{
			sum -= v[i];
			cnt++;
		}
		else
		{
			break;
		}
	}
	return cnt >= num;
}


void solve()
{
	scanf("%lld%lld", &n, &S);
	repp(i, 1, n)
	{
		scanf("%lld", &val[i]);
	}

	ll le = 0, ri = n;
	while (le<ri)
	{
		ll mid = (le + ri + 1) / 2;
		if (check(mid))
		{
			le = mid;
		}
		else
		{
			ri = mid - 1;
		}
	}
	printf("%lld ", le);
	if (le == 0)
	{
		printf("0");
		return;
	}
	repp(i, 1, n)
	{
		v[i] = 1LL * val[i] + 1LL * i*le;
	}
	sort(v + 1, v + n + 1);

	int cnt = 0;
	ll sum = S;
	repp(i, 1, le)
	{
		sum -= v[i];
	}
	printf("%lld", S - sum);
}

D Sagheer and Kindergarten

A kindergarten has $n$ children and $m$ toys. Children request toys over time. A child who receives every requested toy plays and then returns them; otherwise the child waits and makes no other requests. If some children can never receive their requested toys, they cry.

The first $k$ requests are given and guaranteed not to cause crying. For each of $q$ queries, add the final request and calculate how many children cry.

Treat every child as a vertex. Add an edge when one child waits for another child’s toy. Crying occurs exactly when a cycle appears.

For each query, check whether the two vertices are in the same tree. Use DFS order to determine the ancestor–descendant relationship.

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
int n,m,k,q;
int fa[maxn],who[maxn];
int in[maxn],out[maxn];
vector<int>edge[maxn];
int idx;

void dfs(int x,int fa)
{
	idx++;
	in[x]=idx;
	for(int i=0;i<edge[x].size();i++)
	{
		int nxt=edge[x][i];
		if(nxt==fa)continue;
		dfs(nxt,x);
	}
	out[x]=idx;
}

void solve()
{
	sa(n),sa(m),sa(k),sa(q);
	repp(i,1,k)
	{
		int x,y;
		sa(x),sa(y);
		if(who[y])
		{
			fa[x]=who[y];
		}
		who[y]=x;
	}
	repp(i,1,n)
	{
		edge[fa[i]].push_back(i);
	}
	idx=0;
	repp(i,1,n)
	{
		if(in[i]==0)
		{
			dfs(i,-1);
		}
	}
	repp(i,1,q)
	{
		int x,y;
		sa(x),sa(y);
		y=who[y];
		if(in[x]<=in[y]&&out[x]>=out[y])
		{
			printf("%d\n", out[x]-in[x]+1);
		}
		else
		{
			puts("0");
		}
	}
}

E Sagheer and Apple Tree

A tree has $p_i$ apples at every vertex. A player may either eat any number of apples at a leaf, or move any number from a parent to one child. The second player may swap the apple counts of two vertices once. Count the swaps that let the second player win.

Every leaf depth has the same parity. This is a staircase game on a tree; I do not know how to handle it when the parities differ.

XOR the values of vertices whose depth parity matches the leaves. If the result is $0$, the second player wins. To count swaps, enumerate one set and add the count of matching values in the other.

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 ans,res;
int n;
int maxx;
int val[maxn];
int dep[maxn];
vector<int>edge[maxn];
map<int,int>cnt[2];
int c0,c1;

void dfs(int x)
{
	for(int i=0;i<edge[x].size();i++)
	{
		int nxt=edge[x][i];
		dfs(nxt);
		dep[x]=max(dep[x],dep[nxt]+1);
	}
	maxx=max(maxx,dep[x]);
	cnt[dep[x]&1][val[x]]++;
	if(dep[x]&1)c1++;
	else c0++;
}

void solve()
{
	sa(n);
	repp(i,1,n)
	{
		sa(val[i]);
	}
	repp(i,2,n)
	{
		int x;
		sa(x);
		edge[x].push_back(i);
	}
	maxx=0;
	dfs(1);

	for(int i=1;i<=n;i++)
	{
		if(dep[i]%2==0)
		{
			//DE(val[i])
			ans^=val[i];
		}
	}
	//DE(maxx)
	//DE(ans)
	ll res=0;
	if(ans==0)
	{
		res+=1LL*c0*(c0-1)/2;
		res+=1LL*c1*(c1-1)/2;
	}
	for(int i=1;i<=n;i++)
	{
		if(dep[i]%2==0)
		{
			int tmp=ans^val[i];
			res+=cnt[1][tmp];
		}

	}
	printf("%lld\n", res);
}
On this page
Codeforces 417 Div2
  1. A Sagheer and Crossroads
  2. B Sagheer, the Hausmeister
  3. C Sagheer and Nubian Market
  4. D Sagheer and Kindergarten
  5. E Sagheer and Apple Tree