Hi all, [Atcoder Beginner Contest 183](https://atcoder.jp/contests/abc183) was today. I wrote an unofficial English editorial. Hope it helps!↵
↵
### [A: ReLU](https://atcoder.jp/contests/abc183/tasks/abc183_a)↵
↵
We simply write an if statement.↵
↵
Runtime: $\mathcal{O}(1)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
int x; re(x);↵
if (x < 0) {↵
x = 0;↵
}↵
ps(x);↵
~~~~~↵
</spoiler>↵
↵
### [B: Billiards](https://atcoder.jp/contests/abc183/tasks/abc183_b)↵
↵
The trick is to reflect $G$ over the x-axis, so the desired path becomes a straight line. Then it's a matter of simple math to compute the intersection of that line with the x-axis.↵
↵
Runtime: $\mathcal{O}(1)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
double x1, y1, x2, y2;↵
re(x1, y1, x2, y2);↵
y2 *= -1;↵
double r = -y2 / (y1 - y2);↵
double ans = x1 * r + x2 * (1 - r);↵
ps(ans);↵
~~~~~↵
</spoiler>↵
↵
### [C: Travel](https://atcoder.jp/contests/abc183/tasks/abc183_c)↵
↵
Because $N$ is so small, we can simply try all $(N-1)!$ orderings ($7! = 5040$), and it takes $O(N)$ time to evaluate each one. (Why $(N-1)!$? Well, we know we have to start at $1$ and end at $1$, so we can order the $N-1$ other cities in any order.)↵
↵
Runtime: $\mathcal{O}(N!)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
vector<int> p(n - 1);↵
iota(all(p), 1);↵
int ans = 0;↵
do {↵
int cost = 0;↵
for (int i = 0; i + 1 < sz(p); i++) {↵
int u = p[i];↵
int v = p[i + 1];↵
cost += t[u][v];↵
}↵
cost += t[0][p.front()];↵
cost += t[p.back()][0];↵
ans += (cost == k);↵
} while (next_permutation(all(p)));↵
~~~~~↵
</spoiler>↵
↵
### [D: Water Heater](https://atcoder.jp/contests/abc183/tasks/abc183_d)↵
↵
We can simulate the process over all periods of time, and check whether there exists a time such that the total water needed at that time is strictly greater than $W$.↵
↵
To avoid checking every person at every time step, we can note that each person changes the "current water neded" exactly twice: they add $P_i$ at time $S_i$, and they subtract $P_i$ at time $T_i$. We can sort these $2N$ events by time (taking care to put the subtraction events before addition events at the same time, because $T_i$ is exclusive), then iterate through them.↵
↵
Runtime: $\mathcal{O}(N \log N)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
int n, w; re(n, w);↵
vector<pair<int, int>> events;↵
for (int i = 0; i < n; i++) {↵
int s, t, p;↵
re(s, t, p);↵
events.push_back({s, p});↵
events.push_back({t, -p});↵
}↵
sort(all(events));↵
↵
ll balance = 0;↵
for (auto &i : events) {↵
balance += i.second;↵
if (balance > w) {↵
ps(NO);↵
return 0;↵
}↵
}↵
ps(YES);↵
~~~~~↵
</spoiler>↵
↵
### [E: Queen on Grid](https://atcoder.jp/contests/abc183/tasks/abc183_e)↵
↵
We could solve this in $O(H \cdot W \cdot \max(H, W))$ using a classic DP (for each cell, traverse all cells that could have led to it -- this has $HW$ states, and the transition takes $O(\text{number of previous candidate cells})$, which is $O(\max(H,W))$).↵
↵
However, because $H, W \le 2000$, this is too slow. Let's speed up the transition to $O(1)$, so this will run in time.↵
↵
Let's just discuss how to optimize the transition for horizontal moves (it's the same for vertical and diagonal).↵
The simplest way to do the transition (but too slow) is to loop over all cells to the left of your current cell, then add their counts to your current cell's count. Instead, we'll simply track the cumulative sum of this, which can be updated in $O(1)$ and then read in $O(1)$, instead of $O(W)$.↵
↵
Runtime: $\mathcal{O}(HW)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
int h, w; re(h, w);↵
vector<vector<bool>> obs(h, vb(w));↵
for (int i = 0; i < h; i++) {↵
string input; re(input);↵
for (int j = 0; j < w; j++)↵
obs[i][j] = input[j] == '#';↵
}↵
↵
vector<vector<modnum>> dp(h, vector<modnum>(w));↵
vector<vector<modnum>> horiz(h, vector<modnum>(w));↵
vector<vector<modnum>> vert(h, vector<modnum>(w));↵
vector<vector<modnum>> diag(h, vector<modnum>(w));↵
↵
dp[0][0] = horiz[0][0] = vert[0][0] = diag[0][0] = 1;↵
obs[0][0] = true; // that way we don't modify (0, 0) any further in the loop↵
for (int i = 0; i < h; i++) {↵
for (int j = 0; j < w; j++) {↵
if (obs[i][j])↵
continue;↵
↵
if (i - 1 >= 0) {↵
dp[i][j] += vert[i - 1][j];↵
vert[i][j] = vert[i - 1][j];↵
}↵
if (j - 1 >= 0) {↵
dp[i][j] += horiz[i][j - 1];↵
horiz[i][j] = horiz[i][j - 1];↵
}↵
if (i - 1 >= 0 && j - 1 >= 0) {↵
dp[i][j] += diag[i - 1][j - 1];↵
diag[i][j] = diag[i - 1][j - 1];↵
}↵
↵
vert[i][j] += dp[i][j];↵
horiz[i][j] += dp[i][j];↵
diag[i][j] += dp[i][j];↵
}↵
}↵
↵
ps(dp.back().back());↵
~~~~~↵
</spoiler>↵
↵
### [F: Confluence](https://atcoder.jp/contests/abc183/tasks/abc183_f)↵
↵
The core idea is that there are two $O(NQ)$ solutions (too slow!). Let's call type 1 queries "updates" and type 2 queries "queries".↵
↵
First option: we can use a union-find data structure to maintain the groups. To query, loop over all members of class $y$ and check if they're in the same group as $x$. This takes $O(1)$ to process updates, but $O(\text{size of class})$ to process queries, which is up to $O(N)$.↵
↵
Alternatively: we can use one union-find per class, to maintain the count of students from that class in each group. To query, simply output the already-computed count from that union-find. To update, we have to update all the union-finds, so this takes $O(\text{number of classes})$, which is up to $O(N)$. This also takes $O(N \cdot (\text{number of classes}))$ to initialize.↵
↵
The key observation here is that the first solution is really good if we have small class sizes, and the second solution is really good if we have a small number of classes. As a result, we'll use a classic trick: use the first solution for small classes, and the second solution for big classes. If we define a "big" class as having at least $K$ students, the number of big classes is bounded by $N/K$. This means we can solve the problem in $O(N \cdot (N/K) + \max(K, N/K) \cdot Q)$. If we set $K = \sqrt{N}$, then we have a solution in $O((N+Q) \sqrt{N} )$, which is fast enough if you're careful with the constant factor.↵
↵
Runtime: $\mathcal{O}((N + Q) \sqrt N)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
int n, q; re(n, q);↵
const int k = 400; // approximately sqrt(2e5)↵
↵
vector<int> classes(n);↵
re(classes);↵
trav (i, classes)↵
i--;↵
vector<vector<int>> students(n);↵
for (int i = 0; i < n; i++)↵
students[classes[i]].push_back(i);↵
vector<bool> isbig(n);↵
vector<int> big;↵
for (int i = 0; i < n; i++) {↵
if (sz(students[i]) > k) {↵
big.pb(i);↵
isbig[i] = true;↵
}↵
}↵
↵
union_find uf(n);↵
↵
vector<vector<int>> sizes(n);↵
for (int i : big) {↵
sizes[i] = vector<int>(n);↵
for (int j : students[i])↵
sizes[i][j] = 1;↵
}↵
↵
for (int query = 0; query < q; query++) {↵
int type;↵
re(type);↵
if (type == 1) {↵
int a, b;↵
re(a, b);↵
a--, b--;↵
↵
int u = uf.rep(a), v = uf.rep(b);↵
bool should = uf.unio(a, b);↵
if (should) {↵
int r = uf.rep(u);↵
int s = u ^ v ^ r;↵
for (int i : big) {↵
sizes[i][r] += sizes[i][s];↵
}↵
}↵
} else if (type == 2) {↵
int x, y;↵
re(x, y);↵
x--, y--;↵
↵
int ans = 0;↵
if (isbig[y])↵
ans += sizes[y][uf.rep(x)];↵
else {↵
int r = uf.rep(x);↵
for (int j : students[y]) {↵
ans += uf.rep(j) == r;↵
}↵
}↵
ps(ans);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
You can see my submissions [here](https://atcoder.jp/contests/abc183/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: ReLU](https://atcoder.jp/contests/abc183/tasks/abc183_a)↵
↵
We simply write an if statement.↵
↵
Runtime: $\mathcal{O}(1)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
int x; re(x);↵
if (x < 0) {↵
x = 0;↵
}↵
ps(x);↵
~~~~~↵
</spoiler>↵
↵
### [B: Billiards](https://atcoder.jp/contests/abc183/tasks/abc183_b)↵
↵
The trick is to reflect $G$ over the x-axis, so the desired path becomes a straight line. Then it's a matter of simple math to compute the intersection of that line with the x-axis.↵
↵
Runtime: $\mathcal{O}(1)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
double x1, y1, x2, y2;↵
re(x1, y1, x2, y2);↵
y2 *= -1;↵
double r = -y2 / (y1 - y2);↵
double ans = x1 * r + x2 * (1 - r);↵
ps(ans);↵
~~~~~↵
</spoiler>↵
↵
### [C: Travel](https://atcoder.jp/contests/abc183/tasks/abc183_c)↵
↵
Because $N$ is so small, we can simply try all $(N-1)!$ orderings ($7! = 5040$), and it takes $O(N)$ time to evaluate each one. (Why $(N-1)!$? Well, we know we have to start at $1$ and end at $1$, so we can order the $N-1$ other cities in any order.)↵
↵
Runtime: $\mathcal{O}(N!)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
vector<int> p(n - 1);↵
iota(all(p), 1);↵
int ans = 0;↵
do {↵
int cost = 0;↵
for (int i = 0; i + 1 < sz(p); i++) {↵
int u = p[i];↵
int v = p[i + 1];↵
cost += t[u][v];↵
}↵
cost += t[0][p.front()];↵
cost += t[p.back()][0];↵
ans += (cost == k);↵
} while (next_permutation(all(p)));↵
~~~~~↵
</spoiler>↵
↵
### [D: Water Heater](https://atcoder.jp/contests/abc183/tasks/abc183_d)↵
↵
We can simulate the process over all periods of time, and check whether there exists a time such that the total water needed at that time is strictly greater than $W$.↵
↵
To avoid checking every person at every time step, we can note that each person changes the "current water neded" exactly twice: they add $P_i$ at time $S_i$, and they subtract $P_i$ at time $T_i$. We can sort these $2N$ events by time (taking care to put the subtraction events before addition events at the same time, because $T_i$ is exclusive), then iterate through them.↵
↵
Runtime: $\mathcal{O}(N \log N)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
int n, w; re(n, w);↵
vector<pair<int, int>> events;↵
for (int i = 0; i < n; i++) {↵
int s, t, p;↵
re(s, t, p);↵
events.push_back({s, p});↵
events.push_back({t, -p});↵
}↵
sort(all(events));↵
↵
ll balance = 0;↵
for (auto &i : events) {↵
balance += i.second;↵
if (balance > w) {↵
ps(NO);↵
return 0;↵
}↵
}↵
ps(YES);↵
~~~~~↵
</spoiler>↵
↵
### [E: Queen on Grid](https://atcoder.jp/contests/abc183/tasks/abc183_e)↵
↵
We could solve this in $O(H \cdot W \cdot \max(H, W))$ using a classic DP (for each cell, traverse all cells that could have led to it -- this has $HW$ states, and the transition takes $O(\text{number of previous candidate cells})$, which is $O(\max(H,W))$).↵
↵
However, because $H, W \le 2000$, this is too slow. Let's speed up the transition to $O(1)$, so this will run in time.↵
↵
Let's just discuss how to optimize the transition for horizontal moves (it's the same for vertical and diagonal).↵
The simplest way to do the transition (but too slow) is to loop over all cells to the left of your current cell, then add their counts to your current cell's count. Instead, we'll simply track the cumulative sum of this, which can be updated in $O(1)$ and then read in $O(1)$, instead of $O(W)$.↵
↵
Runtime: $\mathcal{O}(HW)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
int h, w; re(h, w);↵
vector<vector<bool>> obs(h, vb(w));↵
for (int i = 0; i < h; i++) {↵
string input; re(input);↵
for (int j = 0; j < w; j++)↵
obs[i][j] = input[j] == '#';↵
}↵
↵
vector<vector<modnum>> dp(h, vector<modnum>(w));↵
vector<vector<modnum>> horiz(h, vector<modnum>(w));↵
vector<vector<modnum>> vert(h, vector<modnum>(w));↵
vector<vector<modnum>> diag(h, vector<modnum>(w));↵
↵
dp[0][0] = horiz[0][0] = vert[0][0] = diag[0][0] = 1;↵
obs[0][0] = true; // that way we don't modify (0, 0) any further in the loop↵
for (int i = 0; i < h; i++) {↵
for (int j = 0; j < w; j++) {↵
if (obs[i][j])↵
continue;↵
↵
if (i - 1 >= 0) {↵
dp[i][j] += vert[i - 1][j];↵
vert[i][j] = vert[i - 1][j];↵
}↵
if (j - 1 >= 0) {↵
dp[i][j] += horiz[i][j - 1];↵
horiz[i][j] = horiz[i][j - 1];↵
}↵
if (i - 1 >= 0 && j - 1 >= 0) {↵
dp[i][j] += diag[i - 1][j - 1];↵
diag[i][j] = diag[i - 1][j - 1];↵
}↵
↵
vert[i][j] += dp[i][j];↵
horiz[i][j] += dp[i][j];↵
diag[i][j] += dp[i][j];↵
}↵
}↵
↵
ps(dp.back().back());↵
~~~~~↵
</spoiler>↵
↵
### [F: Confluence](https://atcoder.jp/contests/abc183/tasks/abc183_f)↵
↵
The core idea is that there are two $O(NQ)$ solutions (too slow!). Let's call type 1 queries "updates" and type 2 queries "queries".↵
↵
First option: we can use a union-find data structure to maintain the groups. To query, loop over all members of class $y$ and check if they're in the same group as $x$. This takes $O(1)$ to process updates, but $O(\text{size of class})$ to process queries, which is up to $O(N)$.↵
↵
Alternatively: we can use one union-find per class, to maintain the count of students from that class in each group. To query, simply output the already-computed count from that union-find. To update, we have to update all the union-finds, so this takes $O(\text{number of classes})$, which is up to $O(N)$. This also takes $O(N \cdot (\text{number of classes}))$ to initialize.↵
↵
The key observation here is that the first solution is really good if we have small class sizes, and the second solution is really good if we have a small number of classes. As a result, we'll use a classic trick: use the first solution for small classes, and the second solution for big classes. If we define a "big" class as having at least $K$ students, the number of big classes is bounded by $N/K$. This means we can solve the problem in $O(N \cdot (N/K) + \max(K, N/K) \cdot Q)$. If we set $K = \sqrt{N}$, then we have a solution in $O((N+Q) \sqrt{N} )$, which is fast enough if you're careful with the constant factor.↵
↵
Runtime: $\mathcal{O}((N + Q) \sqrt N)$.↵
↵
<spoiler summary="Sample code">↵
~~~~~↵
int n, q; re(n, q);↵
const int k = 400; // approximately sqrt(2e5)↵
↵
vector<int> classes(n);↵
re(classes);↵
trav (i, classes)↵
i--;↵
vector<vector<int>> students(n);↵
for (int i = 0; i < n; i++)↵
students[classes[i]].push_back(i);↵
vector<bool> isbig(n);↵
vector<int> big;↵
for (int i = 0; i < n; i++) {↵
if (sz(students[i]) > k) {↵
big.pb(i);↵
isbig[i] = true;↵
}↵
}↵
↵
union_find uf(n);↵
↵
vector<vector<int>> sizes(n);↵
for (int i : big) {↵
sizes[i] = vector<int>(n);↵
for (int j : students[i])↵
sizes[i][j] = 1;↵
}↵
↵
for (int query = 0; query < q; query++) {↵
int type;↵
re(type);↵
if (type == 1) {↵
int a, b;↵
re(a, b);↵
a--, b--;↵
↵
int u = uf.rep(a), v = uf.rep(b);↵
bool should = uf.unio(a, b);↵
if (should) {↵
int r = uf.rep(u);↵
int s = u ^ v ^ r;↵
for (int i : big) {↵
sizes[i][r] += sizes[i][s];↵
}↵
}↵
} else if (type == 2) {↵
int x, y;↵
re(x, y);↵
x--, y--;↵
↵
int ans = 0;↵
if (isbig[y])↵
ans += sizes[y][uf.rep(x)];↵
else {↵
int r = uf.rep(x);↵
for (int j : students[y]) {↵
ans += uf.rep(j) == r;↵
}↵
}↵
ps(ans);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
You can see my submissions [here](https://atcoder.jp/contests/abc183/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.↵
↵
