ABC179 editorial

This is unofficial editorial for atCoder abc179.

A - Plural Form

You just need to check the last character of the string, if it’s s add es, otherwise add s. This can be done using one if statement.

Time complexity \(O(1)\).

Code

B - Go to Jail

Store in a counter variable the number of Consecutive pairs such that \(D_{i, 1} = D_{i, 2}\). Increase it by one when they are equal, and set it to zero when they aren’t, if this counter become \(3\) print Yes.

Time complexity \(O(N)\).

Code

C - A x B + C

We can brute force over \(A\) and \(B\) and check if \(C\) is greater than \(0\). This works because for every value of \(A\) \(B\) can take values exactly \(\frac{N}{A}\). The total runtime complexity can be calculated as: \(\sum_{A=1}^{N} \frac{N - 1}{A} = N \times log(N)\)

Time complexity \(O(N \times log(N))\).

Code

D - Leaping Tak

Simple version

Let’s try to solve the problem for \(N \le 1000\). We will use dynamic programming to solve it. Let dp[i] equal the number of ways to reach cell \(i\). It’s clear that dp[1] = 1, and for every \(d \subset S\) we can write dp[i + d]+=dp[i]. Finally the answer can be found at dn[n].

The solution

All the given \(k\) segments are contentious, so for some segment \(j\) it will increase the answer for contentious indexes between \([i + L_j, i + R_j]\) by the value of dp[i]. To implement this efficiently we need a data structure that supports range updates, this can be done using Segment tree or BIT.

Time complexity \(O(N \times k \times log(N))\).

Code

E - Sequence Sum

The main observation is \(M \le 10^5\). This means that the sequence will get in repeated circle after a while, we just need to implement the operation and find the first time the circle will begun and the length of the circle.

Time complexity \(O(M \times log(M))\).

Code

F - Contrast

Let’s see what happens when we apply the first operation, the number of the changed black cells is equal to N - i - 1 where \(i\) is the top most row in that column containing a white cell, same thing goes when we apply the second operation, but here \(i\) is the left most column containing a white cell in that row. So we just need two segment trees one for columns and one for rows.

For every query let’s change x to n - x + 1, to handle the first type we find i by querying the \(x_{th}\) column from the columns tree, decreasing the number of black cells, and then updating the range \([i, N]\) with value \(x\) in the rows tree. Same thing goes with the second type queries.

Time complexity \(O(Q \times log(N))\).

Code