## Wednesday, November 12, 2014

### Codeforces Round #277 (Div. 2)

Problem C:
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;
int vis;
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.