answer.java

We have a group of N items (represented by integers from 1 to N), and we know that there is some tot

package com.topcoder.match01;

import java.util.Arrays;

public class Answer {
    int N;
    int[][] cost;
    boolean[][] gt;
    int[] last;
    int nq=0;

    public int[] initialize(String[] scosts) {
        N = scosts.length;
        cost = new int[N][N];

        for (int i = 0; i < N; i++) {
            String[] ss = scosts[i].split(" ");
            for (int j = 0; j < N; j++) {
                cost[i][j] = Integer.parseInt(ss[j]);
            }
        }
        gt = new boolean[N][N];
        return last = cheapest();
    }

    

    int[] cheapest() {
        int[] ret = new int[2];
        double min = 1000000000;

        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                if(i==j|| gt[i][j] || gt[j][i]) continue;

                int li=1;int hi=1;int lj=1;int hj=1;

                for (int k = 0; k < N; k++) {
                    if(gt[i][k] && !gt[j][k]) ++hi;
                    if(gt[j][k] && !gt[i][k]) ++hj;
                    if(gt[k][i] && !gt[k][j]) ++li;
                    if(gt[k][j] && !gt[k][i]) ++lj;
                }
                
                double mi=(double)(li)/(double)(li+hi);
                double mj=(double)(lj)/(double)(lj+hj);
                
                mi=Math.min(mi,1.0-mi);
                mj=Math.min(mj,1.0-mj);
                                
                double div=Math.log(1.0+mi*mj);
                
                double currCost=cost[i][j]/div;
                
                if(currCost<min){
                    min=currCost;
                    ret[0]=i+1;
                    ret[1]=j+1;
                }
            }
        }
        if (min > 10000000) {
            return null;
        } else {
            return ret;
        }

    }

    void ford() {
        for (int j = 0; j < N; j++) {
            for (int i = 0; i < N; i++) {
                if (gt[i][j]) {
                    for (int k = 0; k < N; k++) {
                        if (gt[j][k]) {
                            gt[i][k] = true;
                        }
                    }
                }
            }
        }
    }

    public int[] query(boolean result) {
        if (!result) {
            int tmp = last[0];
            last[0] = last[1];
            last[1] = tmp;
            return query(true);
        }
        ++nq;
        gt[last[1] - 1][last[0] - 1] = true;

        ford();

        last = cheapest();
        if (last != null)
            return last;
        else
            return calcResult();
    }

    private class Num implements Comparable {
        int pos;

        Num(int k) {
            pos = k;
        }

        public int compareTo(Object o) {
            Num n = (Num) o;
            if (gt[pos][n.pos])
                return 1;
            else
                return -1;
        }
    }

    int[] calcResult() {
        Num[] tab = new Num[N];
        for (int i = 0; i < N; i++) {
            tab[i] = new Num(i);
        }
        Arrays.sort(tab);

        int[] ret = new int[N];

        for (int i = 0; i < N; i++) {
            ret[i] = tab[i].pos + 1;
        }
        return ret;
    }
}