Tribe Council – solution
Mihai Pătrascu
The solution is based on dynamic programming; however, the ideas that go into it are quite non-trivial. We begin by a simple lemma:
Let us consider a subtree with a fixed root. If there is a way to color the root with color K using only the nodes in the subtree, then there is a way to color the root with any color L<K.
The proof is elementary. The consequence is that we only need to determine the maximum color achievable for the root of a subtree. It is easy to see that splitting the tree in two subtrees can be done by removing an edge. Therefore, our dynamic programming algorithm will try to compute some values for the edges of the tree. More specifically, for each edge U-V we care about the two subtrees rooted in U and V, formed by eliminating the edge. For each subtree, we compute the maximum color the root can be colored with. To do this, we only need information about the edges between the root and its children (from the subtree). This is exactly the information computed by the dynamic program for those edges; a recursive implementation is the easiest way to guarantee that values are computed in the right order.
The final step is now easy. We analyze each edge: if the two vertices can both be colored with the maximum color C, it is trivial to see that we can color one of the with C+1 by considering the subtrees together; otherwise, we can only achieve the maximum of the colors for the two nodes. Obviously, we choose the best edge (which gives the maximum color for one of the vertices).
The time complexity of the algorithm is O(N). The best way to see this is to realize that each edge is analyzed a constant number of times.
There is also a simpler solution, which has time complexity O(N2). This is two try to root the original tree in each possible node, and apply a simple bottom-up dynamic program (this DP step runs in O(N)). Such a solution would have gotten you 30 points. A better solution is to try this simple dynamic program starting from the chief of the tribe. If this algorithm answers K, the real answer to the problem could be either K or K+1 (because you are not considering placing a father before a son in the permutation). By outputing one of these two values you obtain 50 points (it doesn’t matter which one of the two you decide to output, as long as you are consistent for all tests).
#include <stdio.h>
#include <string.h>
#include <assert.h>
#define MAXN 100000
int n;
struct edge {
int cmax[2];
int node[2];
} e[MAXN];
struct edge *epool[2 * MAXN];
struct edge **ebeg[MAXN];
int adj[MAXN];
struct {
int col, mindec;
} nodes[MAXN];
void read_in()
{
int i, j, cnt[MAXN + 1];
freopen("tribe.in", "r", stdin);
scanf("%d", &n);
for(i = 0; i < n - 1; i++)
for(j = 0; j < 2; j++) {
scanf("%d", e[i].node + j);
adj[--e[i].node[j]]++;
}
*cnt = 0;
for(i = 1; i < n; i++)
cnt[i] = adj[i - 1] + cnt[i - 1];
for(i = 0; i < n; i++)
ebeg[i] = epool + cnt[i];
for(i = 0; i < n - 1; i++)
for(j = 0; j < 2; j++)
epool[cnt[e[i].node[j]]++] = e + i;
}
void back(struct edge *e, int side);
int get_maxcol(int node, struct edge *exclude)
{
int i, j, chld, *cnt;
struct edge *p;
if(exclude) {
j = (exclude->node[0] == node);
if(!nodes[node].col && exclude->cmax[j])
get_maxcol(node, NULL);
if(nodes[node].col) {
if(exclude->cmax[j] > nodes[node].mindec)
return(nodes[node].col - 1);
return(nodes[node].col);
}
}
chld = adj[node];
cnt = alloca((chld + 1) * sizeof(int));
memset(cnt, 0, (chld + 1) * sizeof(int));
for(i = 0; i < chld; i++) {
if((p = ebeg[node][i]) == exclude)
continue;
j = (p->node[0] == node);
back(p, j);
if(p->cmax[j] > chld)
cnt[chld]++;
else cnt[p->cmax[j]]++;
}
j = 1;
for(i = 1; i <= chld; i++) {
if(cnt[i]) {
if(i == j)
j++;
continue;
}
while(!cnt[j])
if(++j > chld)
goto out;
cnt[j]--;
}
out:
if(!exclude) {
nodes[node].col = i;
if((i == 1) || (cnt[i - 1] > 1))
nodes[node].mindec = n + 1;
else {
nodes[node].mindec = 0;
for(j = 1; j < i; j++)
if(cnt[j] > 1)
nodes[node].mindec = j;
}
}
return(i);
}
void back(struct edge *e, int side)
{
if(e->cmax[side])
assert(e->cmax[side] != -1);
else {
e->cmax[side] = -1;
e->cmax[side] = get_maxcol(e->node[side], e);
}
}
int main()
{
int i, max;
read_in();
max = 0;
for(i = 0; i < n; i++) {
if(!nodes[i].col)
get_maxcol(i, NULL);
if(nodes[i].col > max)
max = nodes[i].col;
}
fprintf(fopen("tribe.out", "w"), "%dn", max);
return(0);
}
|