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.↵
↵
### [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.↵
