AtCoder Grand Contest 001

Chong Wang Lv6
  2016-07-20 21:49:49 2016-07-20 21:49:49 Created   2026-10-09 08:58:53 2026-10-09 08:58:53 Updated

Last weekend I did AtCoder Grand Contest 001 organized by rng_58. The English solution is here. During the competition, I only answered two questions, and I kept struggling with the second question. As a result, I ran out of time for the third question, and the blogger was relatively weak. . . . Later, I slowly made up the questions and found that D E F were all very cool questions. . . Let’s write down a summary here.

A BBQ Easy

The meaning of the question is to give 2*n lengths, and each two together, the length of these two is calculated as the shorter of the two, and then the total maximum length is calculated.

Sort directly and add up the odd digits to get the total maximum length.

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
#include <iostream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
#define eps 1e-10
#define LL_INF 0x33ffffffffffffff
#define INF 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define sa(n) scanf("%d", &(n))
#define mp make_pair
#define ff first
#define ss second
#define pb push_back

const int maxn = 405;
const ll mod = 1000000007;
const double PI = acos(-1.0);
 
int n;
int val[maxn];
 
void solve()
{
	int res = 0;
	int i, j, k;
	for(i = 1;i <= 2*n; i++)
	{
		sa(val[i]);
	}
	sort(val + 1, val + 2*n + 1);
	for (i = 1; i <= 2 * n - 1; i = i + 2)
	{
		res += val[i];
	}
	printf("%d\n", res);
}
int main()
{
	while (scanf("%d", &n) != EOF)
	{
		solve();
	}
	return 0;
}

B Mysterious Light

Question B is more interesting. It is an equilateral triangle with length n. A beam of light is emitted from position x. It will be reflected when it encounters an edge. It will also be reflected when it encounters its own path. Ask about the distance traveled by this beam of light.

You will find that this beam of light is traveling inside a parallelogram, and this parallelogram is getting smaller and smaller as it goes. Set the side lengths to a, b (a>b). If you continue walking, the parallelogram will become b, a%b. So, write a recursive calculation to calculate the distance traveled by the current parallelogram.

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
#include <iostream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
#define eps 1e-10
#define LL_INF 0x33ffffffffffffff
#define INF 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define sa(n) scanf("%d", &(n))
#define mp make_pair
#define ff first
#define ss second
#define pb push_back

 
const int maxn = 405;
const ll mod = 1000000007;
const double PI = acos(-1.0);
 
ll n, x;
 
ll cal(ll n, ll x)
{
	if (x <= 0)
	{
		return 3 * n;
	}
	if (n % x == 0 )
	{
		return n * 3LL;
	}
	else
	{
		return n / x*x * 3LL + cal(x, n%x);
	}
}
 
void solve()
{
	ll res = 0;
	if (x * 2LL >= n)
	{
		res = cal(x, n - x);
	}
	else
	{
		res = cal(n - x, x);
	}
	printf("%lld\n", res);
}
int main()
{
	while (cin >> n >> x)
	{
		solve();
	}
	return 0;
}

C Shorten Diameter

The meaning of the question is to give a tree and require the longest path in the tree to be k. To ask at least how many points must be deleted to meet the requirements.

The total number of n is only 1000. You can directly search whether k is an odd number or an even number. If k is an odd number, then search according to the edge. Each point can be at most (k-1)/2. If k is an even number, then search according to points, up to k/2 in each direction.

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
#include <iostream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
#define eps 1e-10
#define LL_INF 0x33ffffffffffffff
#define INF 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define sa(n) scanf("%d", &(n))
#define mp make_pair
#define ff first
#define ss second
#define pb push_back

const int maxn = 500005;
const ll mod = 998244353;
const double PI = acos(-1.0);
 
int n, k;
vector<int>edge[maxn];
int u[maxn], v[maxn];
 
int dfs(int x, int fa, int dis)
{
	int res = (dis<0);
	int sz = edge[x].size();
 
	int k = 0;
	int i,j;
	for(i=0;i<sz;i++)
	{
		k = edge[x][i];
		if (k == fa)continue;
 
		res += dfs(k, x, dis - 1);
	}
	return res;
}
 
