I participated in ABC 350. Solved 4 problems (A~D). 1142 performance. I think I should really practice probabilities so that I can solve problems like E... Overall, after upsolving all the problems, I think it was a good set. There were some problems I learned something new and hopefully get some new intuition I can use on other problems.
A - Past ABCs
Simply check for the condition as given in the problem statement. Do be careful to check for ABC316 and ABC000.
Code (Python3):
s = input()
nums = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
if(s.startswith('ABC') and s[3] in nums and s[4] in nums and s[5] in nums and 0<int(s[3:])<=349 and int(s[3:])!=316):
print("Yes")
else:
print("No")
B - Dentist Aoki
Initialize a boolean array which keeps track of whether there is a tooth in each hole. Then each time $T_i$ is given in the query, toggle the $T_i$-th element of the array. Finally, count the number of elements that are turned on.
I accidentally set holes without a tooth as $True$ so I had to $N - count$ to get the answer.
Code (C++):
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
const ll LLINF = 4'500'000'000'000'000'000;
const ll MOD = 1'000'000'007;
bool t[1005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int n, q; cin >> n >> q;
while(q--){
int a; cin >> a;
t[a] = !t[a];
}
int sum = 0;
for(int i=1; i<=n; i++){
sum += t[i];
}
cout << n-sum;
}
C - Sort
Maintain an array which keeps track of where $i$ initially appears in the given permutation. Then, traverse the permutation, and if you encounter $A_i$ such that $A_i \neq i$ swap the element with $i$ (since we precomputed the position of each $i$ in $A$, this takes $\mathcal{O}(1)$ time).
Code (C++):
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
const ll LLINF = 4'500'000'000'000'000'000;
const ll MOD = 1'000'000'007;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int n; cin >> n; vector<int> v(n+1), pos(n+1);
for(int i=1; i<=n; i++) {cin >> v[i]; pos[v[i]] = i;}
vector<pii>q;
for(int i=1; i<=n; i++){
if(v[i] != i){
q.push_back({i, pos[i]});
int a = pos[i], b = v[i];
swap(v[i], v[pos[i]]);
pos[i] = i; pos[b] = a;
}
}
cout << q.size() << endl;
for(auto i:q) cout << i.fr << ' ' << i.sc << endl;
}
D - New Friends
There are a few observations to make. First, if we model the friendships as a graph, it is impossible to make a new friendship between two friends in different connected components. Second, if we consider each connected component as a subgraph as its own, we can create new friendships until the subgraph is a complete graph. Thus, the problem reduces to finding the sum of the number of edges which can be added for each subgraph until it is complete.
The reasoning behind the second observation is as follows. Let's define the distance between two vertices $dist(u, v)$ to be the number of edges in the shortest path between $u$ and $v$. Then, the operation can be thought of as drawing a new edge between two vertices $(x, y)$ where $dist(x, y) = 2$. For any connected component of size greater than or equal to $3$, such $(x, y)$ pair always exists. Now what we have to notice is that by performing the operation for $(x, y)$, for a vertex $z$ which is adjacent to $y$ and $dist(x, z) = 3$ before the operation, $dist(x, z)$ becomes $2$. This allows us to perform the operation for $(x, z)$. This can repeatedly be applied to all vertices at any arbitrary distance within the connected component which effectively allows us to add an edge between any arbitrary pair of vertices (if there isn't one already).
The answer can be calculated using DFS search.
Code (C++):
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
const ll LLINF = 4'500'000'000'000'000'000;
const ll MOD = 1'000'000'007;
vector<int>edges[200005]; bool vis[200005];
ll sz = 0;
ll dfs(ll cur){
ll ret = edges[cur].size();
vis[cur] = 1;
sz++;
for(int &nxt:edges[cur]){
if(vis[nxt]) continue;
ret += dfs(nxt);
}
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int n, m; cin >> n >> m;
for(int i=0; i<m; i++){
int a, b; cin >> a >> b;
edges[a].push_back(b);
edges[b].push_back(a);
}
ll ans = 0;
for(int i=1; i<=n; i++){
if(vis[i]) continue;
sz = 0; ll ret = dfs(i);
ans += (sz*(sz-1))/2 - ret/2;
}
cout << ans;
}
E (upsolved) - Toward 0
If we define $E(X)$ to be the expected cost for $X$ to become 0, $E(X) = min(\frac{1}{6} (E(\lfloor \frac{X}{1} \rfloor) + E(\lfloor \frac{X}{2} \rfloor) + E(\lfloor \frac{X}{3} \rfloor) + E(\lfloor \frac{X}{4} \rfloor) + E(\lfloor \frac{X}{5} \rfloor) + E(\lfloor \frac{X}{6} \rfloor)) + Y, E(\lfloor \frac{X}{A} \rfloor) + X)$
Then since $ \lfloor \frac{X}{1} \rfloor = X $, by grouping the $E(X)$ terms, we can rearrange it to $E(X) = min(\frac{1}{5} (E(\lfloor \frac{X}{2} \rfloor) + E(\lfloor \frac{X}{3} \rfloor) + E(\lfloor \frac{X}{4} \rfloor) + E(\lfloor \frac{X}{5} \rfloor) + E(\lfloor \frac{X}{6} \rfloor)) +\frac{6}{5} Y, E(\lfloor \frac{X}{A} \rfloor) + X)$.
From here, the expected value can be calculated using a simple top-down DP approach. Since the number of states is $\mathcal(abc)$ where $X = 2^{a}3^{b}5^{c}$, we are assured that the time complexity falls within a $log^3$ bound.
In the contest, I wasn't able to come up with the idea of grouping $E(X)$ terms. I was constantly stuck with the question, 'How do I deal with that 1/6 probability that I end up staying in the same spot?'
Code (C++):
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 12
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
const ll LLINF = 4'500'000'000'000'000'000;
const ll MOD = 1'000'000'007;
map<ll, ld>mp;
ld dfs(ll N, ll A, ld X, ld Y){
if( N == 0 ) return 0;
if(mp.find(N) != mp.end()) return mp[N];
ld ret1 = X + dfs(N/A, A, X, Y);
ld ret2 = 1.2 * Y;
for(ll i=2; i<=6; i++){
ret2 += dfs(N/i, A, X, Y)*0.2;
}
return mp[N] = min(ret1, ret2);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
ll N, A, X, Y; cin >> N >> A >> X >> Y;
cout << dfs(N, A, X, Y);
}
F (upsolved) - Transpose
Beautiful problem. I loved the idea used here. Essentially, the first thing that we have to notice is that for characters at an even "bracket depth", their case does not change. This allows us to determine whether each character in the resultant string is upper or lower case with just one "scan" of the original string.
Now let's store for each left/right bracket where its corresponding right/left bracket is and store it in an array called $jmp$. Now we will traverse the string from left to right. If the current character is not a bracket, simply print it. Otherwise, if a left bracket is encountered, skip to its $jmp$ position, and traverse the substring formed by the bracket in reverse direction (when going from right to left, do the same when a right bracket is encountered). Do this recursively, and skip the substrings that have already been traversed once you return.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 16
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
const ll LLINF = 4'500'000'000'000'000'000;
const ll MOD = 998244353;
stack<int>st; string ex;
int jmp[500005];
void solve(int l, int r, bool d){
// 0 : ->, 1 : <-
if(d == 0){
while(l <= r){
if(ex[l]=='('){
solve(l+1, jmp[l]-1, !d);
l = jmp[l];
}
else{
if(ex[l]!=')'){
cout << ex[l];
}
l++;
}
}
}
else{
while(l <= r){
if(ex[r]==')'){
solve(jmp[r]+1, r-1, !d);
r = jmp[r];
}
else{
if(ex[r]!='('){
cout << ex[r];
}
r--;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> ex; int N = ex.size();
for(int i=0; i<N; i++){
if(ex[i] == '('){
st.push(i);
}
else if(ex[i] == ')'){
jmp[st.top()] = i;
jmp[i] = st.top();
st.pop();
}
else{
if(st.size() % 2 == 0) continue;
else{
if(ex[i] >= 'a' && ex[i] <= 'z'){
ex[i] = toupper(ex[i]);
}
else ex[i] = tolower(ex[i]);
}
}
}
solve(0, N-1, 0);
}
G (upsolved) - Mediator
Suppose we maintain a forest of rooted trees, the answer for queries of type 2 for two vertices $(u, v)$ is
- The parent of $v$ if $u$ and $v$ have the same parent.
- $u$ if the parent of the parent of $v$ is $u$.
- $v$ if the parent of the parent of $u$ is $v$.
- $0$ otherwise.
Now all we need to do is maintain the parent of each node in an online incremental scenario. This can be done using the small-to-large disjoint set data structure. We merge the smaller tree to the larger tree, and update the parents of the nodes in the smaller tree accordingly.
Code (C++):
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 16
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
const ll LLINF = 4'500'000'000'000'000'000;
const ll MOD = 998244353;
struct Union_find{
vector<int>root, sz;
vector<vector<int>>edges; vector<int>parent;
Union_find(int N){
root.resize(N+1); iota(root.begin(), root.end(), 0);
parent.resize(N+1); iota(parent.begin(), parent.end(), 0);
sz.resize(N+1, 1); edges.resize(N+1);
}
void dfs(int cur, int par){
parent[cur] = par;
// cout << cur << ' ' << par << endl;
for(int &nxt:edges[cur]){
if(nxt == par) continue;
dfs(nxt, cur);
}
}
int fnd(int node){
if(node = root[node]) return node;
else return root[node] = fnd(root[node]);
}
bool uni(int n1, int n2){
int p1 = fnd(n1), p2 = fnd(n2);
// 1->2, small to large
if(sz[p1] > sz[p2]) {swap(n1, n2); swap(p1, p2);}
dfs(n1, n2);
edges[n1].push_back(n2); edges[n2].push_back(n1);
if(p1 == p2) return false;
else{
root[p1] = p2; sz[p2] += sz[p1];
return true;
}
}
int query(int x, int y){
ll ret = 0;
if(parent[x] != x && parent[x] != y && parent[parent[x]] == y){
ret = parent[x];
}
if(parent[y] != y && parent[y] != x && parent[parent[y]] == x){
ret = parent[y];
}
if(parent[x] == parent[y] && parent[x] != x && parent[y] != y){
ret = parent[y];
}
return ret;
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
int N, Q; cin >> N >> Q;
ll k = 0; ll Xk = 0;
Union_find uf(N);
while(Q--){
ll a, b, c; cin >> a >> b >> c;
ll A = 1 + ((a*(1+Xk)) % MOD)%2;
ll B = 1 + ((b*(1+Xk)) % MOD)%N;
ll C = 1 + ((c*(1+Xk)) % MOD)%N;
if(A == 1){
uf.uni(B, C);
}
if(A == 2){
Xk = uf.query(B, C);
cout << Xk << endl;
}
}
}