# Codeforces Round 666 (CF1396) Tutorial
# Div. 2 Problem A - Juggling Letters (opens new window)
Just count the number of every letter, and check whether every number can be divided by .
Code (Python 3)
from sys import stdin, stdout
def read_int():
return int(stdin.readline().strip())
t = read_int()
for case_num in range(t):
n = read_int()
counter = [0 for _ in range(26)]
for i in range(n):
s = stdin.readline().strip()
for c in s:
counter[ord(c) - ord('a')] += 1
ok = True
for count in counter:
if count % n != 0:
ok = False
break
stdout.write('YES\n' if ok else 'NO\n')
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Div. 2 Problem B - Power Sequence (opens new window)
First sort the array in ascending order, then enumerate . We can constrain the range of by , otherwise we can simply change all to and that will cost less.
Code (Python 3)
from sys import stdin, stdout
def read_int():
return int(stdin.readline().strip())
def read_ints():
return map(int, stdin.readline().strip().split(' '))
n = read_int()
a = list(read_ints())
a.sort()
s = sum(a)
cost = s - n
j = 2
while pow(j, n - 1) <= s * 2:
b = [1]
for k in range(n - 1):
b.append(b[-1] * j)
tot = sum([abs(a[i] - b[i]) for i in range(n)])
cost = min(cost, tot)
j += 1
print(cost)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Problem A - Multiples of Length (opens new window)
We can make use of the fact that and are coprime. First we operate on whose length is , then we operate on whose length is also . After two operations, we can make all numbers divided by . Finally we operate on whose length is , and we can just add to each ( may have changed after the previous operations).
Note that is an edge case.
Code (C++)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve() {
int n;
read(n);
vector<ll> a(n);
for (int i = 0; i < n; ++i)
read(a[i]);
if (n == 1) {
printf("1 1\n%lld\n1 1\n1\n1 1\n-1\n", -a[0]);
return;
}
printf("1 %d\n", n - 1);
for (int i = 0; i < n - 1; ++i) {
ll r = (a[i] % n + n) % n;
a[i] += r * (n - 1);
printf("%lld ", r * (n - 1));
}
printf("\n2 %d\n", n);
for (int i = 1; i < n; ++i) {
ll r = (a[i] % n + n) % n;
a[i] += r * (n - 1);
printf("%lld ", r * (n - 1));
}
printf("\n1 %d\n", n);
for (ll num : a)
printf("%lld ", -num);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}
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
# Problem B - Stoned Game (opens new window)
If , then T can always win. He can just take stones from the largest pile, while HL can only take from the rest piles. Since , there is definitely a time when HL has no stone to take after T takes a stone.
Otherwise, , then both players can avoid with the following strategy:
- If the maximum pile is currently available, just take from it
- Otherwise, it means that the maximum pile has just been taken, so we have . No matter which pile we take a stone from, we will have afterwards.
So the winner depends on the parity of stones. If the total number of stones is odd, then T wins, otherwise HL wins.
Code (C++)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve() {
int n;
read(n);
vector<int> a(n);
int sum = 0, hi = 0;
for (int i = 0; i < n; ++i) {
read(a[i]);
sum += a[i];
hi = max(hi, a[i]);
}
if (hi > sum - hi) {
printf("T\n");
return;
}
printf(sum % 2 == 0 ? "HL\n" : "T\n");
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
# Problem C - Monster Invaders (opens new window)
First, let's consider one level. We have two ways to clear all monsters:
- Kill the boss with one shot. We use pistol to kill all normal monsters, then use AWP to kill the boss. The total time cost is .
- Kill the boss with two shots. We can use pistol to kill all normal monsters, and then attack the boss once. Or we can use the laser gun to kill all normal monsters while damaging the boss at the same time. Then we are forced to leave. The next time we reach this level, we use pistol again to kill the boss. If we only consider the time spent on reloading, the total time cost is .
Now we can consider the general route. Let's reflect on where we shall end.
Supposing we end at , our best choice should be like the figure above. That is to say, we first come to , then we go to the other end and go back to . Otherwise we will spend extra time on teleportation.
So we can divide the total time cost into three parts. The time cost of , the time cost of and the time cost of moving from to which is .
Let be the minimal time to clear and stop at level , be the minimal time to clear and stop at level , our final answer would be
In order to avoid edge cases, we can let .
Then we need to solve and .
is special, because there are no further levels. We can choose to kill all monsters in , or use the teleportation twice and spend . For rest , since we need to go from to and then go back to , so we must have passed level twice. So the total time cost is
Then we will consider . For , we have two strategies.
- Not going back. We go from level to level then kill all monsters, using .
- Going back. We take the route . Since we have passed level and twice, we can use both and , and and .
Comparing the two strategies, we will have
Why don't we consider going back further?
Consider route .
It can be rearranged to , and the length does not change. Moreover, both routes pass level , and at least twice. So these two routes come to the same optimal value. The second part of the rearranged route is just what we have considered (), yet the first part of the rearranged route () is no better than so we do not need to consider it.
We can then use the formula we come to earlier to calculate the final answer.
Code (C++)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
struct Node {
ll time = 0;
int idx = 0, left = 0;
bool operator<(const Node &other) const { return time > other.time; }
};
public:
void solve() {
ll n, r1, r2, r3, d;
read(n), read(r1), read(r2), read(r3), read(d);
vector<ll> a(n + 1), kill_all(n + 1), leave_one(n + 1);
for (int i = 1; i <= n; ++i) {
read(a[i]);
kill_all[i] = r1 * a[i] + r3;
leave_one[i] = min(r2, r1 * (a[i] + 1)) + r1;
}
vector<ll> L(n + 2), R(n + 2);
R[n] = min(kill_all[n], leave_one[n] + d * 2);
for (int i = n - 1; i >= 1; --i)
R[i] = R[i + 1] + d * 2 + min(kill_all[i], leave_one[i]);
ll cost = R[1];
L[0] = R[n + 1] = -d;
for (int i = 1; i <= n; ++i) {
L[i] = L[i - 1] + d + min(kill_all[i], leave_one[i] + d * 2);
if (i >= 2)
L[i] = min(L[i], L[i - 2] + d * 4 +
min(kill_all[i - 1], leave_one[i - 1]) +
min(kill_all[i], leave_one[i]));
cost = min(cost, L[i] + R[i + 1] + d);
}
cout << cost;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}
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
# Problem D - Rainbow Rectangles (opens new window)
Not yet.
# Problem E - Distance Matching (opens new window)
First we want to find when the problem has no answer.
Considering , we can conclude that all possible values have the same parity, since they share the part, while the second part is always even.
Now let's turn to the perspective of edges. We randomly choose a root, then for each non-root node, we consider the edge from its parent to it. We define to be the size of the subtree rooted at . Then the edge can be counted at most times (we try to make as many pairs as we can from nodes in the subtree to the outer nodes). Meanwhile, it will be counted at least times (we try to make as many pairs as we can in its subtree). For this part, see also CF1280C - Jeremy Bearimy (opens new window).
So we have found the lowered bound and the upper bound . And we have known its parity must conform to that of and . If , or 's parity is different from 's, the problem has no answer.
Can we definitely find a valid answer if and is even?
Yes, we can, based on the strategy below.
We will consider how many nodes in each subtree (except the root tree) are cross matched (matched with an external node). The upper limit for each subtree has been calculated in the last step, which equals to . We use binary search to find the minimal global upper bound which will be applied to all subtrees, so that
and
both hold. Note that the part is added so that the parity can be kept.
Since we need , further modification is required. Here we only modify those nodes with to , until the updated sum meets the requirement. Since is the minimal possible value to make , it is ensured that we can meet the requirement within finite steps, otherwise will also make , which contradicts with the premise.
Now that we have constructed all , how can we ensure that a valid matching can be made based on it? Let's consider an invalid configuration instead. In an invalid configuration, there must be a node where , but this case has been excluded via the global upper bound.
Since we already have a valid configuration, we now need to implement it.
We will use another DFS, and handle the deepest subtrees first, because a cross match for a deeper subtree will finally become an internal match at a higher level. For each subtree, we deal with its internal matches. Note that all sub-subtrees of current subtree will have no more internal matches, since that has been handled earlier, so we must match a node in one sub-subtree with a node in another sub-subtree. To achieve that, we will use a set
to store the current number of unmatched nodes in every sub-subtree (the root of the current subtree is also considered a sub-subtree with a single element). Every time, we choose one node from the largest group, and one node from the second largest group, then make them a pair. We repeat this until the number of internally matched nodes has met our configuration. Since all remaining unmatched nodes will be handled outside the current subtree, they will be cross matched just as we have expected.
We still have a few finishing touches. We need to collect all unmatched nodes in the sub-subtrees and put them into the list of the current subtree. There is a trick in this step: we need to always merge a shorter vector into a longer one, in order to save time.
This solution is from jiangly (opens new window).
Code (C++, based on jiangly's solution)
#include <cstdio>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
vector<vector<int>> adj, to_match;
vector<int> size, cross_match;
void dfs(int u, int p) {
size[u] = 1;
for (int v : adj[u])
if (v != p) {
dfs(v, u);
size[u] += size[v];
}
}
void match_in_subtree(int u, int p) {
int remain = 1;
to_match[u].emplace_back(u);
set<pair<int, int>, greater<>> s;
s.emplace(1, u);
for (int v : adj[u])
if (v != p) {
match_in_subtree(v, u);
remain += to_match[v].size();
s.emplace(to_match[v].size(), v);
}
int internal_match = remain - cross_match[u];
while (internal_match) {
int first = s.begin()->second;
s.erase(*s.begin());
int second = s.begin()->second;
s.erase(*s.begin());
printf("%d %d\n", to_match[first].back(), to_match[second].back());
to_match[first].pop_back();
to_match[second].pop_back();
if (!to_match[first].empty())
s.emplace(to_match[first].size(), first);
if (!to_match[second].empty())
s.emplace(to_match[second].size(), second);
internal_match -= 2;
}
for (int v : adj[u])
if (v != p) {
// Insert the shorter vector after the longer vector.
if (to_match[v].size() > to_match[u].size())
swap(to_match[v], to_match[u]);
to_match[u].insert(to_match[u].end(), to_match[v].begin(),
to_match[v].end());
}
}
public:
void solve() {
int n;
ll k;
read(n), read(k);
adj = vector<vector<int>>(n + 1);
size = vector<int>(n + 1);
cross_match = vector<int>(n + 1);
for (int i = 0; i < n - 1; ++i) {
int u, v;
read(u), read(v);
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
dfs(1, 0);
ll lo = 0, hi = 0;
for (int i = 2; i <= n; ++i) {
lo += size[i] % 2;
hi += cross_match[i] = min(size[i], n - size[i]);
}
if (k < lo || k > hi || (k - lo) % 2 != 0) {
printf("NO");
return;
}
printf("YES\n");
int l = 0, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
ll score = 0;
for (int i = 2; i <= n; ++i) {
if (cross_match[i] >= mid)
score += mid + (cross_match[i] - mid) % 2;
else
score += cross_match[i];
}
if (score >= k)
r = mid - 1;
else
l = mid + 1;
}
int &limit = l;
ll score = 0;
for (int i = 2; i <= n; ++i) {
if (cross_match[i] >= limit)
cross_match[i] = limit + (cross_match[i] - limit) % 2;
score += cross_match[i];
}
// Currently score >= k, we need to make score = k;
for (int i = 2; i <= n; ++i)
if (cross_match[i] == limit + 1 && score > k) {
score -= 2;
cross_match[i] -= 2;
}
to_match = vector<vector<int>>(n + 1);
match_in_subtree(1, 0);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}
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