void solve()
{
	sa(n), sa(k);
	int i, j;
 
	for(i=1;i<=n-1;i++)
	{
		sa(u[i]), sa(v[i]);
		edge[u[i]].push_back(v[i]);
		edge[v[i]].push_back(u[i]);
	}
 
	int res = n;
 
	if ((k & 1) == 0)
	{
		for(i=1;i<=n;i++)
		{
			res = min(res, dfs(i, -1, k / 2));
		}
	}
	else
	{
		for(i=1;i<=n-1;i++)
		{
			res = min(res, dfs(u[i], v[i], (k - 1) / 2) + dfs(v[i], u[i], (k - 1) / 2));
		}
	}
	printf("%d\n", res);
}
 
int main()
{
	solve();
	return 0;
}

D Arrays and Palindrome

The meaning of the question is very confusing. There are two arrays a and b. The sum of the elements of array a and the sum of the elements of array b are both n.

There is a string of length n. If the following conditions (1) (2) are met, then the third condition can be derived:

(1) The first a1 characters, the next a2 characters, and the next a3 characters. . . . They are all palindromes.

(2) The first b1 characters, the next b2 characters, and the next b3 characters. . . . They are all palindromes.

(3) Every character in this string is equal.

Then given an arrangement of the a array, you need to find the a array and the b array.

This question is amazing to me. . .

It can be found that when the a array has only one element {x}, then the b array {x-1,1} can meet the conditions.

D_1

And similarly, when there are two numbers, {x, y} becomes {x-1, y+1} to meet the question requirements.

D_2

My feeling when doing this is that when the block is an odd number, the point in the middle is not connected, so when there are many odd blocks, it should not work. How much more? If the number of odd-numbered blocks exceeds two, the question requirement will not be met.

Proof: Suppose a has X odd elements and the string length is N, then the number of edges connecting two points is (N-X)/2, b has Y odd elements, and the number of edges connecting two points is (N-Y)/2. Then, because they must be equal to each other, the number of edges must be at least N-1, so we have (N-X)/2 + (N-Y)/2 >= N-1 deduces that

In this way, the remaining situation is to add 1 and subtract 1. If there are 2 odd numbers, put them on both sides.

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <iostream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
 
typedef long long ll;
#define eps 1e-10
#define LL_INF 0x3fffffffffffffff
#define INF 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define sa(n) scanf("%d", &(n))
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
 
const int maxn = 1e5 + 5;
const ll mod = 998244353;
const double PI = acos(-1.0);
 
int n, m;
int val[maxn];
 
void solve()
{
	int i, j, k;
	sa(n), sa(m);
 
	vector<int>odd;
	vector<int>even;
	for(i=1;i<=m;i++)
	{
		sa(val[i]);
		if (val[i] & 1)
		{
			odd.push_back(val[i]);
		}
		else
		{
			even.push_back(val[i]);
		}
	}
	if (n == 1)
	{
		printf("1\n");
		printf("1\n");
		printf("1\n");
	}
	else
	{
		int od_sz = odd.size();
		int ev_sz = even.size();
 
		if (od_sz > 2)
		{
			puts("Impossible");
		}
		else
		{
			if (od_sz == 0)
			{
				for(i=0;i<ev_sz-1;i++)
				{
					printf("%d ", even[i]);
				}
				printf("%d\n", even[ev_sz - 1]);
 
				printf("%d\n", ev_sz + 1);
				printf("1 ");
				for(i=0;i<ev_sz-1;i++)
				{
					printf("%d ", even[i]);
				}
				printf("%d\n", even[ev_sz - 1] - 1);
			}
			else if (od_sz == 1)
			{
				if (ev_sz == 0)
				{
					printf("%d\n", odd[0]);
					printf("2\n");
 
					printf("%d %d\n", odd[0] - 1, 1);
				}
				else
				{
					printf("%d ", odd[0]);
					for(i=0;i<ev_sz-1;i++)
					{
						printf("%d ", even[i]);
					}
					printf("%d\n", even[ev_sz - 1]);
					printf("%d\n", m);
 
					printf("%d ", odd[0] + 1);
					for(i=0;i<ev_sz-1;i++)
					{
						printf("%d ", even[i]);
					}
					printf("%d\n", even[ev_sz - 1] - 1);
				}
			}
			else if (od_sz == 2)
			{
				if (ev_sz == 0)
				{
					if (odd[0] == 1 && odd[1] == 1)
					{
						printf("1 1\n");
						printf("1\n");
						printf("2\n");
					}
					else
					{
						sort(odd.begin(), odd.end());
						printf("%d %d\n", odd[0], odd[1]);
						printf("2\n");
						printf("%d %d\n", odd[0] + 1, odd[1] - 1);
					}
				}
				else
				{
					printf("%d ", odd[0]);
					for(i=0;i<ev_sz;i++)
					{
						printf("%d ", even[i]);
					}
					printf("%d\n", odd[1]);
 
					vector<int>r;
					r.push_back(odd[0] + 1);
					for(i=0;i<ev_sz;i++)
					{
						r.push_back(even[i]);
					}
					if (odd[1] - 1)
					{
						r.push_back(odd[1] - 1);
					}
					printf("%d\n", r.size());
					int sz = r.size();
					for(i=0;i<sz;i++)
					{
						if (i == sz-1)
						{
							printf("%d\n", r[i]);
						}
						else
						{
							printf("%d ", r[i]);
						}
					}
				}
			}
		}
	}
}
 
