# AtCoder Beginner Contest 178 Tutorial

# Problem A - Not (opens new window)

Just output 1−x1-x, which takes O(1)O(1) time.

Code (Python 3)
x = int(input())
print(1 - x)
1
2

# Problem B - Product Max (opens new window)

At first glance, there seem to be many conditions. But after you realize that the maximum must be within the set {ac,ad,bc,bd}\{ac,ad,bc,bd\}, things become a lot easier.

Time complexity is O(1)O(1).

Code (Python 3)
a, b, c, d = map(int, input().split())
x = [a * c, a * d, b * c, b * d]
print(max(x))
1
2
3

# Problem C - Ubiquity (opens new window)

Simple inclusion-exclusion.

seq with both 0 and 9=all seq−seq without 0−seq without 9+seq without 0 or 9.\text{seq with both 0 and 9}=\text{all seq}-\text{seq without 0}-\text{seq without 9}+\text{seq without 0 or 9}.

So the answer equals to 10n−2⋅9n+8n10^n-2\cdot9^n+8^n.

Time complexity is O(log⁡n)O(\log n).

Code (Python 3)
mod = 1000000007


def fexp(x, y):
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = ans * x % mod
        x = x * x % mod
        y //= 2
    return ans


n = int(input())
ans = fexp(10, n) - 2 * fexp(9, n) + fexp(8, n)
ans %= mod
if ans < 0:
    ans += mod
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Problem D - Redistribution (opens new window)

Enumerate how many numbers there are.

For example, when there are kk numbers, we first take 2k2k out of nn, so now all numbers should be larger than or equal to 11, instead of 33. Then the problem becomes, how many ways there are, if we want to separate n−2kn-2k into kk numbers. This can be considered as insert k−1k-1 partitions into n−2k−1n-2k-1 positions, which is (n−2k−1k−1)n-2k-1\choose k-1.

Time complexity is O(n)O(n), if we consider that the calculation of factorials and their modulo inverses takes constant time.

Code (Python 3)
mod = 1000000007


def fexp(x, y):
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = ans * x % mod
        x = x * x % mod
        y //= 2
    return ans


fac = [1]
rev = [1]

for i in range(1, 2006):
    fac.append(fac[-1] * i % mod)
    rev.append(fexp(fac[-1], mod - 2))


def C(n, k):
    if n < k:
        return 0
    return fac[n] * rev[k] % mod * rev[n - k] % mod


def distribute(n, m):
    return C(n - 1, m - 1)


n = int(input())
if n < 3:
    print(0)
else:
    ans = 0
    parts = 1
    while n - parts * 2 >= 0:
        rest = n - parts * 2
        ans += distribute(rest, parts)
        ans %= mod
        parts += 1
    print(ans)
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

# Problem E - Dist Max (opens new window)

This is a well-known problem and solutions can be easily found on the Internet. However, what is more important is to grasp the essence of such problems.

Our target is to find max⁡∣xi−xj∣+∣yi−yj∣\max|x_i-x_j|+|y_i-y_j|. Brute force will not work because it takes O(N2)O(N^2) time which we cannot afford.

The key point is to expand absolute values. We should be aware that there is another definition of ∣x∣|x|, that is ∣x∣=max⁡{x,−x}|x|=\max\{x,-x\}.

So in this problem, we have

∣xi−xj∣+∣yi−yj∣=max⁡{xi−xj+yi−yj,xi−xj+yj−yi,xj−xi+yi−yj,xj−xi+yj−yi}|x_i-x_j|+|y_i-y_j|=\max\{x_i-x_j+y_i-y_j,x_i-x_j+y_j-y_i,x_j-x_i+y_i-y_j,x_j-x_i+y_j-y_i\}

Which can be further rearranged to

∣xi−xj∣+∣yi−yj∣=max⁡{xi+yi−(xj+yj),xi−yi−(xj−yj),−xi+yi−(−xj+yj),−xi−yi−(−xj−yj)}|x_i-x_j|+|y_i-y_j|=\max\{x_i+y_i-(x_j+y_j),x_i-y_i-(x_j-y_j),-x_i+y_i-(-x_j+y_j),-x_i-y_i-(-x_j-y_j)\}

Then we have

max⁡∣xi−xj∣+∣yi−yj∣=max⁡{max⁡(xi+yi−(xj+yj)),max⁡(xi−yi−(xj−yj)),max⁡(−xi+yi−(−xj+yj)),max⁡(−xi−yi−(−xj−yj))}\max|x_i-x_j|+|y_i-y_j|=\max\{\max(x_i+y_i-(x_j+y_j)),\max(x_i-y_i-(x_j-y_j)),\max(-x_i+y_i-(-x_j+y_j)),\max(-x_i-y_i-(-x_j-y_j))\}

