1. sorry for bad style
2. it passes the first set
import java.util.*;
public class A {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i=1; i<=t; i++) {
int n = sc.nextInt();
int l = sc.nextInt();
if( n == 1 || l == 1) {
System.out.println("Case #"+i+": "+"-");
for(int j=1;j<=n;j++) {
String s =sc.next();
//System.out.println(s);
}
continue;
}
HashMap<String,HashSet<String>> map = new HashMap();
for(int j=1; j<=n; j++) {
String s = sc.next();
String first = s.substring(0, 1);
if(map.containsKey(first)) {
HashSet<String> set = map.get(first);
set.add(s.substring(1));
map.put(first, set);
} else {
HashSet<String> set = new
HashSet<String>();
set.add(s.substring(1));
map.put(first, set);
}
}
String sol = solve(map);
if(sol == null) {
System.out.println("Case #"+i+": "+"-");
} else {
System.out.println("Case #"+i+": "+sol);
}
}
}
public static String solve(HashMap<String, HashSet<String>> map) {
if(map.size() == 1) {
HashMap<String,HashSet<String>> map2 = new HashMap();
String str = "";
for(Map.Entry<String,HashSet<String>> e:map.entrySet())
{
str = e.getKey();
if(str.length() == 1) return null;
}
for(String s: map.get(str)) {
String first = s.substring(0, 1);
if(map2.containsKey(first)) {
HashSet<String> set = map2.get(first);
set.add(s.substring(1));
map2.put(first, set);
} else {
HashSet<String> set = new
HashSet<String>();
set.add(s.substring(1));
map2.put(first, set);
}
}
String sol = solve(map2);
if(sol == null) {
return null;
} else {
return str+sol;
}
} else {
int i = 0;
String str1 = "";
String str2 = " ";
HashSet<String> set1 = new HashSet<String>();
HashSet<String> set2 = new HashSet<String>();
for(Map.Entry<String, HashSet<String>> e:
map.entrySet()) {
if(i>=2) break;
if(i==0) {
str1 = e.getKey();
set1 = e.getValue();
} else {
str2 = e.getKey();
set2 = e.getValue();
}
i++;
}
if(set1.size() > set2.size()) {
String temp = str1;
str1 = str2;
str2 = temp;
HashSet<String> t1 = new HashSet(set2);
HashSet<String> t2 = new HashSet(set1);
set2 = t2;
set1 = t1;
}
for(String ss :set2) {
if(!set1.contains(ss)) {
return str1+ss;
}
}
map.remove(str1);
String sol = solve(map);
return sol;
}
}
}
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/a540fa68-ff7e-44bf-8925-a87433654fc3%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
