### A – Vanishing Pitch

**Spoiler**

The ball is invisible when it's between $$$V \cdot T$$$ and $$$V \cdot S$$$ meters away, inclusive. Thus the answer is `Yes`

if $$$D < V \cdot T$$$ or $$$D > V \cdot S$$$, and `No`

otherwise.

Time complexity: $$$O(1)$$$

### B – Remove It

**Spoiler**

Either use a dynamic array (`vector`

in C++ / `ArrayList`

in Java/Kotlin) to store the values $$$A_i \neq X$$$, or construct the output string directly. If using the latter method in Java/Kotlin, one should use the `StringBuilder`

class to avoid wasting time copying the string in $$$O(N^2)$$$; this is not a problem in C++ as strings are mutable there.

Time complexity: $$$O(N)$$$

### C – Digital Graffiti

**Spoiler**

Simulate a "wall-following" algorithm. Specifically, let `.`

represent empty space, and `#`

represent walls. Find the first `#`

character in reading order. Stand to its north, facing east, with your right hand on the "wall". Then walk forwards. If your hand runs out of wall, turn right, if you run into a wall, turn left, incrementing the answer each time you change direction. Stop when you return to your starting position.

Time complexity: $$$O(HW)$$$

### D – Circle Lattice Points

**Spoiler**

Working with `double`

floating points in this problem may cause precision issues. It's best to multiply the input by $$$10^4$$$ and convert to signed 64-bit integers right away (note that if you're reading the input as a floating point, you need to round before converting). Now the problem becomes the number of points in the circle where $$$X$$$ and $$$Y$$$ are both divisible by $$$10^4$$$.

Iterate through the multiples of $$$10^4$$$ between $$$Y - R$$$ and $$$Y + R$$$ inclusive; let the current value be $$$y$$$.

Now you want to find the minimum and maximum $$$x$$$ that remains in the circle. Either binary search for them, or use `sqrt`

to solve $$$(x - X)^2 + (y - Y)^2 \leq R^2$$$; however since `sqrt`

uses floating points, brute force its neighborhood to avoid precision issues. Then add $$$\displaystyle\left\lfloor\frac {max} {10^4} \right\rfloor - \left\lceil\frac {min} {10^4} \right\rceil + 1$$$ to the answer.

One must also be careful with the divisions, as the behavior of the `/`

operator may differ depending on the sign of the dividend. (In C++ and Java/Kotlin, it *truncates*, i.e., rounds toward zero, instead of finding the floor consistently.)

Time complexity: $$$O(\lceil R \rceil)$$$ or $$$O(\lceil R \rceil \log \lceil R \rceil)$$$

### E – Come Back Quickly

**Spoiler**

Construct the weighted directed graph and run Dijkstra's algorithm from each node. However we have to deal with the fact that the goal node is the same as the source node. There are several ways:

- Set the cost of the source node to $$$\infty$$$ and prepopulate the priority queue with the nodes directly reachable from the source
- Create a new fictional node $$$n+1$$$ to use as the goal node. Redirect all back-to-source edges there.
- First precalculate the cheapest edge from each node to the source node (or $$$\infty$$$ if there are none). Run Dijkstra as normal, then add the costs and find the minimum.

Time complexity: $$$O(N (N+M) \log (N+M))$$$

### F – GCD or MIN

**Spoiler**

Observe that a value $$$x$$$ could be the final value iff $$$x \leq \min A$$$ AND $$$x$$$ is the gcd of some non-empty subset of $$$A$$$.

For the latter condition to hold, $$$x$$$ must be a divisor of at least one value $$$A_i$$$. Also, if $$$[A_a, A_b, ..., A_c]$$$ are all the values of $$$A$$$ divisible by $$$x$$$, their collective gcd must be equal to $$$x$$$.

Thus we can iterate through the divisors of each $$$A_i$$$ and maintain a hashmap, mapping a divisor to the collective gcd of its multiples in $$$A$$$, then count the number of divisors that satisfy.

Time complexity: $$$O(N (\sqrt M + D \log M))$$$, where $$$M = \max A$$$ and $$$D$$$ is the maximum number of divisors for a value $$$A_i$$$, which can be considered roughly $$$O(M^{1/3})$$$.

Spheniscine For problem F -> how is the rough bound O(M^(1/3)) ? I don't understand the maximum bound of D can someone explain ?

It's just a rough "rule of thumb", the exact values can be found on this page.

The divisor function is hard to describe usefully in terms of big $$$O$$$, but it can be proven to always be $$$< 3.528 M ^ {1/3}$$$, which can be considered $$$O(M ^ {1/3})$$$

In theoretical terms it's actually $$$O(M^\varepsilon)$$$ for all $$$\varepsilon > 0$$$, but it converges really slowly.

Thanks for the explanation

Spheniscine can you explain why this submission has failed for problem D https://atcoder.jp/contests/abc191/submissions/20025093

I followed the editorial but it is still failing on test cases handmade_marginal_00.txt

I don't have a C++ debugger handy but might I ask why you have +1 and -1 in these lines:

It might be redundant but I think I added it to be on the safer side

I don't know if it's safer or might be causing the issue. Note that the partial result for some rows can actually be zero, if the circle crosses the line but doesn't actually include any lattice points.

Spheniscine

well I tried this and it worked but I don't understand why it was failing earlier

https://atcoder.jp/contests/abc191/submissions/20025313