Atcoder Beginner Contest 143 — Unofficial English Editorial

Revision en1, by AnandOza, 2019-10-19 16:33:11

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

A: Curtain

The curtains can cover a maximum of $$$2B$$$. So either they don't cover the whole window and the remainder is $$$A-2B$$$, or they do and the remainder is $$$0$$$. So the answer is $$$\max(0, A-2B)$$$.

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

Sample code


We can simply loop through every pair (taking care not to double count) and add the health points restored.

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

Sample code

C: Slimes

We have to count the number of "runs" of consecutive slimes of the same color. We can do this by looping through the array and checking whether the current slime continues the run, then incrementing our answer when we reach the end of a run.

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

Sample code

D: Triangles

The total number of (unordered) triples of sticks is $$$\binom{n}{3} = n(n-1)(n-2)/3$$$. I think it's simplest to count the number of triples that cannot form a triangle, and subtract them. Let's first sort the input array, then if we have a triple $$$(i,j,k)$$$ with $$$i < j < k$$$, we also know $$$L_i \le L_j \le L_k$$$.

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

Sample code

E: Travel by Car

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

Sample code

F: Distinct Numbers

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

Sample code

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

Tags abc, atcoder, editorial, english


  Rev. Lang. By When Δ Comment
en4 English AnandOza 2019-10-21 07:50:40 464 added O(N) solution by Tejs for B
en3 English AnandOza 2019-10-19 17:12:46 2 fixed runtime on A
en2 English AnandOza 2019-10-19 17:09:26 6884 (published)
en1 English AnandOza 2019-10-19 16:33:11 2669 Initial revision (saved to drafts)