int main()
{
	 solve();
	 return 0;
}

E BBQ Hard

The meaning of the question is to give N packs, each pack has A beef and B pepper. Pick two packs from N and put them together, and ask how many ways to put them together. Assuming that what is taken out is Ai+Aj, Bi+Bj, then the placement type of this portion is:

$$\frac{(A{i}+A{j}+B{i}+B{j})!}{(A{i}+A{j})!*(B{i}+B_{j})!}$$

Then assume that this function is f(x,y), that is:

$$f(x,y)=\frac{(x+y)!}{x!*y!}$$

So I discovered something, this function is equal to the number of squares moved. E_1

That is, how many ways are there if walking from coordinate (0,0) to coordinate (x,y) can only go up or to the right. For f(Ai+Aj,Bi+Bj), it means walking from coordinates (0,0) to coordinates (Ai+Aj,Bi+Bj), that is, (-Ai,-Bi) walking to (Aj,Bj). Then in this case, you can ask for help from DP.

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
#include <iostream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pill;
 
#define eps 1e-10
#define LL_INF 0x3fffffffffffffff
#define INF 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define sa(n) scanf("%d", &(n))
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
 
const int maxn = 4e3 + 5;
const ll mod = 1e9+7;
const double PI = acos(-1.0);
 
int n;
int u[200005],v[200005];
ll fac[2*maxn],infac[2*maxn];
ll cnt[maxn][maxn];
 
ll po(ll x,ll y)
{
	ll res=1;
	while(y)
	{
		if(y&1)
		{
			res =(res*x)%mod;
		}
		x=x*x%mod;
		y=y>>1;
	}
	return res;
}
 
void init()
{
	int i,j,k;
	
	fac[0]=1;
	
	for(i=1;i<=8000;i++)
	{
		fac[i]=(fac[i-1]*i)%mod;
		infac[i]=po(fac[i],mod-2);
	}
}
 
ll cal(int x,int y)
{
	return ((fac[x+y]*infac[x])%mod*infac[y])%mod;
}
 
void solve()
{
	int i,j,k;
	
	memset(cnt,0,sizeof(cnt));
 
	for(i=1;i<=n;i++)
	{
		sa(u[i]),sa(v[i]);
		cnt[2000-u[i]][2000-v[i]]++;
	}
	for(i=0;i<=4000;i++)
	{
		for(j=0;j<=4000;j++)
		{
			if(i>0)
			{
				cnt[i][j] = (cnt[i][j]+cnt[i-1][j])%mod;
			}
			if(j>0)
			{
				cnt[i][j] = (cnt[i][j]+cnt[i][j-1])%mod;
			}
		}
	}
	ll r=0;
	for(i=1;i<=n;i++)
	{
		r = (r+cnt[2000+u[i]][2000+v[i]])%mod;
		r = ((r-cal(2*u[i],2*v[i]))%mod+mod)%mod;
	}
	r = (r*po(2,mod-2))%mod;
	printf("%lld\n",r);
}
 
int main()
{
    init();
    while(scanf("%d",&n)!=EOF)
    {
    	solve();
    }
    return 0;
}

F Wide Swap

