Colored Sticks

From Progteam

Revision as of 18:11, 22 February 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by hjfreyer.


Colored Sticks
Problem Number 2513
Sorter: hjfreyer
Source: The UofA Local 2000.10.14
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2513



Colored Sticks is problem number 2513 on the Peking University ACM site. The problem concerns a long list of sticks, each end of which has a color. The question is, given that list, can one arrange the sticks in a single straight line such that the color of the end of each stick matches the end of the next stick. For example, with a list of sticks:

  • (Red Yellow)
  • (Green Yellow)
  • (Blue Green)

a valid straight line would be (Red Yellow) (Yellow Green) (Green Blue). The problem only asks if such an arrangement is possible.

Contents

Data Representation

The sticks are represented in the solution as a graph, with vertices representing the colors, and edges representing the sticks. For convenience and speed, the names of the colors are substituted with numbers 0...N-1, N being the number of distinct colors among all the sticks.

Algorithm

Given this graph, we wish to know if it's possible to traverse it touching every node, without ever hitting a "dead end" before all the vertices have been visited. If this can be done, we know that every edge can line up, end to end, without ever reaching an end that has no matching stick, until all sticks have been used. This problem is identical to the problem, given a graph, can you draw it on paper without picking up your pencil?

Rather than traversing this graph to find the answer (which could take perhaps exponential time), we will solve this by observing a property of graphs: the Even-Odd Vertex Rule. The rule states that any vertex of odd degree will end up at the bottom (or top) of a depth first search, and will have to be backtracked from. In the context of this problem, it implies that any DFS of the graph will start or end at a vertex of odd degree. This also means when drawing a shape on paper, you will be unable to continue drawing without backtracking when you reach an odd vertex.

Given the fact that the DFS stops and backs up at any odd vertex, and we want to get from the beginning to end without ever backing up, three cases emerge:

  • The graph has no odd vertices, and you can start at any vertex and continue through the graph to every other one without backtracking
  • The graph has two odd vertices, where one acts as the beginning of a successful traversal with no backtracks, and the other acts as the end (at both of these points, a backtrack is fine, because it will only occur once every vertex is visited), or
  • The graph has more than 2 odd vertices, in which case the DFS will necessarily terminate and backtrack after reaching the third (and forth, and fifth...) odd vertex.

Therefore, one simply needs to count the number of nodes of odd degree. If it's 0 or 2, it's possible, otherwise, it isn't.

Caveats

A simple situation where this fails is in a disconnected graph. A list of sticks like this:

  • (Blue Red)
  • (Green Yellow)
  • (Green Yellow)

has only two vertices with odd edges (Blue and Red), but cannot be arranged into a stick because the graph is not connected. A simple DFS to check the graph's connectivity is necessary.

Also, a very annoying thing that is done by the judging software on this problem is it sends a completely empty input. This will break code that does not account for this, however illogical it may be.

Solution

import java.util.*;

public class Main{

    public static Scanner in;

    public static HashMap<String,Integer> colorNum;
    public static LinkedList<Edge> edges;

    public static Graph G;
   
    public static void main(String[] args){

	in=new Scanner(System.in);

	colorNum=new HashMap<String,Integer>();

	edges=new LinkedList<Edge>();

	int cur=0;
	while(in.hasNext()){
	    String color1=in.next(),color2=in.next();
	    int num1,num2;

	    if(!colorNum.containsKey(color1)){
		num1=cur;
		colorNum.put (color1,cur++);
	    }
	    else
		num1=colorNum.get(color1);


	    if(!colorNum.containsKey(color2)){
		num2=cur;
		colorNum.put(color2,cur++);
	    }
	    else
		num2=colorNum.get(color2);

	    Edge e=new Edge();

	    e.i=num1;
	    e.j=num2;

	    edges.add(e);
	}
   
	G=new Graph(colorNum.size());

	//This is just stupid
	if(colorNum.size()==0){
	    System.out.println("Possible");
	    return;
	}
       
	for(Edge e:edges){
	    G.addEdge(e.i,e.j);
	}
   
	//Graph is built!
	edges=null;
	colorNum=null;

	System.gc();

	solve();
    }
   
    public static void solve(){
	//compress(G.getFirst());

	int odd=0;

	for(Vertex v:G.verts){
	    if(1==v.degree()%2)
		odd++;
	}

	if(G.isConnected()&&(2==odd||0==odd))
	    System.out.println("Possible");
	else
	    System.out.println("Impossible");
    }
}

class Graph{
    public Vertex[] verts;
   
    public Graph(int order){
	verts=new Vertex[order];
   
	for(int i=0;i<order;i++){
	    verts[i]=new Vertex();
	}
    }
   
    public void addEdge(Vertex i,Vertex j){
	i.adj.add(j);
	j.adj.add(i);
    }

    public void addEdge(int i,int j){
	addEdge(verts[i],verts[j]);
    }

    public void removeEdge(Vertex i,Vertex j){
	i.adj.remove(j);
	j.adj.remove(i);
    }
    
    public Vertex getFirst(){
	return verts[0];
    }

    public boolean isConnected(){
	return verts.length==DFS(getFirst());

    }

    int DFS(Vertex v){
	if(v.visited)
	    return 0;
	
	v.visited=true;

	int num=1;

	for(Vertex x:v){
	    num+=DFS(x);
	}
	
	return num;
    }
}

class Vertex implements Iterable<Vertex>{
    public boolean visited=false;
    public List adj;

    public Vertex(){
	adj=new List();
    }

    public int degree(){
	return adj.size;
    }

    public Iterator<Vertex> iterator(){
	return adj.iterator();
    }
}

class List implements Iterable<Vertex>{
    
    class Node{
	Vertex el;
	Node next;
    }

    class Iter implements Iterator<Vertex>{
	Node ptr;

	public boolean hasNext(){
	    return ptr.next!=null;
	}
	public Vertex next(){
	    ptr=ptr.next;return ptr.el;
	}
	public void remove(){}
    }

    Node header;
    int size;
   
    public List(){
	header=new Node();
	header.next=null;
	size=0;
    }
    
    public boolean add(Vertex v){
	Node n=new Node();
	n.el=v;
	n.next=header.next;
	header.next=n;
	++size;
	return true;
    }

    public boolean remove(Vertex v){
	for(Node n=header;n.next!=null;n=n.next)
	    if(n.next.el.equals(v)){
		n.next=n.next.next;
		--size;
		return true;
	    }
	return false;
    }
    
    public Iter iterator(){
	Iter i=new Iter();
	i.ptr=header;
	return i;
    }
}

class Edge{
    int i,j;
}

Personal tools