10054 Necklace TLE issue

All about problems in Volume C. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

10054 Necklace TLE issue

Postby zuzumumba » Sun May 29, 2011 2:18 am

I've gotten the correct output under various test cases I've given it but it's apparently too slow.
Here's my java solution:

import java.util.LinkedList;
import java.util.HashMap;
import java.util.Scanner;

public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
HashMap<Integer, LinkedList<Integer>> map;
LinkedList<Integer> path;
int runs = in.nextInt();
for (int t = 1; t < runs + 1; t++)
{
path = new LinkedList<Integer>();
int beads = in.nextInt();
map = new HashMap<Integer, LinkedList<Integer>>(beads + 5);
int start = -1;
for (int n = 0; n < beads; n++)
{
int color1 = in.nextInt();
int color2 = in.nextInt();
if (n == 0)
start = color1;
if (!map.containsKey(color1))
map.put(color1, new LinkedList<Integer>());
if (!map.containsKey(color2))
map.put(color2, new LinkedList<Integer>());
map.get(color2).add(color1);
map.get(color1).add(color2);
}
System.out.println("Case #" + t);
if (isEuler(map))
{
int prev = start;
int next;
while (map.containsKey(prev))
{
next = map.get(prev).removeFirst();
map.get(next).remove(new Integer(prev));
path.add(prev);
path.add(next);
if (map.get(next).size() == 0)
map.remove(next);
if (map.containsKey(prev))
{
if (map.get(prev).size() == 0)
map.remove(prev);
}
else
break;
prev = next;
}
if (map.isEmpty())
while (!path.isEmpty())
System.out.println(path.removeFirst() + " "
+ path.removeFirst());
else
System.out.println("some beads may be lost");
}
else
System.out.println("some beads may be lost");
if (t != runs)
System.out.println();
}
}
public static boolean isEuler(HashMap<Integer, LinkedList<Integer>> map)
{
if (map.isEmpty())
return false;
for (LinkedList<Integer> list : map.values())
if (list.size() % 2 != 0)
return false;
return true;
}
}
zuzumumba
New poster
 
Posts: 1
Joined: Sun May 29, 2011 2:06 am

Return to Volume C

Who is online

Users browsing this forum: No registered users and 1 guest