Meet in the middle

[•Cosmin]

http://infoarena.ro/blog/meet-in-the-middle

[•Steve]

Nice article!

1. We can consider each person in the network a node in a graph with friendship relationships as edges. With a BFS approach, we insert each of person 1's friends in a Hash table. Then we check for each of person 2's friends if he is in the Hash table. If so, we have our solution.

2. Same thing as the first problem, we do a BFS of max depth 3 from person 1 and insert every node we come across into a Hash table. After that, we do a BFS from person 2 of max depth 4. If we find a node that is in the Hash table, we basically have our solution. Reconstruction is pretty straight-forward: we can keep a pointer for each of the visited nodes to the node which we came from, etc.

3. We already know that the 2 subsets we are looking for have the same sum which is equal to the sum of all the elements in the set / 2, so we only need to find the elements of 1 of the 2 subsets. A neat solution would be splitting the set into 2 random disjoint subsets of size N / 2, namely A and B. Then we insert each sum of every combination of elements from A into a hash table. We then check the sums of every combination of elements from B i. e. for a sum K, if S / 2 - K is in the hash, then we have a solution. Final complexity: O(2 ^ (N / 2 + 1)). An alternative to this solution would be a well implemented algorithm which randomly moves elements from one subset to the other. This outperforms the 2 ^ (N / 2) algorithm on memory and may even have better results on time.

6. I only know a simple algorithm for solving this...We'll consider the empty space as element 0. We'll keep every state found until the present state in a queue etc. For the present state "A" swap the element 0 with each of it's neighbours and remove "A" from the queue. For each of the new 2-4 states, check if it is already in the queue or has been "done". If not, check if it is the final configuration. If it is we have the minimal solution, else add this configuration to the queue. After checking all neighbours, mark state "A" as "done". If at some point the queue turns out to be empty, then the puzzle has no solution. I'm not sure if a technique similar to the Rubik cube solving algorithms might work here because there may be unreachable states.

7. Step 1: For each x and y, 0 <= x <= y < N, reverse the elements between x and y in string S. The resulting strings are kept in a queue. Repeat step 1, only this time we will be keeping the resulting strings in a Hash.
Step 2: For each x and y, 0 <= x <= y < N, reverse the elements between x and y in string T. Do this once more. If one of the resulting substrings is in the Hash, then that's a solution. (We'll also need to implement an algorithm similar to Rabin-Karp for quick string comparison). Final complexity: O(N^5).

Will come back later, if I figure out any of the other problems.

[•mips]

4. Split vertices in 2 equal-sized sets. We need 3 states for each vertex:
A. Active in the local set of vertices
B. Active in the whole graph
C. Inactive

From all generated sets(3^(n/2)) we must check if the A and B vertices cover all egdes between all vertices in the set. If so, then we encode the configuration treating A and C the same(ex: A,C->0; B->1). Associated with the hash we should also keep the A and B sets.
We do the same thing with the second set, checking in first's hashlist for a complementary configuration:

For every vertex from the first set we expect it's value to be:
A or C (0): if all edges between this vertex and the second set's vertices are B
B (1): otherwise

If a complementary configuration is found then A and B vertices from the first and the second set form a vertex-cover. We keep the vertex-cover with the smallest cardinality

Note:
The reason why we actually need 3 states comes from the fact that while a vertex which isn't in the vertex cover(inactive) implies that all vertices in the other set that share an edge with it must be in the vertex cover, an edge that is already in the vertex cover(active) implies nothing about the vertices from the other set that share an edge with it. This is a variable we don't want when we need to search the exact configuration hash, so one solution is to split the active state into: active only locally in the set and active overall.

5. Split the array in 2 equal-sized sets. For each set, associate to each of the set elements one of the states:
A. part of the 1st edge
B. part of the 2nd edge
C. part of the 3rd edge
D. part of the 4th edge
Generating all possible configuration will take O(4^(n/2))
We keep as a hash the resulted sizes of the 4 edges. Associated to this hash we keep the sets for each state.
When we compute hashes for the second set we search for the complementary configuration in the first:
desired edge size - edge1 size(sum of all A planks in second set)
desired edge size - edge2 size(sum of all B planks in second set)
desired edge size - edge3 size(sum of all C planks in second set)
desired edge size - edge4 size(sum of all D planks in second set)
Where (desired edge size) = sum of all planks/4
If such configuration is found, then the union is the answer.

6. We generate all configurations that are reachable in 16 moves from the given position and we hash them. Associated to the hash we keep the moves used to reach this configuration. We generate all configurations that are reachable in 15 moves from the final position and search the hash for each. If found, then the moves associated to the hash followed by the reversed list of moves used to reach the "middle" configuration starting with the final configuration is the answer.

[•Cosmin]

Yup, it's a typo. Thanks Oleg.

[•Cosmin]

@Corrie, the problem mentions that using the same number more than once is ok. You can do a similar solution if you don't want to have numbers repeated but it's slightly more involved.

[•S7012MY]

6)You can use a bfs and kee all the configurations where you've already been and to check in bfs not to go to a configuration 2 times. You have at most 9! configurations.

[•devilkind]

@S7012MY: There are way more than 9 solutions.

6) You can do 2 BFS in the same time. Let's say you start with 2 queues. First one contains the starting point (the initial configuration), the second one contains the ending point (the desired configuration). Now you can just expand the nodes alternatively (expand a node from the first queue, then from the second queue and so on). Everytime you try to insert a node in it's queue, you check if that node isn't already in the other queue. If so then you found your solution.

[•Protoman]

@devilkind: You should read the exclamation mark too.

[•devilkind]

Ah oops, my bad.

[•Cosmin]

Thanks Nick. Glad you like it.

Cute problem.

[•Cosmin]

 The problem already mentions : "(the same element can be used multiple times)". I did that to avoid handling the annoying case you mention .

[•mihai.alpha]

 It is a very interesting method. Thanks for sharing it!