Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Meet in the middle  (Citit de 24273 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« : August 10, 2012, 21:40:18 »

http://infoarena.ro/blog/meet-in-the-middle
Memorat
Steve
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #1 : August 11, 2012, 06:57:22 »

Nice article! Smile

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.
« Ultima modificare: August 11, 2012, 07:33:01 de către Stefan Eniceicu » Memorat
mips
Strain
*

Karma: 1
Deconectat Deconectat

Mesaje: 30



Vezi Profilul
« Răspunde #2 : August 11, 2012, 08:53:02 »

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.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #3 : August 13, 2012, 19:46:45 »

Yup, it's a typo. Thanks Oleg.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #4 : August 15, 2012, 02:30:45 »

@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.
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #5 : August 15, 2012, 19:44:19 »

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.
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #6 : August 17, 2012, 09:24:37 »

@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.
« Ultima modificare: Septembrie 18, 2012, 21:32:50 de către Serban Andrei Stan » Memorat
Protoman
Infoarena Monthly
De-al casei
*****

Karma: 119
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #7 : August 18, 2012, 00:52:38 »

@devilkind: You should read the exclamation mark too.
« Ultima modificare: Septembrie 18, 2012, 21:33:04 de către Serban Andrei Stan » Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #8 : August 19, 2012, 15:29:23 »

Ah oops, my bad.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #9 : Septembrie 18, 2012, 08:54:25 »

Thanks Nick. Glad you like it.

Cute problem.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #10 : Martie 29, 2013, 04:23:56 »

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


Karma: 0
Deconectat Deconectat

Mesaje: 16



Vezi Profilul
« Răspunde #11 : Aprilie 14, 2017, 17:47:49 »

 It is a very interesting method. Thanks for sharing it!
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines