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 this as thee 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.↵
↵
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 & F coming soon (still typing them up).### [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 th
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.↵
↵
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>↵
↵
↵
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.↵
