Talk:Arctic Network

From Progteam

Jump to: navigation, search

Is this really a minimum spanning tree problem? I don't think it is, because there are no edges to the graph. It seems to me that this is a proximity problem. It's late and I'm tired, but after a quick glance at the problem it looks like one needs to determine the diameter of the point set-that is find the distance between the two furthest points in the plane. Of course, then there are also S satellite channels which have no distance requirements, so one needs to find the (S - 1) furthest neighbors, and the least one of these will be the maximum distance required to span. I will take a closer look tomorrow.

Mfv2 00:53, 11 September 2007 (EDT)

The reason that I think of it as a MST problem is that distance problems are really just graph problems with a fully connected graph. But I'm now thinking that maybe it's simpler than an MST. I still think it's a graph, but really you just want to sort all the edges in the graph, and add the edges, smallest first, until the graph is connected. Once the graph is connected, then throw away as many of these edges (in descending order) as you can by including Satellite links. Hjfreyer 16:17, 18 September 2007 (EDT)

My attempted solution

Is here:


import java.util.*;

public class Main{

    public static Scanner in;
 
    public static void main(String[] args){
        in=new Scanner(System.in);

        doStuff();
    }

    public static void doStuff(){
        int N=in.nextInt();

        for(int i=0;i<N;i++){
            solve();
        }
    }

    public static void solve(){
	int S=in.nextInt();
	int P=in.nextInt();

	PropertyMatrix<Double> dist=new PropertyMatrix(P,P);

	{
	    // dimensions are <which station>,<x or y>
	    PropertyMatrix<Integer> plot=new PropertyMatrix(P,2);
	    for(int j=0;j<P;j++)
		for(int i=0;i<=1;i++)
		    plot.set(in.nextInt(),j,i);
			
	    
	    for(int i=0;i<P;i++){
		for(int j=0;j<=i;j++){
		    if(j==i){
			dist.set(Double.MAX_VALUE,i,j);
		    } else {
			double d=distform(plot.get(i,0),
					  plot.get(i,1),
					  plot.get(j,0),
					  plot.get(j,1));
			dist.set(d,i,j);
			dist.set(d,j,i);
		    }
		}
	    }
	}
	// Dist now has the distances between the points

	Tuple[] sorted_tmp=dist.sortedEntries();
	List<Tuple> sorted=new LinkedList<Tuple>();

	for(int i=0;i<sorted_tmp.length;i+=2){
	    if(sorted_tmp[i].get(0)!=sorted_tmp[i].get(1))
		sorted.add(sorted_tmp[i]);
	}

	//		for(Tuple t:sorted)
	//	    System.out.println(dist.get(t));

	DisjointSet<Integer> forest=new DisjointSet<Integer>();
	for(int i=0;i<P;i++)
	    forest.add(i);

	List<Tuple> mst=new ArrayList<Tuple>();
	
	for(Tuple t:sorted){
	    if(forest.sets==S)
		break;

	    mst.add(t);
	    
	    forest.union(t.get(0),t.get(1));	    
	    System.out.printf("%d: %.2f\n",forest.sets,dist.get(t));
	}


	double res=dist.get(mst.get(mst.size()-1));
	System.out.printf("%.2f\n",Math.round(100.0*res)/100.0);
    }
    public static double distform(int x1,int y1, int x2,int y2){
	double dx=x2-x1;
	double dy=y2-y1;
	
	return Math.sqrt(Math.pow(dx,2)+Math.pow(dy,2));
    }
}

class PropertyMatrix<T extends Comparable<T>> {
    private int[] dim;
    private int[] place_value;
    private T[] props;
    
    // This line is included for my sanity, not strictly necessary
    @SuppressWarnings("unchecked")
    public PropertyMatrix(int... size) {
	dim=size;

	place_value=new int[size.length];
	
	int totalval=1;
	for(int i=0;i<dim.length;i++) {
	    place_value[i]=totalval;
	    totalval*=dim[i];
	}

	props=(T[])new Comparable[totalval];
    }    

    public T get(int... entry) {
	return props[index(entry)];
    }
    
    public void set(T prop,int... entry){
	props[index(entry)]=prop;
    }

    private int index(int... entry){
	int fin=0;
	for(int i=0;i<entry.length;i++)
	    fin+=entry[i]*place_value[i];
	
	return fin;
    }

   /* The rest is totally optional */
    public void setAll(T init){
	for(int i=0;i<props.length;i++)
	    props[i]=init; 
    }

    public T get(Tuple t){
	return get(t.tuple);
    }

    /* Returns the entries in ascending order */
    /* Has not been tested on 3 dimensional matrices */
    public Tuple[] sortedEntries(){
	Tuple[] sorted=new Tuple[props.length];

	for(int i=0;i<props.length;i++){
	    int[] coord=new int[dim.length];
	    
	    int tmp=i;

	    for(int n=0;n<coord.length;n++){
		coord[n]=tmp%dim[n];
		tmp/=dim[n];
	    }
	    

	    sorted[i]=new Tuple(coord);
	}

	Arrays.sort(sorted,new Comparator<Tuple>(){
		public int compare(Tuple a, Tuple b){
		    return get(a).compareTo(get(b));
		}
	    });
	
	return sorted;
    }
}

class Tuple{
    public int[] tuple;

    public Tuple(int... entries) {
	tuple=entries;
    }    

    public int get(int i){
	return tuple[i];
    }
    
    /* just for debugging */
    public String toString(){
	if(tuple.length==0)
	    return "()";
	StringBuilder s=new StringBuilder();
	s.append(tuple[0]);
	for(int i=1;i<tuple.length;i++)
	    s.append(", ").append(tuple[i]);
	return s.toString();
    }
}

class DisjointSet<T> {
    HashMap<T,T> parent;
    Random rand;
    int sets=0;

    public DisjointSet(){
	rand=new Random();
	parent=new HashMap<T,T>();
    }

    public void union(T a, T b){
	if(a.equals(b))
	    return;
	if(parent.get(a).equals(a) && parent.get(b).equals(b)){
	    if(rand.nextBoolean())
		parent.put(b,a);
	    else
		parent.put(a,b);
	    sets--;
	    return;
	}
	union(find(a),find(b));	
    }
    
    public T find(T x){
	if(parent.get(x).equals(x))
	    return x;
	T p=find(parent.get(x));
	parent.put(x,p);
	
	return p;
    }

    public boolean equal(T a, T b){
	return find(a).equals(find(b));
    }

    public void add(T t){
	parent.put(t,t);
	sets++;
    }
}
Personal tools