Which can be easily done in O(N)O(N) time by storing maximum and minimum of each of the four forms.

If you have referred to a solution on the Internet, that is OK. But the important thing is to understand how this works. The simple expression ∣x∣=max⁡{x,−x}|x|=\max\{x,-x\} can help you in many more problems.

Code (C++)
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
const int d[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int main() {
  int n;
  cin >> n;
  vector<ll> lo(4, 1e12), hi(4, -1e12);
  for (int i = 0; i < n; ++i) {
    ll x, y;
    cin >> x >> y;
    for (int k = 0; k < 4; ++k) {
      ll result = x * d[k][0] + y * d[k][1];
      lo[k] = min(lo[k], result);
      hi[k] = max(hi[k], result);
    }
  }
  ll ans = 0;
  for (int k = 0; k < 4; ++k)
    ans = max(ans, hi[k] - lo[k]);
  cout << ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Problem F - Contrast (opens new window)

This problem is similar to CF1381C - Mastermind (opens new window).

First we need to handle the conflicting numbers. The strategy is based on swapping. We use a max-heap to store all conflicting numbers. Each time, we pick one from the top group xx, and one from the second top group yy, and put an xx at the yy's position, while putting a yy at the xx's position. There is only one exceptional case. If there are three groups left in the heap, and they all have only one position left, we should make a triplet swap, x→y,y→z,z→xx\rightarrow y,y\rightarrow z,z\rightarrow x.

After this, there can be at most one conflicting group left. We try to put all the nubmers of this group (not only the conflicting ones, considering the {1,2},{2,2}\{1,2\},\{2,2\} example, there is only one pair of conflicting 22, but we need to handle all 22s) into valid positions.

If this cannot be done, then this configuration has no solution.

After that, we can put the rest numbers (which cannot cause conflicts) into the rest positions.

Code (C++)
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n), cb(n + 1);
  vector<bool> taken(n);
  vector<vector<int>> ca(n + 1);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    ca[a[i]].emplace_back(i);
  }
  for (int i = 0; i < n; ++i) {
    cin >> b[i];
    cb[b[i]]++;
  }
  priority_queue<pair<int, int>> pq;
  for (int i = 1; i <= n; ++i) {
    int lo = min((int)ca[i].size(), cb[i]);
    if (lo)
      pq.emplace(lo, i);
  }
  while (pq.size() >= 2) {
    auto [cx, x] = pq.top();
    pq.pop();
    auto [cy, y] = pq.top();
    pq.pop();
    if (cx == 1 && pq.size() == 1) {
      auto [cz, z] = pq.top();
      pq.pop();
      int px = ca[x].back();
      int py = ca[y].back();
      int pz = ca[z].back();
      taken[px] = taken[py] = taken[pz] = true;
      b[px] = y;
      b[py] = z;
      b[pz] = x;
      ca[x].pop_back();
      ca[y].pop_back();
      ca[z].pop_back();
      cb[x]--;
      cb[y]--;
      cb[z]--;
    } else {
      int px = ca[x].back();
      int py = ca[y].back();
      taken[px] = taken[py] = true;
      b[px] = y;
      b[py] = x;
      ca[x].pop_back();
      ca[y].pop_back();
      cb[x]--;
      cb[y]--;
      if (cx > 1)
        pq.emplace(cx - 1, x);
      if (cy > 1)
        pq.emplace(cy - 1, y);
    }
  }
  int idx = 0;
  if (!pq.empty()) {
    auto [cx, x] = pq.top();
    pq.pop();
    while (cb[x]) {
      while (idx < n && (taken[idx] || a[idx] == x))
        idx++;
      if (idx >= n)
        break;
      b[idx] = x;
      cb[x]--;
      taken[idx] = true;
    }
    if (cb[x]) {
      cout << "No" << flush;
      return 0;
    }
  }
  vector<int> rest;
  for (int i = 1; i <= n; ++i)
    if (cb[i]) {
      for (int j = 0; j < cb[i]; ++j)
        rest.emplace_back(i);
    }
  idx = 0;
  for (int i : rest) {
    while (taken[idx])
      idx++;
    b[idx] = i;
    taken[idx] = true;
  }
  cout << "Yes" << endl;
  for (int i : b)
    cout << i << " ";
  cout << flush;
}
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