Ed Markovich
/*
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=3&problem=76&mosmsg=Submission+received+with+ID+6982490
*/
 
#include <stdio.h>
#include <string.h>
 
#define c2a(x) ( x-'A' )
#define a2c(x) ( 'A'+x )                 
 
#define MAX_DIM 26
 
char graph[MAX_DIM][MAX_DIM];
 
char order[8];
char best_order[8];
int order_len = 0;
 
int min_score = 99999;
 
const char* print_order(char *target) {
 
    static char buf[30] = "";
    char *x = buf;
 
    for (int i=0; i<order_len; ++i) {    
        *x = a2c(*target++);
        ++x;
        *x = ' ';
        ++x;
    }    
 
    return buf;
}
 
// returns the biggest bandwidth for the current ordering. Since the objective is to find orderings
// with smallest bandwidth, if we detect an intermediate bandwidth that's large than the known min,
// stop evaluating this one , it can't be the winner.
int score2() {    
 
    // the biggest 'bandwidth' of this ordering so far.
    int local_max = 0; 
 
    // I moves from the left, J moves from the right since this helps us find the 'biggest' connections
    // first. we know that once distance between i and j is less than the previously discovered local_max,
    // there's no point looking closer, hence j>i+local_max condition
    for (int i=0; i< order_len; ++i) {
        for (int j=order_len-1; j>i+local_max; --j) {
 
            // We know I and J are more than 'local_max' appart - now check if the connection exists
            if (graph[order[i]][order[j]]) {                    
                local_max = j-i;     
 
                // We already know that this ordering is of at least local_max bandwidth. if that's larger
                // than the best known min_score, it tells us this ordering is not a winner. So we just
                // return the local max even though it may not be the biggest bandwidth for this ordering.
                if (local_max > min_score) { 
                    return local_max;
                }
                // Distance btw. I and J is getting narrower, we know we can't do better on this I
                break; 
            }
        }
    }
    return local_max;
}
 
// generate (almost) all the permutations of the nodes - ie all possible orderings.
void permute(int position) {
    int i,j,x=0;
 
    // If we're moving the left-most node around, don't bother moving it past the middle
    // point, since all orderings like were already evalauted in the mirror image version.
    int limit = position > 0 ? order_len : order_len/2 + 1;
    bool last_one = position == order_len -1;
 
    for (i=position ; i<limit; ++i) {
 
        int tmp = order[i];
        order[i] = order[position];
        order[position] = tmp;        
 
        if (last_one) {            
            // Score this position....
            int x = score2();
 
            // If this is the best (least) score so far, or we've tied the best and are
            // smaller alphabetically, treat the current result as the best
            if (x < min_score || 
                    (x == min_score && memcmp(best_order, order, sizeof(order)) > 0 )) {
                memcpy(best_order, order, sizeof(order));
                min_score = x;
            }            
 
            return;         
        } else {
            permute(position+1);
        }
 
        order[position] = order[i];            
        order[i] = tmp;
    }    
}
 
// processes this input format A:FB;B:GC;D:GC;F:AGH;E:HD
// A:FB means A has edge to F and B. I call A the 'from'/node1 node and F and B are 'to'/node2 nodes
void parse_line(const char* line) {
 
#define add_node(node) if (!nodes_that_exist[node]) { \
        nodes_that_exist[node] = 1;                   \
        *x = node;                                    \
        ++x;                                        }  
 
    char *x = order; // used to create an initial order to permute
 
    min_score = 999999;    
    memset(graph, 0, sizeof(graph)); // 26x26 matrix where graph[a][b] == 1 means there's an edge
 
    // quick and dirty 'set' equivalent to make sure we don't add the same node into the ordering twice
    char nodes_that_exist[MAX_DIM];
    memset(nodes_that_exist, 0, sizeof(nodes_that_exist));
 
    bool new_node = true;  // tells us that the next node is the 'from' node
    int node1;             // the current 'from' node
    while (*line != '\0') {
 
        if (*line == ';') {
            ++line; 
            new_node = true;
        }
 
        if (new_node) { 
            new_node = false;
            node1 = c2a(*line);
            add_node(node1);
            line +=2;
        }    
 
        int node2 = c2a(*line);
        graph[node1][node2] = graph[node2][node1] = 1;
 
        add_node(node2);
 
        ++line;        
    }
 
    order_len = x - order;
    *x = -1;    
}
 
int main() {
    char val[100];
 
    while (1) {
        scanf("%s", val);
        if (val[0] == '#') { return 0; }    
 
        parse_line(val);        
        permute(0);
 
        printf("%s-> %d\n", print_order(best_order), min_score);    
    }
 
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License