From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details
This question is the second question(Carried 35 marks out of 100) for the Round 1 of 2013 hacker cup. only top 500 contestants will be moved to Round 2.
Problem Statement
You are designing a new encryption system that works in the following way:
For server-client communication you need a key k, composed of m sections, each of length l, and the key consists only of lowercase characters in the set {a, b, c, d, e, f}. The server has a key k1 and the client has a key k2 where:
- k1 = f(k). f is a function that receives a key and replace some random letters by ? indicating that those characters can be any lowercase letter of the set described before.
- k2 = f(g(k)). g is a function that takes a key and produces a random permutation of its m sections. And f is the function defined above.
For example: let m = 3, l = 2
- f(‘abacbc’) = ‘?ba??c’
- g(‘abacbc’) = ‘acbcab’ (each section was moved one place to the left).
Your task is given k1 and k2, find key k. If there are several solutions, print the lexicographically smallest key. And if there is no solution at all, print “IMPOSSIBLE” (without the quotes).
Input description:
The first line has a single integer T, which corresponds to the number of test cases. T test cases follows: the first line of the test case corresponds to the integer m, the second line contains the string k1 and the third line contains the string k2.
Constraints:
- T <= 20
- 0 < |k1| <= 100
- 0 < m <= 50
- |k2| = |k1|
- It is guaranteed that m is always a divisor of |k1|
- k1 and k2 consist of {a, b, c, d, e, f, ?}
Output description:
For test case i, numbered from 1 to T, output “Case #i: “, followed by the lexicographically smallest key or “IMPOSSIBLE”.
Example Input
5 2 abcd c?ab 3 ab?c?c ac?c?? 3 ab?c?c aabbdd 2 aa bb 2 abcd cdab
Example Output
Case #1: abcd Case #2: abacac Case #3: IMPOSSIBLE Case #4: IMPOSSIBLE Case #5: abcd
Solution:
Basically we can divide the k1 and k2 both into m sets of l length, now this problem is reduced to map the sets in such a way that the generated key is lexicographically smallest.
For example 2 of the input set where k1 = ab?c?c and k2 = ac?c??.
ab => ?? (2)
?c => ac, ?c, ?? (0, 1, 2)
?c => ac, ?c, ?? (0, 1, 2)
here numbers are the index of the set in k2Sets.
So we have to first consider where only 1 set is mapped and remove that index from other possibilities and keep on doing it till we dont get only 1 possibility, @ that point we have to take the first set in k1 with smallest possibility and consider the set from k2 which is lexicographically smallest.
Here is the java code for the same:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Security {
public static String IMPOSSIBLE = "IMPOSSIBLE";
public String getKey(int m, String k1, String k2){
int l = k1.length()/m;
String[] k2Sets = getSets(k2, m, l);
String[] k1Sets = getSets(k1, m, l);
String[] finalSet = new String[m];
ArrayList<ArrayList<Integer>> k1Arr = new ArrayList<ArrayList<Integer>>();
for(String oneSet: k1Sets){
ArrayList<Integer> countList = new ArrayList<Integer>();
int index =0;
for(String twoSet: k2Sets){
if(isMatching(oneSet, twoSet)){
countList.add(index);
}
index++;
}
k1Arr.add(countList);
if(countList.size() == 0){
return IMPOSSIBLE;
}
//System.out.println(countList);
}
while(true){
int minSize = getNextMinSize(k1Arr);
if(minSize == -1){
break;
}
for(int i =0; i < k1Arr.size(); i++){
ArrayList<Integer> countList = k1Arr.get(i);
if(countList.size() == minSize){
if(minSize == 1)
{
finalSet[i] = getCommonString(k1Sets[i], k2Sets[countList.get(0)]);
try{
remove(k1Arr, countList.get(0), i);
}catch (Exception e) {
return IMPOSSIBLE;
}
}else{
Wrapper wrapper = getMinimum(k1Sets[i], k2Sets, countList);
finalSet[i] = wrapper.str;
try{
countList.clear();
remove(k1Arr, wrapper.index, i);
}catch (Exception e) {
return IMPOSSIBLE;
}
break;
}
}
}
}
String res = "";
for(String str: finalSet){
res += str;
}
String fRes ="";
for(Character c: res.toCharArray()){
if(c == '?'){
c = 'a';
}
fRes += c;
}
return fRes;
}
private Wrapper getMinimum(String oneSet, String[] k2Set, ArrayList<Integer> countList){
ArrayList<Wrapper> strList = new ArrayList<Wrapper>();
for(Integer count: countList){
Wrapper wrapper = new Wrapper(getCommonString(oneSet, k2Set[count]), count);
strList.add(wrapper);
}
Collections.sort(strList, new WrapperComparator());
return strList.get(0);
}
class Wrapper{
String str;
int index;
public Wrapper(String str, int index) {
this.str= str;
this.index = index;
}
}
class WrapperComparator implements Comparator<Wrapper>{
@Override
public int compare(Wrapper o1, Wrapper o2) {
return o1.str.compareTo(o2.str);
}
}
private static String getCommonString(String str1, String str2){
String res = "";
for(int i = 0; i < str1.length(); i++){
char c1 = str1.charAt(i);
char c2 = str2.charAt(i);
if(c1 != '?'){
res += c1;
}else if(c2 != '?'){
res += c2;
}else{
res += '?';
}
}
return res;
}
private static int getNextMinSize(ArrayList<ArrayList<Integer>> k1Arr){
int minSize = -1;
for(ArrayList<Integer> countList: k1Arr){
int size = countList.size();
if(size == 0)
continue;
if(minSize == -1 || size < minSize){
minSize = size;
}
}
return minSize;
}
private static void remove(ArrayList<ArrayList<Integer>> k1Arr, Integer toRemove, int fromIndex) throws Exception{
int index = 0;
for(ArrayList<Integer> countList: k1Arr){
if(countList.size() > 0)
{
countList.remove(toRemove);
if(countList.size() == 0 && index != fromIndex){
throw new Exception("IMPOSSIBLE");
}
}
index++;
}
}
private static String[] getSets(String input, int m, int l){
String[] k2Sets = new String[m];
int count = 0;
for(int i=0; i< input.length(); i+=l){
String oneSet = input.substring(i, i+l);
k2Sets[count] = oneSet;
count++;
//System.out.println(oneSet);
}
return k2Sets;
}
public static boolean isMatching(String str1, String str2){
for(int i = 0; i < str1.length(); i++){
char c1 = str1.charAt(i);
char c2 = str2.charAt(i);
if(!(c1 == '?' || c2 == '?' || c1 == c2)){
return false;
}
}
return true;
}
}
