140 - Bandwidth

[brianfry713]

Clear used before calling backtrack

[shipu_a]

Try this

Code: Select all

Z:A

[snublefot]

I've been staring at this code for days, and I can't seem to identify the problem.

I get WA, but all the test cases come through just great.

If anyone could help, I'd be very grateful.

Code: Select all

import java.io.*;
import java.util.*;

class Main
{
	int count;
	char node_names[];
	boolean[][] graph;
	int no_of_nodes;
	int min_length;
	int[] min_permutation;
	int[] current_permutation;
	boolean in_the_permutation[];
	int permutation_depth;
	static String ReadLn (){  // utility function to read from stdin

		int maxLg = 500;
		byte lin[] = new byte [maxLg];
		int lg = 0, car = -1;
		try{
			while (lg < maxLg)
			{
				car = System.in.read();
				if ((car < 0) || (car == '\n')) break;
				lin [lg++] += car;
			}
		}
		catch (IOException e){
			return (null);
		}

		if ((car < 0) && (lg == 0)) return (null);  // eof
		return (new String (lin, 0, lg));
	}

	static String readNeLn(){
		String ret = "";

		while(ret.length() == 0){
			ret = ReadLn();
			if(ret == null){
				return ret;
			}
		}
		return ret;
	}

	public static void main(String args[])  // entry point from OS
	{
		Main myWork = new Main();  // create a dynamic instance
		myWork.Begin();            // the true entry point
	}

	void Begin(){
		while(true){
			//Program stops when end of input ('#') is reached
			String input_string = readNeLn();
			char[] input = input_string.toCharArray();				
			if(input[0] == '#'){
				//end of input
				System.exit(0);
			}

			no_of_nodes = 0;
			node_names = new char[8];

			//Get the node names first, then sort them alphabetically
			for(int i=0;i<input.length;i++){
				char next_char = input[i];
				if(next_char >= 'A' && next_char <= 'Z'){
					get_index(next_char);
				}
			}
			//Shrink the node name list
			char n_copy[] = new char[no_of_nodes];
			for(int i=0;i<n_copy.length;i++){
				n_copy[i] = node_names[i];
			}
			node_names = n_copy;

			//Sort using selection sort
			for (int i = 0; i < no_of_nodes; i++) {
				int smallest_letter_index = i;
				for (int j = i+1; j < no_of_nodes; j++) {
					if(node_names[j] < node_names[smallest_letter_index]){
						smallest_letter_index = j;
					}
				}
				char temp = node_names[i];
				node_names[i] = node_names[smallest_letter_index];
				node_names[smallest_letter_index] = temp;
			}

			graph = new boolean[no_of_nodes][no_of_nodes];

			//Read the input again and populate the graph
			for(int i=0;i<input.length-1;i++){
				char nodename = input[i];
				int u = get_index(nodename);
				i++;

				//skip the colon
				i++;

				char next_char = input[i];
				while(next_char != ';' && i<input.length-1){
					int v = get_index(next_char);
					graph[u][v] = true;
					graph[v][u] = true;
					i++;
					next_char = input[i];
				}
			}

			min_permutation = new int[no_of_nodes];
			current_permutation = new int[no_of_nodes];
			min_length = Integer.MAX_VALUE;
			in_the_permutation = new boolean[no_of_nodes];
			permutation_depth = 0;
			

			//Find every permutation 
			//Calculate the value of the permutation
			//Compare to and possibly swap out the best permutation thus far

			//first node in the permutation
			for(int i=0;i<no_of_nodes;i++){
				permute(i);
			}

			//Print the solution
			for (int i = 0; i < no_of_nodes; i++) {
				System.out.print(node_names[min_permutation[i]]+" ");
			}
			System.out.println("-> "+min_length);
			
		}
	}

	void permute(int index){
		in_the_permutation[index] = true;
		current_permutation[permutation_depth] = index;
		permutation_depth++;
		if(permutation_depth  == no_of_nodes){
			compare_permutations();
		}else{
			for (int i = 0; i < no_of_nodes; i++) {
				if(!in_the_permutation[i]){
					permute(i);
				}
			}
		}

		in_the_permutation[index] = false;
		permutation_depth--;
	}

	void compare_permutations(){
		int max_distance_this_permutation = 0;

		for (int i = 0; i < no_of_nodes; i++) {
			int u = current_permutation[i];
			for (int j = 0; j < no_of_nodes; j++) {
				int v = current_permutation[j];
				if(graph[u][v]){
					int distance = j-i;
					if(distance > max_distance_this_permutation){
						max_distance_this_permutation = distance;
					}
				}
			}
		}

		if(max_distance_this_permutation < min_length){
			min_length = max_distance_this_permutation;
			for (int i = 0; i < no_of_nodes; i++) {
				min_permutation[i] = current_permutation[i];
			}
		}
	}
	int get_index(char c){
		int index = -1;
		for(int j=0;j<no_of_nodes;j++){
			if(node_names[j] == c){
				index = j;
			}
		}
		if(index == -1){
			node_names[no_of_nodes] = c;
			index = no_of_nodes;
			no_of_nodes++;
		}

		return index;
	}
}

[brianfry713]

Try running your code on the sample input.

[rafastv]

Hi, some tips for you.

1) Do not assume the 8 nodes will be the 8 first letters of the alphabet.

2) Strip spaces from the line (A: B; C : D => A:B;C:D).

3) There may be repeating neighbors like A:BB.

4) Beware of Maximal Cliques (you should think of a way to avoid them and gain some speed up).