Atcoder Beginner Contest 183 — Unofficial English Editorial

Правка en2, от AnandOza, 2020-11-15 16:46:15

Hi all, Atcoder Beginner Contest 183 was today. I wrote an unofficial English editorial. Hope it helps!

A: ReLU

We simply write an if statement.

Runtime: $$$\mathcal{O}(1)$$$.

Sample code

B: Billiards

The trick is to reflect $$$G$$$ over the x-axis, so the desired path becomes a straight line. Then it's a matter of simple math to compute the intersection of that line with the x-axis.

Runtime: $$$\mathcal{O}(1)$$$.

Sample code

C: Travel

Because $$$N$$$ is so small, we can simply try all $$$(N-1)!$$$ orderings ($$$7! = 5040$$$), and it takes $$$O(N)$$$ time to evaluate each one. (Why $$$(N-1)!$$$? Well, we know we have to start at $$$1$$$ and end at $$$1$$$, so we can order the $$$N-1$$$ other cities in any order.)

Runtime: $$$\mathcal{O}(N!)$$$.

Sample code

D: Water Heater

We can simulate the process over all periods of time, and check whether there exists a time such that the total water needed at that time is strictly greater than $$$W$$$.

To avoid checking every person at every time step, we can note that each person changes the "current water neded" exactly twice: they add $$$P_i$$$ at time $$$S_i$$$, and they subtract $$$P_i$$$ at time $$$T_i$$$. We can sort these $$$2N$$$ events by time (taking care to put the subtraction events before addition events at the same time, because $$$T_i$$$ is exclusive), then iterate through them.

Runtime: $$$\mathcal{O}(N \log N)$$$.

Sample code

E: Queen on Grid

We could solve this in $$$O(H \cdot W \cdot \max(H, W))$$$ using a classic DP (for each cell, traverse all cells that could have led to it -- this has $$$HW$$$ states, and the transition takes $$$O(\text{number of previous candidate cells})$$$, which is $$$O(\max(H,W))$$$).

However, because $$$H, W \le 2000$$$, this is too slow. Let's speed up the transition to $$$O(1)$$$, so this will run in time.

Let's just discuss how to optimize the transition for horizontal moves (it's the same for vertical and diagonal). The simplest way to do the transition (but too slow) is to loop over all cells to the left of your current cell, then add their counts to your current cell's count. Instead, we'll simply track the cumulative sum of this, which can be updated in $$$O(1)$$$ and then read in $$$O(1)$$$, instead of $$$O(W)$$$.

Runtime: $$$\mathcal{O}(HW)$$$.

Sample code

F: Confluence

The core idea is that there are two $$$O(NQ)$$$ solutions (too slow!). Let's call type 1 queries "updates" and type 2 queries "queries".

First option: we can use a union-find data structure to maintain the groups. To query, loop over all members of class $$$y$$$ and check if they're in the same group as $$$x$$$. This takes $$$O(1)$$$ to process updates, but $$$O(\text{size of class})$$$ to process queries, which is up to $$$O(N)$$$.

Alternatively: we can use one union-find per class, to maintain the count of students from that class in each group. To query, simply output the already-computed count from that union-find. To update, we have to update all the union-finds, so this takes $$$O(\text{number of classes})$$$, which is up to $$$O(N)$$$. This also takes $$$O(N \cdot (\text{number of classes}))$$$ to initialize.

The key observation here is that the first solution is really good if we have small class sizes, and the second solution is really good if we have a small number of classes. As a result, we'll use a classic trick: use the first solution for small classes, and the second solution for big classes. If we define a "big" class as having at least $$$K$$$ students, the number of big classes is bounded by $$$N/K$$$. This means we can solve the problem in $$$O(N \cdot (N/K) + \max(K, N/K) \cdot Q)$$$. If we set $$$K = \sqrt{N}$$$, then we have a solution in $$$O((N+Q) \sqrt{N} )$$$, which is fast enough if you're careful with the constant factor.

Runtime: $$$\mathcal{O}((N + Q) \sqrt N)$$$.

Sample code

You can see my submissions here as well, if you prefer that to reading the code in the blog.

Thanks for reading! Let me know if you have any questions or feedback for me.

Теги editorial, atcoder, abc, abc183, english

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский AnandOza 2020-11-15 16:46:15 2 Tiny change: ' x-axis.\nRuntime:' -> ' x-axis.\n\nRuntime:'
en1 Английский AnandOza 2020-11-15 16:40:45 8138 Initial revision (published)