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[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.