AtCoder Regular Contest 224

Introduction

I participated in the AtCoder Regular Contest– 224 this past Sunday. This was my first full-solving an ARC live, and I felt the problems were very educational.

A. Attach 00

Problem. Given a positive integer $𝐾$ ($1\le 𝐾\le {10}^9$), find the smallest positive integer $𝑛$ such that $𝑛$ is a multiple of $𝐾$, and the base-ten representation of $𝑛$ contains the substring 00.

Analysis. At first glance, there doesn’t seem any clear path towards computing the answer. I thought that instead of trying to guess constructions, I should try to prove some results.

First, I need to show that such an $𝑛$ even exists. In fact, $100𝐾$ always ends in 00, so such an $𝑛$ exists, and the upperbound is $100𝐾$.

Now I see that there are only $100$ candidates to test: $𝐾,2𝐾,3𝐾,\dots ,100𝐾$, so each test case can be solved in at most ${log}_{10}\left(𝐾\right)+{log}_{10}\left(2𝐾\right)+\dots +{log}_{10}\left(100𝐾\right)={log}_{10}\left(100!\right)+100{log}_{10}\left(𝐾\right)\le 200+900=1100$ operations, so the brute-force algorithm is fast enough even over $𝑇={10}^5$ testcases.

Note that if we keep track of the current length of the base-ten representation, we can avoiding the log factor for every integer and achieve a solution with about $110$ operations per testcase, but this is not necessary for this problem.

B. Adjacent Tiles

Problem. Place $𝑁$ ($1\le 𝑁\le {10}^{18}$) unit squares on a plane so that they do not overlap. What is the maximum possible number of pairs of different tiles that share one full side?

Analysis. Since $𝑁$ can be up to ${10}^{18}$, the solution is likely a simple math formula.

Indeed, with some greedy guessing and contradiction logic, it is possible to prove with a lemma that the answer is

C. Ascending Labels

Problem. Given a connected simple undirected graph with $𝑁$ vertices and $𝑀$ edges ($1\le 𝑁\le 3\times {10}^5$, $𝑁-1\le 𝑀\le 3\times {10}^5$). Assign an integer ${𝐴}_{𝑣}$ ($0\le {𝐴}_{𝑖}\le 𝑁$) to every vertex $𝑣$ such that ${𝐴}_1=0$ and for all vertices $𝑣\ne 1$, there is exactly one vertex $𝑤$ adjacent to $𝑣$ satisfying ${𝐴}_{𝑤}={𝐴}_{𝑣}-1$.

Analysis. We first think about the following question: “what kind of structure has the required property?” By thinking about this question, we recall that a tree has the property that each vertex besides the root has exactly one parent, and if we can assign ${𝐴}_{𝑣}$ to the depth of some tree describing the edges, we are done.

What is a tree we can make from a graph? A DFS tree! It is not hard to show that a DFS tree satisfies the given properties. Therefore, for each vertex $𝑣$, we output the depth of $𝑣$ in the DFS tree rooted at $0$ for the given graph. The time complexity is $𝑂\left(𝑁+𝑀\right)$.

D. Angst for All Pairs

Problem. There are $𝑁$ ($1\le 𝑁\le {10}^6$) cards, numbered $1$ through $𝑁$. Initially nothing is written on any of the cards. Writing a number $𝑘$ on a card incurs a cost equal to the number of digits in the decimal representation of $𝑘$. Find the minimum cost required to make sure that for every integer pair $\left(𝑥,𝑦\right)$ with $1\le 𝑥<𝑦\le 𝐾$ ($2\le 𝐾\le {10}^6$), there exists a card containing exactly one of $𝑥$ and $𝑦$. If this is impossible, output $-1$.

Analysis. In my opinion, this problem is quite difficult to solve purely by staring at it and trying to prove a magical answer. It is more intuitive to play around with some examples.

After playing around with various examples for a while, I discovered that we can skip one of the numbers. Then, we should put one number on each card first. If there are more, put a number on two cards such that this pair has not been selected for a “two-card” level. Then do the same for three, four, … until we have no numbers left. The game is impossible if we still have numbers left after exhausting the level of “write to every card.”

For level $𝑚=0,1,2,\dots ,𝑁$, there are $\left(\genfrac{}{}{0ex}{}{𝑁}{𝑚}\right)$ spots to put a number. Therefore, we can put at most

numbers in total. The answer is $-1$ if and only if $𝐾>2^{𝑁}$.

Now suppose $𝐾\le 2^{𝑁}$. We will execute the greedy algorithm described above for $𝑥=𝐾,𝐾-1,\dots ,1$ (place the larger numbers first).

The time complexity for this simulation is in $𝑂\left(𝐾log𝐾+{\left(log𝑘\right)}^2\right)$, but it is a bit hard to show.

E. ABC|AB|A

Problem. Given a string $𝑆$ ($1\le \left|𝑆\right|\le {10}^6$) consisting of A, B, and C, you can perform the following oepration zero or more times: “Choose a substring of $𝑆$ that is either A, AB, or ABC, and delete it.” Find the minimum possible length of $𝑆$ in the end.

Analysis. I was surprised that I solved this problem in five minutes. The problem reminded me of ideas in DFAs (Deterministic Finite Automations).

The idea is to keep track of “how close we are to being able to delete a substring.” We can do this by defining a DFA with states being the suffixes of the deletable substrings.

We will process the characters of $𝑆$ in reverse order. We will define a DFA with the following states: ${𝑞}_0,{𝑞}_{\text{B}},{𝑞}_{\text{C}},{𝑞}_{\text{BC}}$, representing the current suffix we see. The transitions are straightforward: $\left({𝑞}_0,\text{C}\right)\to {𝑞}_{\text{C}}$, $\left({𝑞}_{\text{C}},\text{B}\right)\to {𝑞}_{\text{BC}}$, $\left({𝑞}_0,\text{B}\right)\to {𝑞}_{\text{B}}$. Let ans be $|𝑆|$ initially. Whenever we reach one of the deletable substring, we move back to ${𝑞}_0$ and add subtract the length from ans, and whenever we reach a string that can never be extended leftwards to match a deletable substring (i.e. not part of the transitions), we go back to ${𝑞}_0$. We can show this greedy algorithm is correct by induction on the suffix of $𝑆$. The time complexity is $𝑂\left(|𝑆|\right)$.

F. AND/OR

Problem. See official statement.

Analysis. This problem has some nice ideas about the prefix sums of binomial coefficients.

This will take a while to explain, sorry. See official editorial for their solution, which was the same as mine.