AtCoder Regular Contest 073

Chong Wang Lv6
  2017-05-06 10:34:44 2017-05-06 10:34:44 Created   2026-10-09 08:54:05 2026-10-09 08:54:05 Updated  

I did ARC073, but I haven’t done any questions in a long time. . . Why do I always feel that AtCoder’s questions are impossible to solve? Every time I solve them, they are so amazing. . .

C - Sentou

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n,t;
int val[maxn];
 
void solve()
{
	ll res = 0;
	sa(n),sa(t);
	sa(val[1]);
 
	repp(i,2,n)
	{
		sa(val[i]);
		if(val[i]>=val[i-1]+t)res+=t;
		else
		{
			res+=val[i]-val[i-1];
		}
	}
	res+=t;
	printf("%lld\n", res);
}

D - Simple Knapsack

The meaning of the question is that there are $N(N<=100)$ items, each item weighs $w(w<=10^9)$ and is worth $v(v<=10^9)$. You now have a backpack that can hold $W$, ask for the best value. Then there is an additional condition, the weight difference between $N$ items does not exceed $3$.

Can DP, the backpack status is $3*N$ at most.

Then you can do greedy for each weight (there are 4 types in total), and the worst complexity is ($\frac{N^4}{4}$).

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
int N, W;
int w[maxn], v[maxn];
vector<ll>val[10];
 
void solve()
{
	ll res = 0;
	sa(N), sa(W);
	ll ind;
	repp(i, 1, N)
	{
		sa(w[i]), sa(v[i]);
		if (i == 1)ind = w[i];
		val[w[i] - w[1]].push_back(v[i]);
	}
	rep(i, 0, 4)
	{
		sort(val[i].begin(), val[i].end(), greater<ll>());
	}
	ll s1 = 0, s2 = 0, s3 = 0, s4 = 0;
	ll ans = 0;
	for (int i = 0; i <= val[0].size(); )
	{
		s2 = 0;
		for (int j = 0; j <= val[1].size(); )
		{
			s3 = 0;
			for (int k = 0; k <= val[2].size();)
			{
				s4 = 0;
				for (int h = 0; h <= val[3].size();)
				{
					ll sum = 1LL * i*(ind)+1LL * j*(ind + 1) + 1LL * k*(ind + 2) + 1LL * h*(ind + 3);
					if (sum <= W)
					{
						ans = max(ans, s1 + s2 + s3 + s4);
					}
					h++;
					if (h >= 1&&h<=val[3].size())s4 += val[3][h - 1];
				}
				k++;
				if (k >= 1 && k <= val[2].size())s3 += val[2][k - 1];
			}
			j++;
			if (j >= 1 && j <= val[1].size())s2 += val[1][j - 1];
		}
		i++;
		if (i >= 1&&i<=val[0].size())s1 += val[0][i - 1];
	}
	printf("%lld\n", ans);
}

E - Ball Coloring

The meaning of the question is to give $2*N$ balls, in groups of two. One ball in a group is dyed red and the other is dyed blue. Each ball has a number. The product of the difference between the maximum and minimum number of all the red balls and the difference between the maximum and minimum number of the blue ball is the smallest. That is, the value of $(R_{max}-R_{min})*(B_{max}-B_{min})$ is the smallest.

How do I figure out this question E? It’s too difficult and I don’t know how to do it. . . I feel very frustrated every time I go to look at the solutions. . .

This $2*N$ ball will have $MAX、MIN$, so the final result will be two situations,

1.$R_{min}=MIN，B_{max}=MAX$, then this situation is very simple, let each pair of smaller ones be dyed with red balls, and the larger pair with blue balls.

  1. $R_{min}=MIN，R_{max}=MAX$, sort the smaller ones, and then continue to replace them with larger ones. Using monotonicity, I found that all situations can be traversed in this way. This approach is embarrassing. . .
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
int n;
pair<ll,ll>val[maxn];
multiset<ll>v1,v2;
 
void solve()
{
	sa(n);
	if(n==1)
	{
		puts("0");
		return;
	}
	repp(i,1,n)
	{
		int x,y;
		sa(x),sa(y);
		if(x>y)swap(x,y);//x<=y
		val[i].first = x;
		val[i].second = y;
		v1.insert(x);
		v2.insert(y);
	}
	sort(val+1,val+n+1);
	ll ans = 1LL*(*v1.rbegin()-*v1.begin())*(*v2.rbegin()-*v2.begin());
	repp(i,1,n)
	{
		v1.erase(v1.find(val[i].first));
		v2.erase(v2.find(val[i].second));
 
		v1.insert(val[i].second);
		v2.insert(val[i].first);
		ans = min(ans,1LL*(*v1.rbegin()-*v1.begin())*(*v2.rbegin()-*v2.begin()));
	}
	printf("%lld\n", ans);
}

