# AtCoder Beginner Contest 182 Tutorial

# Problem A - twiblr (opens new window)

Just output 2A+100−B2A+100-B. Time complexity is O(1)\mathcal{O}(1).

Code (Python 3)
a, b = map(int, input().split())
print(2 * a + 100 - b)
1
2

# Problem B - Almost GCD (opens new window)

Brute force. Time complexity is O(N⋅max⁡(a))\mathcal{O}(N\cdot\max(a)).

Code (Python 3)
n = int(input())
a = list(map(int, input().split()))
hi = 0
ans = 0
for i in range(2, max(a) + 1):
    cnt = 0
    for j in a:
        if j % i == 0:
            cnt += 1
    if cnt > hi:
        hi = cnt
        ans = i
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13

# Problem C - To 3 (opens new window)

A number can be divided by 33 if and only if the sum of its digits can be divided by 33.

  • N≡0mod3N\equiv0\mod 3, no digits need to be removed.
  • N≡1mod3N\equiv1\mod 3, first try to delete one digit that ≡1mod3\equiv1\mod3, then try to delete two digits that ≡2mod3\equiv2\mod3.
  • N≡2mod3N\equiv2\mod 3, first try to delete one digit that ≡2mod3\equiv2\mod3, then try to delete two digits that ≡1mod3\equiv1\mod3.

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

Code (Python 3)
s = input()
n = int(s)
if n % 3 == 0:
    print(0)
else:
    a = list(map(int, list(s)))
    c = [0] * 3
    for i in a:
        c[i % 3] += 1
    if c[n % 3] >= 1 and len(a) > 1:
        print(1)
    elif c[3 - n % 3] >= 2 and len(a) > 2:
        print(2)
    else:
        print(-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Problem D - Wandering (opens new window)

We can maintain the farthest position ansans, the current position pospos, the prefix sum sumsum, and the maximum of prefix sum hihi.

In each round, we first update sumsum, then update hihi. It is obvious that we can reach at most pos+hipos+hi in this round, so we will use it to update ansans, and then use pos+sumpos+sum to update pospos.

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

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

using namespace std;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  int a;
  ll ans = 0, hi = 0, sum = 0, pos = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a;
    sum += a;
    hi = max(hi, sum);
    ans = max(ans, pos + hi);
    pos += sum;
  }
  cout << ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Problem E - Akari (opens new window)

Just put all the light bulbs and the walls into the matrix, then do a 44-pass scan.

  • For each row, from left to right.
  • For each row, from right to left.
  • For each column, from top to bottom.
  • For each column, from bottom to top.

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

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

using namespace std;

int main() {
  int h, w, n, m;
  cin >> h >> w >> n >> m;
  int a, b, c, d;
  vector<vector<int>> mat(h, vector<int>(w));
  for (int i = 0; i < n; ++i) {
    cin >> a >> b;
    mat[a - 1][b - 1] = 1;
  }
  for (int i = 0; i < m; ++i) {
    cin >> c >> d;
    mat[c - 1][d - 1] = -1;
  }
  for (int i = 0; i < h; ++i) {
    bool light = false;
    for (int j = 0; j < w; ++j) {
      if (mat[i][j] == 1) {
        light = true;
      } else if (mat[i][j] == -1) {
        light = false;
      } else if (light)
        mat[i][j] = 2;
    }
    light = false;
    for (int j = w - 1; j >= 0; --j) {
      if (mat[i][j] == 1) {
        light = true;
      } else if (mat[i][j] == -1) {
        light = false;
      } else if (light)
        mat[i][j] = 2;
    }
  }
  for (int j = 0; j < w; ++j) {
    bool light = false;
    for (int i = 0; i < h; ++i) {
      if (mat[i][j] == 1) {
        light = true;
      } else if (mat[i][j] == -1) {
        light = false;
      } else if (light)
        mat[i][j] = 2;
    }
    light = false;
    for (int i = h - 1; i >= 0; --i) {
      if (mat[i][j] == 1) {
        light = true;
      } else if (mat[i][j] == -1) {
        light = false;
      } else if (light)
        mat[i][j] = 2;
    }
  }
  int ans = 0;
  for (int i = 0; i < h; ++i)
    for (int j = 0; j < w; ++j)
      ans += mat[i][j] > 0;
  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
51
52
53
54
55
56
57
58
59
60
61
62
63

# Problem F - Valid payments (opens new window)

Actually we need to find the number of tuples {ki}\{k_i\} that satisfy

∑kiai=x\sum k_ia_i=x

and

∀ki,âˆŖkiaiâˆŖ<ai+1\forall k_i, |k_ia_i| < a_{i+1}

We can choose from left to right. It is easy to see that, we only need to store each state that can be reached, and the corresponding number of ways. We do not need to store the detailed coefficients.

Since ai+1a_{i+1} is a multiple of aia_i, so after we determine kik_i, we need to ensure that the current sum can be divided by ai+1a_{i+1}. On the other hand, according to the constraint âˆŖkiaiâˆŖ<ai+1|k_ia_i| < a_{i+1}, we only have two choices for each state.

We start from {x,1}\{x,1\}. It seems that there will be exponentional states, but actually, there are at most two states at any time. So the total time complexity is O(N)\mathcal{O}(N).

# Example

a=[1,3,12,36,108],x=190a=[1,3,12,36,108],\ x=190

The states in each step are:

  • (190,1)â€Ļoriginal(190,1)\dots\text{original}
  • (189,1),(192,1)(189,1),(192,1)
  • (180,1),(192,2)(180,1),(192,2)
  • (180,3),(216,2)(180,3),(216,2)
  • (108,3),(216,5)(108,3),(216,5)
  • (0,8)â€Ļterminal(0,8)\dots\text{terminal}

As we can see from the example, after each step, all states must be divided by ai+1a_{i+1} (for the last step, the only valid state is 00). Also, the states cannot change more than ai+1a_{i+1}, e.g., in the first step, we can only go from 190190 to 189189 or 192192, which are the nearest number that can be divided by a1=3a_1=3 to the left and to the right. We cannot go any further because that means we will go more than 33, and thus violates the rule that both people use the minimum number of coins (because we can use the 33-Yen coin instead of the 11-Yen coin).

Illustration

We can also see that, the span is either 00 or exactly ai+1a_{i+1} for each step.

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

using namespace std;
typedef long long ll;

int main() {
  int n;
  ll x;
  cin >> n >> x;
  vector<ll> a(n);
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  unordered_map<ll, ll> v;
  v[x] = 1;
  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    unordered_map<ll, ll> nv;
    for (auto [c, f] : v) {
      if (i + 1 < n) {
        ll rem = c % a[i + 1];
        nv[c - rem] += f;
        if (rem > 0)
          nv[c + a[i + 1] - rem] += f;
      } else {
        if (c % a[i] == 0)
          nv[0] += f;
      }
    }
    v = move(nv);
  }
  cout << v[0];
}
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