C. Palindrome Transformation

Solution:

Divide the string into two halves. Depending on which half \(p\) is, we can implement a greedy (an very intuitive) strategy to make that half exactly mirror the other half.

#include <iostream> #include <cstdio> #include <algorithm> #include <string> using namespace std; int N, P; string str; int iabs(int i){ return (i >= 0 ? i : -i); } int needs(int i){ int j = N - i - 1; int dif = iabs((int)str[i] - (int)str[j]); int cdif = 26 - dif; return min(dif, cdif); } void solve(){ int ans = 0; for(int i=0;i<N/2;++i){ ans += needs(i); } if(ans == 0) { printf("%d", ans); return; } P--; int L, R; if(P < N/2) { L = 0; R = N/2; } else { L = N/2; R = N; } int left = 123456, right = -1; for(int i=L;i<R;++i){ if(str[i] != str[N-i-1]){ left = min(left, i); right = max(right, i); } } ans += (right - left) + min(iabs(right - P), iabs(P - left)); printf("%d\n", ans); } int main(){ scanf("%d %d", &N, &P); cin >> str; solve(); return 0; }

Problem D:

D. Valid Sets

Solution:

An interesting graph problem, I learnt a new technique to avoid double counting issues. So we can think about this problem in stages. First stage is, what if we are given that \(d = \infty\)? The problem is reduced to finding the total number of sets possible on the whole tree. Let M(i) be the set containing all sets of a subtree with root i, such that i is an element of all the sets in M(i). Now suppose i has several children, name them u,v, and w. Suppose we know M(u), M(v) and M(w) (here u, v, and w are all the root of their corresponding subtrees). Then we can form sets containing i by the following ways:

1. add i directly into the sets M(u), M(v), and M(w).

2. combine any M(u), M(v), and M(w) and insert node i which will act as a bridge between nodes in M(u) and M(v).

3. a set containing node i by itself.

We will end up with something like |M(i)| = |M(u)||M(v)||M(w)| + |M(u)||M(v)| + ... + |M(v)| + |M(w)| + 1. Recognize the pattern?

Therefore |M(i)| = product of { (|M(j)| + 1) } for all j that is a direct descendant of i.

Now for a given \(d\), we can break the problem into smaller problems in the following manner:

1. for each node \(i\), we find the tree such that \(a_i\) is the smallest in the tree, and all nodes j in the tree satisfy \(|a_i - a_j| \leq d\). This can be done by employing DFS.

2. On such tree, we see that it is exactly similar to the case where \(d = \infty\). So we can calculate \(|M(i)|\) from the resulting tree.

3. Adding up all |M(i)| will give us the desired answer.

However implementing the idea in the above form will result in various double counting, and it happens exactly when we want to count |M(i)| and |M(j)| such that \(a_i = a_j\) and they are connected. I did not know there is a very elegant way to avoid such situations: compute \(M(i)\) in increasing order of \(i\), and whenever we encounter node j such that \(a_i = a_j\), we only consider its contribution if \(i < j\), otherwise we must have accounted for that node in the previous iterations.

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; long long MOD = (long long) 1e9 + 7LL; vector<vector<int> > adj; int val[2003]; int vis[2003]; int N, D; long long dfs(int u, int r){ vis[u] = 1; long long ret = 1LL; for(int i=0;i<adj[u].size();++i){ int v = adj[u][i]; if(vis[v]) continue; if(val[v] == val[r] && v < r) continue; if(val[r] <= val[v] && val[v] - val[r] <= D){ ret *= (1LL + dfs(v,r)); ret %= MOD; } } return ret; } int main(){ int u, v; scanf("%d %d", &D, &N); for(int i=0;i<N;++i){ scanf("%d", &val[i]); } adj = vector<vector<int> > (N+3); for(int i=0;i<N-1;++i){ scanf("%d %d", &u, &v); u--; v--; adj[u].push_back(v); adj[v].push_back(u); } long long ans = 0LL; for(int i=0;i<N;++i){ for(int j=0;j<N;++j) vis[j] = 0; ans += dfs(i,i); ans %= MOD; } cout << ans << endl; return 0; }

Problem E:

Discussed on a separate post.

## No comments:

## Post a Comment