The meaning of question F is that a permutation P from 1 to n is given, and then two subscripts i and j are given. When j-i>=k, and |Pj-Pi|=1, the two elements can be exchanged, and the permutation that achieves the lexicographic minimum of the given permutation is asked.

Consider an arrangement Q, Q[P[i]]=i, then the above conditions can be converted into when Qj-Qi>=k and adjacent, the two elements can be exchanged. In this way, you will find that when Oj-Qi<k, the relative positions of the two elements are fixed. The problem is converted into a graph. When Qj-Qi<k, there is an edge from Qj to Qi, and then find the minimum topological sequence of this edge.

The topological sequence part of the graph can be optimized using priority queues. The problem lies in building edges. For an element, we want to find the nearest element around it that meets the requirements to build an edge. We use a line segment tree to do it. The value that meets the conditions is the value of its position. See the code for details.

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <fstream>
#include <iostream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
 
typedef long long ll;
#define eps 1e-10
#define LL_INF 0x33ffffffffffffff
#define INF 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define sa(n) scanf("%d", &(n))
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
 
const int maxn = 500005;
const ll mod = 998244353;
const double PI = acos(-1.0);
 
struct no
{
	int le;
	int ri;
	int max_v;
}node[4 * maxn];
 
void build(int root, int le, int ri, int v)
{
	if (le == ri)
	{
		node[root].le = le;
		node[root].ri = ri;
		node[root].max_v = v;
		return;
	}
	int mid = (le + ri) >> 1;
	build(root << 1, le, mid, v);
	build((root << 1) | 1, mid + 1, ri, v);
	node[root].le = le;
	node[root].ri = ri;
	node[root].max_v = v;
}
 
int query(int root, int le, int ri)
{
	if (node[root].le == le&&node[root].ri == ri)
	{
		return node[root].max_v;
	}
	int mid = (node[root].le + node[root].ri) >> 1;
	if (mid >= ri)
	{
		return query(root << 1, le, ri);
	}
	else if (mid + 1 <= le)
	{
		return query(root << 1 | 1, le, ri);
	}
	else
	{
		return max(query(root << 1, le, mid), query(root << 1 | 1, mid + 1, ri));
	}
}
 
void update(int root, int k, int v)
{
	if (node[root].le == k&&node[root].ri == k)
	{
		node[root].max_v = v;
		return;
	}
	int mid = (node[root].le + node[root].ri) >> 1;
	if (k <= mid)
	{
		update(root << 1, k, v);
	}
	else
	{
		update(root << 1 | 1, k, v);
	}
	node[root].max_v = max(node[root << 1].max_v, node[root << 1 | 1].max_v);
}
 
int n, k;
int pos[maxn], out[maxn], res[maxn];
vector<int>ed[maxn];
priority_queue<int>que;
 
void solve()
{
	int i, j, m;
	sa(n), sa(k);
	for(i=1;i<=n;i++)
	{
		sa(m);
		pos[m] = i;
	}
	
	build(1, 1, n, -INF);
	for(i=1;i<=n;i++)
	{
		m = query(1, pos[i], min(n, pos[i] + k - 1));
		if (m != -INF)
		{
			int x = m;
			out[pos[x]]++;
			ed[pos[i]].push_back(pos[x]);
		}
		update(1, pos[i], i);
	}
 
	build(1, 1, n, -INF);
	for (i = n; i >= 1; i--)
	{
		m = query(1, pos[i], min(n, pos[i] + k - 1));
		if (m != -INF)
		{
			int x = -m;
			out[pos[i]]++;
			ed[pos[x]].push_back(pos[i]);
		}
		update(1, pos[i], -i);
	}
	
	for(i=1;i<=n;i++)
	{
		if (out[i] == 0)
		{
			que.push(i);
		}
	}
	for (i = n; i >= 1;i--)
	{
		int v = que.top();
		que.pop();
		res[v] = i;
		
		for(j=0;j<ed[v].size();j++)
		{
			out[ed[v][j]]--;
			if (out[ed[v][j]] == 0)
			{
				que.push(ed[v][j]);
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		printf("%d\n", res[i]);
	}
}
 
int main()
{
	solve();
	return 0;
}
On this page
AtCoder Grand Contest 001
  1. A BBQ Easy
  2. B Mysterious Light
  3. C Shorten Diameter
  4. D Arrays and Palindrome
  5. E BBQ Hard
  6. F Wide Swap