AtCoder Beginner Contest 170

Updated: 2020-06-14

Source codes

Solutions

B - Crane and Turtle

Just try all possibilities. The head of crane $i$ runs in $[0, X]$ and let $j = X - i$. Then, we check $2i + 4j = Y$ or not.

C - Forbidden List

Just try all possibilities for $x \in [-100, 200]$.

D - Not Divisible

Let $L = 10 ^ 6 + 10$.

Solution

The main concept is the way of sieve of Eratosthenes.

We create two tables.

$cnt[i] = \sharp \{ j \in N \mid A _ j = i \}$,
$valid[i] = $ true if the number $i$ cannot be divided by other $A[j] \neq i$.

Then, the answer is \[ \sharp \{ 1 \leq i \leq L \mid valid[i] \land cnt[i] = 1 \}. \]

We try $i \in [1, L]$ with $cnt[i] > 0$. For $j = 2, 3, \dots$, $valid[i \times j] \gets $ false.

The total time complexity is $O(L \log L)$.

E - Smart Infants

Let $L = 10 ^ 5 + 10$. Assume $0$-indexed.

My Solution

Let $tree$ be the RangeMinQuery-type segment tree. We update $tree$ and ask it the answer for each query. By each transfer, only two gardens will be updated.

We define as follows.

vector<multiset<int, greater<int>>> $garden[i] = $ the multiset of the scores of the infants belonging to the garden $i$,
SegTree<int, int> $tree[i] = $ the maximum score of the infants belonging to the garden $i$ if the garden is not empty; otherwise $\infty$.

For each transfer, we regard $(score, src, dst)$ as a query. We erase $score$ from $garden[src]$ and insert it into $garden[dst]$. We take the maximum elements from each garden (or $\infty$ if it is empty) and update $tree[src]$ and $tree[dst]$. Then, ask $tree$ the answer.

Time complexity

The initial setting takes $O(N \log N + L \log L)$-time. Each update takes $O(\log L + \log N)$-time. The total time complexity will be $O(N \log N + L \log L + Q \log L + Q \log N)$-time.

F - Pond Skater

Observation

The number of the maximal steps $K$ is so large. We have to reduce the possibilities to solve this problem. In this kind of the problems, the key idea is to decompose the transition into more fundamental steps. We keep how many times the frog has continued the same direction. Then, we just try $4$ possibilities for each query.

This problem is about the extended version of Dijkstra’s algorithm.

My solution (extended Dijkstra)

We regard $(x, y, k)$ as an extended point, with $(x, y) \in H \times W$ being the point, $k \in 4$ being the direction.

We regard $(d, md)$ as an extended distance, where $d$ is the actual distance from the starting point, and $ms$ is the step where the frog has continued the same direction.

DP part

Definition

Type definitions:

using Score = tuple<int, int>; $(s, ms)$ for the value of $dp$,
using Info = tuple<int, int, int, int, int>; $(s, ms, x, y, k)$ for the value of min_heap.

DP definitions:

vector<vector<vector<Score>>> $dp[x][y][k] = $ the minimum score in $(x, y, k)$,
min_heap<Info> $H$.

Initial State

$H \gets (0, 0, sx, sy, k)$ for $k \in 4$. We set $dp[x][y][k] = $ Empty or Invalid.

Answer

We try $dp[gx][gy][k]$ for all $k \in 4$. If they all are empty, the answer is -1. Otherwise, it is the minimum value of them. We regard $(s, ms) \mapsto s$ if $ms = 0$ or $(s, ms) \mapsto s + 1$ if $ms > 0$.

Transition

We get $(s, ms; x _ s, y _ s, k _ s) \gets H$ and execute H.pop();. If $dp[x _ s][y _ s][k _ s] = $ Empty, execute continue;.

First, we think of the change of the direction. For $k _ d \in 4$ with $k _ d \neq k _ s$, the new point is $(x _ s, y _ s, k _ d)$. If it is valid and $dp[x _ s][y _ s][k _ d]$ is Empty, we execute the following. \[ H \gets \begin{cases} (s + 1, 0; x _ s, y _ s, k _ d) & ms > 0, \
(s, 0; x _ s, y _ s, k _ d) & ms = 0. \end{cases} \]

Second, we think of the proceeding. The new point is $(x _ d, y _ d, k _ d) = (x _ s + dx[k _ s], y _ s + dy[k _ s], k _ s)$. If it is valid and $dp[x _ d][y _ d][k _ d]$ is Empty, we execute the following. \[ H \gets \begin{cases} (s + 1, 0; x _ d, y _ d, k _ d) & ms = K - 1, \
(s, ms; x _ d, y _ d, k _ d) & ms < K - 1. \end{cases} \]

Another Solution #1 (Using set for pre-visited points)

We reduce $O(HWK)$-BFS to $O(HW (\log H + \log W)))$-BFS by using vector<set<Point>> Sx, Sy;. By lower_bound and upper_bound, we can avoid visiting the point which we have visited before. Be careful for @.

I made an attempt to implement this solution, but I felt that this was a difficult solution since I had to care empty sets.

Another Solution #2 (Break if we meet less-than-distance grid)

We reduce $O(HWK)$-BFS to $O(HW)$-BFS. First, we implement normal BFS.

    while (!Q.empty())
    {
      auto p{Q.front()};
      auto [x, y] = p;
      Q.pop();
      for (auto k{0}; k < 4; ++k)
      {
        for (auto i{1}; i <= K; ++i)
        {
          auto nx{x + dx[k] * i};
          auto ny{y + dy[k] * i};
          // we want to discuss how we can make transition here.
        }
      }
    }

Transition is summarized as follows.

Of course, if we meet an @ grid or out-of-range, we put break;.
If we meet an empty grid, we write the answer in $V$ and go further.
If we meet a visited grid whose value is equal to $V[x][y]$, we continue; to go further since we may reach an empty grid beyond that.
If we meet a visited grid whose value is less than $V[x][y]$, we put break; since it suffice to try BFS by another chance from that point. Thus, even if we stop there, the final result will be the same.

          if (!valid(nx, ny))
          {
            break;
          }
          else if (V[nx][ny] == Infty<int>())
          {
            V[nx][ny] = V[x][y] + 1;
            Q.push(Point{nx, ny});
          }
          else if (V[nx][ny] == V[x][y] + 1)
          {
            continue;
          }
          else
          {
            break;
          }

We can estimate the maximal visit for each grid. It will be less than or equal to $4$ since the kinds of directions is less than $4$. If we think more carefully, the upper bound $4$ becomes $2$.

Caution

This solution works because we use BFS. By BFS, we determine the distance of each grid before we visit it. This is a key to make a break. For example, if we apply Dijkstra method for this problem, we cannot use this trick.

Others

Review: 2020-06-20

A - sample: 2, tle: 2.000, time: 04:46, from_submit: 48:53
B - sample: 3, tle: 2.000, time: 01:26, from_submit: 47:27
C - sample: 3, tle: 2.000, time: 03:48, from_submit: 43:39
D - sample: 3, tle: 2.000, time: 04:23, from_submit: 39:16
E - sample: 2, tle: 3.500, time: 16:48, from_submit: 22:29
F - sample: 3, tle: 3.000, time: 22:29, from_submit: 00:00

Kazune Takahashi