# AtCoder Beginner Contest 191 Editorial

# Problem A - Vanishing Pitch (opens new window)

To avoid dealing with floats, we can calculate the invisible range of distance instead. If DD falls within this range, then Aoki cannot hit the ball.

  • Time complexity is O(1)\mathcal{O}(1).
  • Space complexity is O(1)\mathcal{O}(1).
Code (Rust)
use proconio::input;

fn main() {
    input! {
        v: usize,
        t: usize,
        s: usize,
        d: usize,
    }

    println!("{}", if d < v * t || d > v * s {"Yes"} else {"No"});
}
1
2
3
4
5
6
7
8
9
10
11
12

# Problem B - Remove It (opens new window)

Just perform the simulation. Actually we even do not need an array. We can just read from the stream and process the numbers one by one.

  • Time complexity is O(N)\mathcal{O}(N).
  • Space complexity is O(N)\mathcal{O}(N) or O(1)\mathcal{O}(1) if we read the numbers one by one.
Code (Rust)
use proconio::input;

fn main() {
    input! {
        n: usize,
        x: usize,
        a: [usize; n],
    }

    for num in a {
        if num != x {
            print!("{} ", num);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Problem C - Digital Graffiti (opens new window)

It would be a lot easier if we could explicitly draw the outline. How can we achive that?

My trick here is to extend the board, so that

....
.#..
.##.
....
1
2
3
4

becomes

.........
.........
..###....
..###....
..#####..
..#####..
..#####..
.........
.........
1
2
3
4
5
6
7
8
9

A big advantage is that in the new pattern, each side of the polygon has a minimum length of 33. As a result, we just need to count the number of turning points to get the number of sides. They must equal!

How do we find turing points?

We define a # cell which is in touch with a . cell in any of the 8 directions (diagonals included) as an outer cell. These cells form the outline of the pattern. Of course, a turning point must be an outer cell.

We can observe that all turning points must form a right angle with two of its 4-direction neighbors, which should also be outer cells, Thus we can find all the turning points by checking if they can form a right angle.

  • Time complexity is O(HW)\mathcal{O}(HW).
  • Space complexity is O(HW)\mathcal{O}(HW).
Code (Rust)
use proconio::input;
use proconio::marker::Chars;

fn main() {
    input! {
        h: usize,
        w: usize,
        s: [Chars; h],
    }

    let mut extended = vec![vec!['.'; w * 2 + 1]; h * 2 + 1];
    for i in 1..h - 1 {
        for j in 1..w - 1 {
            if s[i][j] == '#' {
                for x in 2 * i..=2 * i + 2 {
                    for y in 2 * j..=2 * j + 2 {
                        extended[x][y] = '#';
                    }
                }
            }
        }
    }

    let mut outer = vec![vec![false; w * 2 + 1]; h * 2 + 1];
    for i in 1..h * 2 {
        for j in 1..=w * 2 {
            if extended[i][j] == '#' {
                for x in i - 1..=i + 1 {
                    for y in j - 1..=j + 1 {
                        if extended[x][y] == '.' {
                            outer[i][j] = true;
                        }
                    }
                }
            }
        }
    }

    let mut ans = 0;
    for i in 1..=h * 2 {
        for j in 1..=w * 2 {
            if outer[i][j] {
                if (outer[i - 1][j] && outer[i][j - 1]) || (outer[i][j - 1] && outer[i + 1][j]) || (outer[i + 1][j] && outer[i][j + 1]) || (outer[i][j + 1] && outer[i - 1][j]) {
                    ans += 1;
                }
            }
        }
    }

    println!("{}", 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

# Problem D - Circle Lattice Points (opens new window)

The idea is easy to come up with. We can do a sweeping line either along the xx-axis or the yy-axis.

Supposing that we sweep along the yy-axis from the lowest integer point to the highest integer point. We can easily find the two intersections of our current line y=y0y=y_0 and the circle, which should be (X−R2−(Y−y0)2,y0)(X-\sqrt{R^2-(Y-y_0)^2}, y_0) and (X+R2+(Y−y0)2,y0)(X+\sqrt{R^2+(Y-y_0)^2},y_0). We can then find the number of interger points between these two points.

However, the floating point precision is a bit annoying. Many contestants got AC on most test cases but could not pass the rest due to this issue.

My solution is to avoid the usage of floats from the beginning. Since there are at most 44 digits after the decimal point, we can multiply all the numbers by 1000010000 and they would fit in i32, which means their squares can fit in i64.

An offset can be used to further avoid negative number divisions, which is also a source of error.

Finally, instead of calculating the radius, we can use binary search to find the leftmost and the rightmost integer points.

  • Time complexity is O(Rlog⁥R)\mathcal{O}(R\log R).
  • Space complexity is O(1)\mathcal{O}(1).
Code (Rust)
use proconio::input;

const TEN: [i64; 4] = [1, 10, 100, 1000];

fn parse(s: String) -> i64 {
    let v = s.split(".").collect::<Vec<&str>>();
    if v.len() == 1 {
        v[0].parse::<i64>().unwrap() * 10000
    } else {
        let sub = v[1].parse::<i64>().unwrap();
        let len0 = v[1].len();
        if v[0].starts_with('-') {
            v[0].parse::<i64>().unwrap() * 10000 - sub * TEN[4 - len0]
        } else {
            v[0].parse::<i64>().unwrap() * 10000 + sub * TEN[4 - len0]
        }
    }
}

fn main() {
    input! {
        x: String,
        y: String,
        r: String,
    }

    let offset = 20_000_000_000_000;
    let offset_s = 2_000_000_000;

    let mut ans = 0i64;
    let x = parse(x);
    let y = parse(y);
    let r = parse(r);

    for i in (y - r + offset) / 10000 - offset_s..=(y + r - 1 + offset) / 10000 + 1 - offset_s {
        let h = y - i * 10000;

        let mut lo = -offset_s;
        let mut hi = x;

        while lo <= hi {
            let mid = (lo + hi) / 2;
            if (mid - x) * (mid - x) + h * h <= r * r {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        let left = (lo - 1 + offset) / 10000 + 1 - offset_s;

        lo = x;
        hi = offset_s;

        while lo <= hi {
            let mid = (lo + hi) / 2;
            if (mid - x) * (mid - x) + h * h <= r * r {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        let right = (hi + offset) / 10000 - offset_s;
        if right >= left {
            ans += right - left + 1;
        }
    }

    println!("{}", 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
64
65
66
67
68
69
70

# Problem E - Come Back Quickly (opens new window)

Problem E proved to be much easier than Problem D. We can solve it by running a Dijkstra from each town.

  • Time complexity is O(N2log⁥M)\mathcal{O}(N^2\log M).
  • Space complexity is O(N+M)\mathcal{O}(N+M).
Code (Rust)
use proconio::input;
use proconio::marker::Usize1;
use std::collections::BinaryHeap;

const INF: i64 = 1_000_000_000_000;

fn main() {
    input! {
        n: usize,
        m: usize,
        edges: [(Usize1, Usize1, i64); m],
    }

    let mut adj: Vec<Vec<(usize, i64)>> = vec![vec![]; n];
    for (u, v, c) in edges {
        adj[u].push((v, c));
    }

    let mut ans = vec![-1; n];
    for i in 0..n {
        let mut dist = vec![INF; n];
        let mut pq: BinaryHeap<(i64, usize)> = BinaryHeap::new();
        pq.push((0, i));
        while !pq.is_empty() {
            let (d, u) = pq.pop().unwrap();
            let d = -d;
            if d > dist[u] {
                continue;
            }
            for (v, c) in adj[u].clone() {
                if d + c < dist[v] {
                    dist[v] = d + c;
                    pq.push((-dist[v], v));
                }
            }
        }
        if dist[i] != INF {
            ans[i] = dist[i];
        }
    }

    for i in ans {
        println!("{}", i);
    }
}
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

# Problem F - GCD or MIN (opens new window)

An important observation is gcd⁡(x,y)≤min⁡(x,y)\gcd(x,y)\leq\min(x,y). So the minimum of all numbers min⁡Ai\min{A_i} proves to be the maximum answer we could get.

Since all the possible answers must be a factor of some number in the array, we can find the factors of every number within O(Nmax⁥Ai)\mathcal{O}(N\sqrt{\max{A_i}}) iterations.

Not all factors can be the final answer. Supposing that a factor k<min⁥Aik<\min{A_i} can be the final answer,

  • kk must be a factor of some number AiA_i.
  • kk comes from a series gcd⁥\gcd operations, e.g., gcd⁥(Ap1,Ap2,â€Ļ)\gcd(A_{p_1},A_{p_2},\dots). kk cannot be AiA_i itself since we have k<min⁥Aik<\min{A_i}.
  • Since the order of gcd⁥\gcd operations does not matter, the first time we meet kk, supposing that we are dealing with the number AiA_i, we can set memo[k]memo[k] to AiA_i. Note that here we have memo[k]â‰Ĩkmemo[k]\geq k.
  • Our goal is to get kk in the end (memo[k]=kmemo[k]=k), so each time we have the chance to perform a gcd⁥\gcd operation (meaning that kk is also a factor of some other number AjA_j), we should perform the gcd⁥\gcd operation to reduce the number memo[k]memo[k] to gcd⁥(memo[k],Aj)\gcd(memo[k],A_j). Since both memo[k]memo[k] and AjA_j can be divided by kk, it is assured that memo[k]memo[k] can be divided by kk. We do the gcd⁥\gcd operation whenever possible because gcd⁥(x,y)≤min⁥(x,y)\gcd(x,y)\leq\min(x,y), and we want to reduce the value memo[k]memo[k].

After processing all the numbers, we check our memomemo and count for how many factors memo[k]=kmemo[k]=k holds.

And the final answer would be that count plus 11 (by using min⁥\min operations only).

  • Time complexity is O(Nmax⁥Ailog⁥max⁥Ai)\mathcal{O}(N\sqrt{\max{A_i}}\log{\max{A_i}}).
  • Space complexity is O(Nd)\mathcal{O}(Nd), where dd is the maximum number of factors of a single number.
Code (C++)
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  int lo = *min_element(a.begin(), a.end());

  unordered_map<int, int> memo;
  for (int ai : a) {
    for (int j = 1; j * j <= ai && j < lo; ++j) {
      if (ai % j == 0) {
        memo[j] = __gcd(ai, memo[j]);
        if (ai / j < lo)
          memo[ai / j] = __gcd(ai, memo[ai / j]);
      }
    }
  }

  int ans = 1;
  for (auto [factor, terminal] : memo)
    if (factor == terminal)
      ans++;

  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
Code (Rust)
use proconio::input;
use std::collections::HashMap;

fn gcd(x: usize, y: usize) -> usize {
    if y == 0 {
        x
    } else {
        gcd(y, x % y)
    }
}

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }

    let mut factors: HashMap<usize, usize> = HashMap::new();
    let lo = *a.iter().min().unwrap();

    for i in 0..n {
        for j in 1..lo {
            if j * j > a[i] {
                break;
            }

            if a[i] % j == 0 {
                let original = *factors.entry(j).or_insert(a[i]);
                factors.insert(j, gcd(original, a[i]));
                if a[i] / j < lo {
                    let original = *factors.entry(a[i] / j).or_insert(a[i]);
                    factors.insert(a[i] / j, gcd(original, a[i]));
                }
            }
        }
    }

    let mut ans = 1;
    for (original, terminal) in factors {
        if original == terminal {
            ans += 1;
        }
    }

    println!("{}", 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