Atcoder Beginner Contest 174 — Unofficial English Editorial
Difference between en2 and en3, changed 518 character(s)
Hi all, [Atcoder Beginner Contest 174](https://atcoder.jp/contests/abc174) was today. I wrote an unofficial English editorial. Hope it helps!↵

### [A: Air Conditioner](https://atcoder.jp/contests/abc174/tasks/abc174_a)↵

We simply write an if statement.↵

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

<spoiler summary="Sample code">↵
~~~~~↵
int x = in.nextInt();↵
out.println(x >= 30 ? "Yes" : "No");↵
~~~~~↵
</spoiler>↵

### [B: Distance](https://atcoder.jp/contests/abc174/tasks/abc174_b)↵

We can loop through all the points, and test each one. To avoid potential rounding errors, it's simplest to check $x^2 + y^2 \le D^2$, so we can keep everything in integers.↵

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

<spoiler summary="Sample code">↵
~~~~~↵
int n = in.nextInt();↵
long d = in.nextInt();↵
d = d * d;↵
Point[] points = Point.readPoints(in, n);↵

int answer = 0;↵
for (Point p : points) {↵
    if (p.x * p.x + p.y * p.y <= d)↵
        answer++;↵
}↵

out.println(answer);↵
~~~~~↵
</spoiler>↵

### [C: Repsept](https://atcoder.jp/contests/abc174/tasks/abc174_c)↵

First, we simplify: if $k$ is a multiple of $7$, then we can look for a number like $1111$ that's a multiple of $k/7$. Otherwise, using $7777$ instead of $1111$ doesn't help us.↵

If you consider the sequence of numbers to check as $a_i = 10 a_{i-1} + 1$ modulo $k$, there is guaranteed to be a solution within $k$ steps if and only if $\mathrm{gcd}(10, k) = 1$.↵
So we can check for impossibility using this fact, and then iterate through the choices otherwise and check them all until we find the smallest one that works.↵

<spoiler summary="Proof of bound">↵
Suppose we go through $k$ values without seeing one that's $0$ modulo $k$. Then we have at most $k-1$ distinct values↵
(modulo $k$), so by pigeonhole there exist $i$ and $j$ such that $a_i = a_j$ modulo $k$ (and let's assume $i<j$).↵

If we compute $a_j-a_i$ we end up with $a_{j-i} \times 10^i$, so $a_{j-i} \times 10^i = 0$ modulo $k$. Since $k$ doesn't share any common factor with $10$,↵
this means that $a_{j-i}$ is a multiple of $k$, which is a contradiction.↵
</spoiler>↵

Take care to test locally on $k=1$ specifically, it's easy to get this wrong with a loop.↵

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

<spoiler summary="Sample code">↵
~~~~~↵
int k = in.nextInt();↵
if (k % 7 == 0)↵
    k /= 7;↵

if (gcd(10, k) != 1) {↵
    out.println(-1);↵
    return;↵
}↵

long v = 1 % k;↵
int len = 1;↵
while (v != 0) {↵
    v = (10 * v + 1) % k;↵
    len++;↵
}↵

out.println(len);↵
~~~~~↵
</spoiler>↵

### [D: Alter Altar](https://atcoder.jp/contests/abc174/tasks/abc174_d)↵

A few quick observations:↵

 - At the end, we want a sequence that looks like RRRRWWWWWWW (some number of red stones, followed by some number of white stones, and one of these could possibly be zero).↵
 - If we want to change a red stone's color and a white stone's color, this takes 1 step as we can swap them.↵

Now, we can simply try all values of the final number of red stones from $0$ to $N$ (let's call this number $R$). For a given value of $R$, the cost is given as↵

$$X = (\text{number of white stones in the first $R$})$$↵
$$Y = (\text{number of red stones in the last $N-R$})$$↵
$$C_R = X + Y - \min(X,Y)$$↵

If we compute prefix sums to help us compute this, we can test one value in $O(1)$, so testing them all will run in time.↵

Bonus: this function is convex, so we can minimize it using ternary search.↵

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

<spoiler summary="Sample code">↵
~~~~~↵
int n = in.nextInt();↵
char[] c = in.next().toCharArray();↵

int[] w = new int[n + 1];↵
for (int i = 0; i < n; i++) {↵
    w[i + 1] = w[i] + (c[i] == 'W' ? 1 : 0);↵
}↵

IntUnaryOperator moves = left -> {↵
    int wrongLeft = w[left];↵
    int wrongRight = (n - left) - (w[n] - w[left]);↵

    return wrongLeft + wrongRight - Math.min(wrongLeft, wrongRight);↵
};↵

int answer = ternarySearch(moves, 0, n);↵
out.println(moves.applyAsInt(answer));↵
~~~~~↵
</spoiler>↵

### [E: Logs](https://atcoder.jp/contests/abc174/tasks/abc174_e)↵

It's hard to figure out which logs to cut greedily, but given a value $L$ for the final answer, we can easily check whether it's attainable in $O(N)$.↵

In order to do this, we loop through all the logs and cut off pieces of exactly length $L$ from them, until they are length $L$ or shorter. So for a log of length $x$, this takes $\lfloor(x-1)/L \rfloor$ steps.↵

It's also easy to see intuitively that the cost is non-increasing as $L$ increases, so we can binary search to find the smallest length $L$ so that the numbers of steps is $\le k$.↵

Runtime: $\mathcal{O}(N \log L)$, where $L$ is the maximum possible length of a log.↵

<spoiler summary="Sample code">↵
~~~~~↵
int n = in.nextInt();↵
int k = in.nextInt();↵
int[] a = in.readIntArray(n);↵

IntPredicate cuts = l -> {↵
    if (l <= 0)↵
        return false;↵
    long c = 0;↵
    for (int x : a) {↵
        c += (x - 1) / l;↵
    }↵
    return c <= k;↵
};↵

out.println(binarySearch(cuts));↵
~~~~~↵
</spoiler>↵

### [F: Range Set Query](https://atcoder.jp/contests/abc174/tasks/abc174_f)↵

This is a standard algorithm, which I didn't figure out myself but learned some time ago by web search, from the following link: https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/↵

To implement it efficiently without bugs, I copy/pasted from my submission for a previous Codeforces problem ([submission:85732941]).↵

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

Time to write: $O(1)$.↵

<spoiler summary="Sample code">↵
~~~~~↵
int n = in.nextInt(), queryCount = in.nextInt();↵
int[] c = in.readIntArray(n);↵
for (int i = 0; i < n; i++) {↵
    c[i]--;↵
}↵
Pii[] queries = new Pii[queryCount];↵
for (int i = 0; i < queryCount; i++) {↵
    queries[i] = Pii.of(in.nextInt() - 1, in.nextInt());↵
}↵

List<Integer>[] byEnd = Util.arrayOfLists(n + 1);↵
for (int i = 0; i < queryCount; i++) {↵
    byEnd[queries[i].second].add(i);↵
}↵

IntSumSegmentTree st = new IntSumSegmentTree(n);↵
int[] last = new int[n];↵
Arrays.fill(last, -1);↵

int[] answer = new int[queryCount];↵
for (int i = 0; i < n; i++) {↵
    if (last[c[i]] != -1) {↵
        st.update(last[c[i]], 0);↵
    }↵

    st.update(i, 1);↵
    last[c[i]] = i;↵

    for (int j : byEnd[i + 1]) {↵
        answer[j] = st.query(queries[j].first, queries[j].second);↵
    }↵
}↵

for (int x : answer)↵
    out.println(x);↵
~~~~~↵
</spoiler>↵


You can see my submissions [here](https://atcoder.jp/contests/abc174/submissions?f.Task=&f.Language=&f.Status=AC&f.User=AnandOza) 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.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English AnandOza 2020-08-02 17:24:46 518
en2 English AnandOza 2020-08-02 16:57:47 2438
en1 English AnandOza 2020-08-02 16:47:06 3795 Initial revision (published)