# AtCoder Beginner Contest 188 Editorial

Video Editorial (opens new window)

# Problem A - Three-Point Shot (opens new window)

Check if โˆฃXโˆ’Yโˆฃโ‰ค2|X-Y|\leq2.

Time complexity is O(1)\mathcal{O}(1).

Code (Python 3)
x, y = map(int, input().split())
print('Yes' if abs(x - y) <= 2 else 'No')
1
2

# Problem B - Orthogonality (opens new window)

Just calculate the inner product,

Time complexity is O(N)\mathcal{O}(N).

Code (Python 3)
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print('Yes' if sum(ai * bi for ai, bi in zip(a, b)) == 0 else 'No')
1
2
3
4

# Problem C - ABC Tournament (opens new window)

Find the maximum of the lower half and the upper half, and compare them. The index of the smaller value is the answer we need.

Time complexity is O(2N)\mathcal{O}(2^N).

Code (Python)
n = int(input())
a = list(map(int, input().split()))
half = 1 << (n - 1)
left_win = 0
for i in range(half):
    if a[i] > a[left_win]:
        left_win = i
right_win = half
for i in range(half, 1 << n):
    if a[i] > a[right_win]:
        right_win = i
if a[left_win] > a[right_win]:
    print(right_win + 1)
else:
    print(left_win + 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Problem D - Snuke Prime (opens new window)

TIP

Editorial for this problem has been completely rewritten.

Consider at first we have an infinite time span [0,+โˆž)[0,+\infty). The services will split the span into several non-overlapping segments. For example, if we have servcies [1,4][1,4] and [3,8][3,8], the final segments would be (note that we discard the leftmost segment, which should be [0,0][0,0] in this case):

[1,2],[3,4],[5,8],[9,+โˆž)[1,2],[3,4],[5,8],[9,+\infty)

Which can also be seen as:

[1,3),[3,5),[5,9),[9,+โˆž)[1,3),[3,5),[5,9),[9,+\infty)

To represent these segments, we only need their left endpoints, that is, 1,3,5,91,3,5,9. And these left endpoints come from either aia_i or bi+1b_i+1. This is because only the start or the end of a service will make a difference. A service [ai,bi][a_i,b_i] can also be seen as [ai,bi+1)[a_i,b_i+1), in which bi+1b_i+1 is the first day that is not included, which means it is a start of a new segment. On the aia_i-th day, the total cost will increase by cic_i, while on the bi+1b_i+1-th day, the total cost will decrease by cic_i.

After we get the segments, we need to calculate the cost for each segment, and compare it with CC, the price of the subscription. The time span of a segment can be easily determined from the start of the current segment and the start of the next segment.

To deal with the segments, we have two choices.

  1. (More overhead) We can discretize the endpoints and use a difference array to find the cost of each segment.
  2. (Clearer) We can use a map to store the change happening to the total cost on each critical day (aia_i or bi+1b_i+1, which is the start endpoint of a segment), then handle the segments one by one.

Both methods have a time complexity of O(NlogโกN)\mathcal{O}(N\log N), since in both cases we need a sorted list of the timestamps.

Code (C++, Discretization)
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
  int N;
  ll C;
  cin >> N >> C;
  vector<int> a(N), b(N), c(N);
  set<int> s;
  for (int i = 0; i < N; ++i) {
    cin >> a[i] >> b[i] >> c[i];

    // We only need a[i] and b[i]+1 to represent the final segments.
    // For example, [1, 4] and [3, 8] will make
    // [1, 2], [3, 4], [5, 8] and [9, +inf].
    // We need 1, 3, 5, and 9 to represent these segments.
    s.insert(a[i]), s.insert(b[i] + 1);
  }

  // Discretize the endpoints.
  int idx = 0;
  map<int, int> mp;
  for (int si : s)
    mp[si] = idx++;
  int M = s.size();
  vector<int> v(s.begin(), s.end());

  // Use a difference array to handle the services.
  vector<ll> diff(M);
  for (int i = 0; i < N; ++i)
    diff[mp[a[i]]] += c[i], diff[mp[b[i] + 1]] -= c[i];

  // Accumulate the difference array to get the value of each segment.
  // At the same time, add to the total cost.
  vector<ll> acc(M);
  acc[0] = diff[0];
  ll ans = 0;
  for (int i = 0; i < M - 1; ++i) {
    if (i >= 1)
      acc[i] = acc[i - 1] + diff[i];
    int span = v[i + 1] - v[i];
    ans += min(C, acc[i]) * span;
  }
  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
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
Code (C++, Map)
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
  int N;
  ll C;
  cin >> N >> C;
  vector<int> a(N), b(N), c(N);
  set<int> s;
  map<int, ll> changes;
  for (int i = 0; i < N; ++i) {
    cin >> a[i] >> b[i] >> c[i];

    // We only need a[i] and b[i]+1 to represent the final segments.
    // For example, [1, 4] and [3, 8] will make
    // [1, 2], [3, 4], [5, 8] and [9, +inf).
    // They can also be seen as [1, 3), [3, 5), [5, 9) and [9, +inf].
    // We need 1, 3, 5, and 9 to represent these segments.
    s.insert(a[i]), s.insert(b[i] + 1);

    // We use a map to store the change of cost on each critical day.
    changes[a[i]] += c[i];
    changes[b[i] + 1] -= c[i];
  }

  vector<int> v(s.begin(), s.end());
  int M = v.size();

  ll ans = 0, acc = 0;
  for (int i = 0; i < M - 1; ++i) {
    // Deal with the starting and ending of segments.
    acc += changes[v[i]];

    // Add to the total cost.
    ans += min(C, acc) * (v[i + 1] - v[i]);
  }
  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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# Problem E - Peddler (opens new window)

Do dynamic programming in a reverse order (from NN to 11).

Time complexity is O(N+M)\mathcal{O}(N+M).

Code (C++)
#include <iostream>
#include <vector>
#define MAXN 200005

using namespace std;

int main() {
  int N, M;
  cin >> N >> M;

  vector<int> A(N + 1);
  for (int i = 1; i <= N; ++i)
    cin >> A[i];

  vector<vector<int>> adj(N + 1);
  for (int i = 0; i < M; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].emplace_back(v);
  }

  vector<int> hi(N + 1, -1e9);
  int ans = -1e9;
  for (int i = N; i >= 1; --i) {
    for (int v : adj[i])
      hi[i] = max(hi[i], hi[v]);
    ans = max(ans, hi[i] - A[i]);
    hi[i] = max(hi[i], A[i]);
  }
  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
24
25
26
27
28
29
30
31

# Problem F - +1-1x2 (opens new window)

  • If Xโ‰ฅYX\geq Y, the answer if Xโˆ’YX-Y.
  • Otherwise, we use BFS to solve this problem. To reduce the number of states, we start from YY instead of XX. For each current value Yโ€ฒY', first try updating the answer with d+โˆฃYโ€ฒโˆ’Xโˆฃd+|Y'-X|. If Yโ€ฒ>XY'>X, then further consider the following cases:
    • If Yโ€ฒY' is even, use รท2\div2 (reverse of ร—2\times2)
    • Otherwise, use +1+1 or โˆ’1-1. Specially, if the steps of the front element is equal to or larger than the answer, we can stop the search.
Code (Python)
from collections import deque

X, Y = map(int, input().split())
if X >= Y:
    print(X - Y)
else:
    ans = Y - X
    dq = deque([(Y, 0)])
    vis = set([Y])
    while dq:
        u, d = dq.popleft()
        if d >= ans:
            break
        ans = min(ans, d + abs(u - X))
        if u <= X:
            continue
        if u % 2 == 0:
            if u // 2 not in vis:
                vis.add(u // 2)
                dq.append((u // 2, d + 1))
        else:
            if u + 1 not in vis:
                vis.add(u + 1)
                dq.append((u + 1, d + 1))
            if u - 1 not in vis:
                vis.add(u - 1)
                dq.append((u - 1, d + 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