Indoorienteering: Difference between revisions

From programming_contest
Jump to navigation Jump to search
Newer edit →
imported>Kmk21
Created page with "= Introduction = This problem whether a graph contains a hamiltonian cycle of a given length = Solutions= == Greedy/BFS == === Idea === So long as each internal node uses..."
 
imported>Kmk21
No edit summary
Line 1: Line 1:
= Introduction =
= Introduction =
This problem whether a graph contains a [[hamiltonian cycle]] of a given length
This problem whether a graph contains a [[hamiltonian cycle]] of a given length.


= Solutions=
= Solutions=
== Greedy/BFS ==
== Brute Force ==
=== Idea ===
=== Idea ===
So long as each internal node uses both of its values with some adjacent node, it doesn't matter which edges are used by which values. This is only true because it's a tree. If there were loops, it would get much more complicated.
Hamiltonian Cycle is NP complete ....must do brute force. Iterate over all possible permutations of points and check the length.


Two cases:
Further, it's clear it's brute-force-ish because n=14.
# No internal nodes: just assign the same to values to the nodes
# Internal nodes: pick a "start" internal node. Assign it two values (0 and 1 sound good). Alternating between the two values, choose an adjacent node, and fix it's first value to the chosen value from our start node. This guarantees that both values are used by some edge. Run BFS, and when you reach a node, choose the next unused value as the nodes second value (remember we assigned it's first value from the preceding node), and the assign the first values of all it's successor nodes to one of the two values (ensuring both are used somewhere). When you reach an edge node, assign any frequency.


===Runtime===
===Runtime===
* n
* n! = 87178291200


=== Code ===
== Fixed Starting Point ==
=== Idea ===
It's a cycle, so therefore we'll reach every point. If we fix a start point, we eliminate a dimension.
===Runtime===
* (n-1)! = 6227020800
 
== Divide and Conquer ==
=== Idea ===
Split the points up into two equal halves. Compute the lengths of each side to see if any of the possibilities add up
===Runtime===
* (n-1 choose n/2) * n/2! * n/2!
* (n-1)!/(n/2!)^2 * (n/2!)^2
* (n-1)! :(


==== Solution - Java ====
== Divide and Conquer with Hashmap ==
<syntaxhighlight line lang="java">
=== Idea ===
import java.util.*;
When you compute the first side, store all the lengths into the hashset. When you compute the second half, simply check whether the hashmap contains total length minus length second half length.
public class h {
===Runtime===
Scanner in=new Scanner(System.in);
* (n-1 choose n/2) * (n/2! + n/2!)
public static void main(String[] args) {
* n-1!/(n/2!)^2 * 2 * n/2!
new h().go();
* 2 * (n-1)! / (n/2!) = 17,297,280
}
private void go() {
int n=in.nextInt();
int ord=0;
HashMap<Integer, HashSet<Integer>>hm=new HashMap<Integer,HashSet<Integer>>();
for(int i=1;i<n;i++){
int ii=in.nextInt();
int j=in.nextInt();
if(!hm.containsKey(ii))hm.put(ii, new HashSet<Integer>());
if(!hm.containsKey(j))hm.put(j, new HashSet<Integer>());
hm.get(ii).add(j);
hm.get(j).add(ii);
}
TreeSet<Integer> visited=new TreeSet<Integer>();
int[][] ass=new int[n+1][2];
for(int i=0;i<ass.length;i++)for(int j=0;j<ass[0].length;j++)ass[i][j]=-1;
Queue<Integer> q=new LinkedList<Integer>();
for(int i:hm.keySet())if(hm.get(i).size()!=1){//Start with a non-leaf node
q.add(i);
ass[i][0]=ord++;//assumption is this comes from previous node
break;
}
if(q.isEmpty()){//degenerate case
System.out.println("0 1");
System.out.println("1 0");
System.exit(0);
}
while(!q.isEmpty()){
int on=q.poll();
int s=1;
ass[on][1]=ord++;
visited.add(on);
for(int i:hm.get(on)){
if(!visited.contains(i)){
ass[i][0]=ass[on][s++%2];//for most nodes we can just use the new frequency...but for first node, gotta ensure both get used..so just alternate
q.offer(i);
}
}
}
for(int i=1;i<n+1;i++)System.out.printf("%d %d\n",ass[i][0],ass[i][1]);
}
}
</syntaxhighlight>


[[Category:nwerc2014]]
[[Category:nwerc2014]]
[[Category:ICPC Problems]]
[[Category:ICPC Problems]]
[[Category:BFS]]
[[Category:Graph]]
[[Category:Greedy]]
[[Category:NP]]
[[Category:Combinatorics]]
[[Category:Algorithm Medium]]
[[Category:Algorithm Medium]]
[[Category:Implementation Medium]]
[[Category:Implementation Medium]]

Revision as of 21:59, 31 January 2015

Introduction

This problem whether a graph contains a hamiltonian cycle of a given length.

Solutions

Brute Force

Idea

Hamiltonian Cycle is NP complete ....must do brute force. Iterate over all possible permutations of points and check the length.

Further, it's clear it's brute-force-ish because n=14.

Runtime

  • n! = 87178291200

Fixed Starting Point

Idea

It's a cycle, so therefore we'll reach every point. If we fix a start point, we eliminate a dimension.

Runtime

  • (n-1)! = 6227020800

Divide and Conquer

Idea

Split the points up into two equal halves. Compute the lengths of each side to see if any of the possibilities add up

Runtime

  • (n-1 choose n/2) * n/2! * n/2!
  • (n-1)!/(n/2!)^2 * (n/2!)^2
  • (n-1)! :(

Divide and Conquer with Hashmap

Idea

When you compute the first side, store all the lengths into the hashset. When you compute the second half, simply check whether the hashmap contains total length minus length second half length.

Runtime

  • (n-1 choose n/2) * (n/2! + n/2!)
  • n-1!/(n/2!)^2 * 2 * n/2!
  • 2 * (n-1)! / (n/2!) = 17,297,280
Retrieved from "https://wiki.speedyguy17.info/index.php?title=Indoorienteering&oldid=262"