F - Many Moves

Two robots, the starting positions are $A、B$, and then there are related commands, $x_{i}$, which requires that one robot must be at the position $x_{i}$, and then each time the robot reaches $x_{i}$, there will be a moving distance. What is the minimum moving distance after executing all the commands.

Question F has a very similar question on hackerrank, question link.

Let’s consider the most violent DP first. $dp[i][x][y]$ means that at the i-th command, a ball is at position $x$, a ball is at position $y$, and then transferred. Complexity $O(Q*N^2)$.

Then consider that when executing the $x[i]$ command, the position of a ball must be at $x[i-1]$, so just enumerate the position of another ball. This is the Hackerrank question. $O(Q*N)$.

The complexity is still not enough. Assuming you already know $dp[i-1][k]$, consider two transfer methods to $dp[i][k]$:

  1. Transfer from $x[i-1]$ and add $abs(x[i]-x[i-1])$ to all $dp[i][k]$.

2.$dp[i][x[i-1]]=min(dp[i-1][j]+abs(j-x[i])) {for \ j \ in \ range(1,N)}$, then take off $abs$, you will find two line segment trees, just maintain $dp[i-1][j]+j$ and $dp[i-1][j]-j$.

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
ll seq[maxn];
 
struct Segtree
{
	struct Node
	{
		ll val, add;
	};
	Node tree[maxn * 4];
	void modify_add_Node(int node, ll val)
	{
		tree[node].val += val;
		tree[node].add += val;
	}
	void pushup(int node)
	{
		tree[node].val = min(tree[node << 1].val, tree[node << 1 | 1].val);
	}
	void pushdown(int node)
	{
		if (tree[node].add)
		{
			modify_add_Node(node << 1, tree[node].add);
			modify_add_Node(node << 1 | 1, tree[node].add);
			tree[node].add = 0;
		}
	}
	void build(int l, int r, int node)
	{
		if (l == r)
		{
			tree[node].val = seq[l];
			tree[node].add = 0;
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, node << 1);
		build(mid + 1, r, node << 1 | 1);
		pushup(node);
	}
	void modify_add(int L, int R, int l, int r, int node, int val)
	{
		if (r < L || R < l) return;
		if (L <= l&&r <= R)
		{
			modify_add_Node(node, val);
			return;
		}
		pushdown(node);
		int mid = (l + r) >> 1;
		modify_add(L, R, l, mid, node << 1, val);
		modify_add(L, R, mid + 1, r, node << 1 | 1, val);
		pushup(node);
	}
	void modify_min(int pos, int l, int r, int node, ll val)
	{
		if (l == r)
		{
			tree[node].val = min(tree[node].val, val);
			return;
		}
		pushdown(node);
		int mid = (l + r) >> 1;
		if (pos <= mid) modify_min(pos, l, mid, node << 1, val);
		else modify_min(pos, mid + 1, r, node << 1 | 1, val);
		pushup(node);
	}
	ll query_min(int L, int R, int l, int r, int node)
	{
		if (r<L || R<l) return INF;
		if (L <= l&&r <= R) return tree[node].val;
		pushdown(node);
		int mid = (l + r) >> 1;
		return min(query_min(L, R, l, mid, node << 1), query_min(L, R, mid + 1, r, node << 1 | 1));
	}
	ll dfs(int l, int r, int node)
	{
		if (l == r) return tree[node].val + l;
		pushdown(node);
		int mid = (l + r) >> 1;
		return min(dfs(l, mid, node << 1), dfs(mid + 1, r, node << 1 | 1));
	}
}s,t;
 
int N, Q, A, B;
int x[maxn];
 
void solve()
{
	sa(N), sa(Q), sa(A), sa(B);
	repp(i, 1, Q)
	{
		sa(x[i]);
	}
	repp(i, 1, N)
	{
		seq[i] = INF;
	}
	seq[B] = -B;
	s.build(1, N, 1);
 
	seq[B] = B;
	t.build(1, N, 1);
 
	x[0] = A;
	repp(i, 1, Q)
	{
		ll tmp = min(s.query_min(1, x[i], 1, N, 1) + x[i], t.query_min(x[i], N, 1, N, 1) - x[i]);
 
		s.modify_add(1, N, 1, N, 1, abs(x[i] - x[i - 1]));
		t.modify_add(1, N, 1, N, 1, abs(x[i] - x[i - 1]));
 
		s.modify_min(x[i - 1], 1, N, 1, tmp - x[i - 1]);
		t.modify_min(x[i - 1], 1, N, 1, tmp + x[i - 1]);
	}
	ll ans = s.dfs(1, N, 1);
 
	printf("%lld\n", ans);
}
On this page
AtCoder Regular Contest 073
  1. C - Sentou
  2. D - Simple Knapsack
  3. E - Ball Coloring
  4. F - Many Moves