Facebook Hacker Cup 2013 Round 1 – Security

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, ?}

My Solution
When I saw this problem the first thing that I thought was “Is an Assignation Problem”.

1. Create a bipartite graph with Strings
2. Add a Cost on each Edge
3. Run a Min Cost Max Flow
4. Detect which edges were used

My Implementation in Java:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
    BufferedReader in;
    StringTokenizer str;
    PrintWriter out;

    String next() throws IOException {
        while ((str == null) || (!str.hasMoreTokens())) {
            str = new StringTokenizer(in.readLine());
        }
        return str.nextToken();
    };

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    };

    // SOLUTION BEGIN
    int T, m;
    String k1, k2;

    BigInteger INF = new BigInteger("9999993919911741000425436580141602948346923222862262837729229258431798216982848864256");
    int[][] cap = new int[110][110];
    BigInteger[][] cost = new BigInteger[110][110];

    void minCostMaxFlow(int numVertices, int s, int t) {
        while(true) {
            int[] prev = new int[numVertices];
            BigInteger[] dist = new BigInteger[numVertices];
            for(int i=0; i<numVertices ;i++) {
                prev[i] = 0;
                dist[i] = INF;
            }

            dist[s] = BigInteger.ZERO;
            while (true) {
                boolean updated = false;
                for (int i = 0; i < numVertices; ++i){
                    if (dist[i].compareTo(INF) < 0) {
                        for (int j = 0; j < numVertices; ++j) {
                            if(cap[i][j] > 0) {
                                if(dist[i].add(cost[i][j]).compareTo(dist[j]) < 0) {
                                    dist[j] = dist[i].add(cost[i][j]);
                                    prev[j] = i;
                                    updated = true;
                                }
                            }
                        }
                    }
                }
                if (!updated) break;
            }
            if (dist[t].compareTo(INF) >= 0) break;
            for(int cur=t; cur!=s ; cur=prev[cur]) {
                --cap[ prev[cur] ][cur];
                ++cap[cur][ prev[cur] ];
            }
        }
    }

    BigInteger isStrPossible(String a, String b, int index) {
        BigInteger res = BigInteger.ZERO;
        BigInteger fact = new BigInteger(6+"");
        for(int i=0; i<a.length() ;i++) {
            char x = a.charAt(i);
            char y = b.charAt(i);
            if(x == y) continue;
            if(x == '?') {
                if(y != '?') {
                    BigInteger p = new BigInteger((y-'a')+"");
                    p = fact.pow(index +a.length() -1 -i).multiply(p);
                    res = res.add(p);
                }
                continue;
            }
            if(y == '?') continue;
            return null;
        }
        return res;
    }

    String mergeStr(String a, String b) {
        String res = "";
        for(int i=0; i<a.length() ;i++) {
            char x = a.charAt(i);
            char y = b.charAt(i);
            if(x == '?') {
                if(y == '?') res = res + 'a';
                else res = res + y;
            }
            else res = res + x;
        }
        return res;
    }

    String solve2() {
        String[] a = new String[m];
        String[] b = new String[m];
        for(int i=0; i<m ; i++) {
            a[i] = "";
            b[i] = "";
        }

        int l = k1.length() / m;
        for(int i=0; i<m ; i++) {
            for(int j=0; j<l ;j++) {
                a[i] += k1.charAt( i*l+j );
                b[i] += k2.charAt( i*l+j );
            }
        }
        for(int i=0; i<m*2+2 ;i++) {
            for(int j=0; j<m*2+2 ;j++) {
                cost[i][j] = BigInteger.ZERO;
                cap[i][j] = 0;
            }
        }

        for(int i=0; i<m ;i++) {
            for(int j=0; j<m ;j++) {
                cost[i+2][j+m+2] = isStrPossible(a[i], b[j], (m-1-i)*l);
                if(cost[i+2][j+m+2] != null)
                    cap[i+2][j+m+2] = 1;
                else
                    cost[i+2][j+m+2] = BigInteger.ZERO;
            }
        }
        for(int i=0; i<m ;i++) {
            cap[0][i+2] = 1;
            cap[i+m+2][1] = 1;
        }

        minCostMaxFlow(m*2+2, 0, 1);

        int maxi = 0;
        String res = new String();
        for(int i=0; i<m ;i++) {
            for(int j=0; j<m ;j++) {
                if(cap[j+m+2][i+2] > 0) {
                    res = res + mergeStr(a[i], b[j]);
                    maxi++;
                }
            }
        }
        if(maxi != m) return "IMPOSSIBLE";
        return res;
    }

    void solve() throws IOException{
        T = nextInt();
        for(int cas=1; cas<=T ;cas++) {
            m = nextInt();
            k1 = next();
            k2 = next();
            System.out.println("Case #" + cas + ": " + solve2());
        }
    }

    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter writer;

    void run() throws IOException {
//        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        in = new BufferedReader(new FileReader("input2.txt"));
//        out.println("output.txt");
        solve();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s