Divide and Conquer #2 - Cave
This is the second post of a series that focuses on Divide and Conquer. If you want to check the previous one, click here.
The problem we will analyze is Cave from the International Olympiad in Informatics (IOI 2013). You may find the problem statement here and a place to submit here.
A synthesis of the problem statement is : you have N (1 <= N <= 5000) switches and doors. Each switch is linked to a door and has two possible configurations (0 or 1) : one that opens the connected door and one that does not. You can try up to 70000 configurations of switches and see the last door that is open. After those tries you must return the connected door to each switch and also its correct state.
There are 5 subtask in this problem. Subtasks 1 and 2 are the ones that give the most crucial hints in order to arrive to the full solution. However, I will use a different strategy to get the 100 points : we will focus on the first door.
The reason for that is that you do not need to know any information about the other doors in order to know about the first one. Therefore, it seems to be a good approach to focus on it.
Our first problem is to discover the correct state of the switch that opens the first door.
To solve this, we will try a configuration where all switches are set to the same configuration. Let's exemplify that with an image. Imagine that each switch is a position in our sequence of blocks, that the color blue represents the state “0” and that the color yellow represents “1”. If we try a configuration with all blocks having the blue color and it opens the first door, then the switch that opens the first door must be blue; otherwise, the first door would not be open. In the case the configuration fails to open the door, then the switch must be yellow.
Our second problem is then to discover which switch opens the first door. There are three approaches to discover the position of the switch : by doing a complete search, by bucketing switches and by using a Divide and Conquer approach.
The simplest idea is to do the complete search : we test all switches one by one. When we are trying a switch, we set it to the correct color and all the others to the complementary color.
If the configuration with only the i-th switch set opens the first door, then this is the switch we are looking for. Otherwise, we continue to try other switches. An image helps us exemplify the idea again : first we test only the first switch with the correct color blue. In that case it did not work out, so we must try the second switch with the blue color. Then we discover that this configuration opens the first door and we assign the first door to the second switch.
A refinement of the idea above is to use buckets in order to do less queries.
We group the switches into B buckets of roughly the same size. Then we apply the complete search idea , but with buckets instead : we set all the switches of the current bucket we are testing to the correct state and all the other ones to the complementary state. By doing this, we will discover the bucket that contains the desired switch. After that, we do a complete search on the switches of that bucket. The total number of queries is B + N/B. The value of B that minimizes the sum is sqrt(N), so this is a considerable gain if we consider that the idea is not that much different from the O(N) approach.
The most efficient idea will then be Divide and Conquer. The key idea of our algorithm will be that there is one and only one switch that opens the first door.
The “Divide” part of our algorithm will be as follows : we split the current set of switches we are considering into two halves. We then try a configuration with the switches of the first half set to the correct state and all other switches set to the complementary state.
The “Conquer” part is based in the result of our query. If the mentioned configuration opens the first door, then the switch we are looking for is on the first half and we discard all the switches of the other half. If it does not, then we discard all the ones from the first half and stick with the ones from the second half. Let's make an example with the set {1,2,3,4,5,6}. We split the set into L = {1,2,3} and R = {4,5,6} and try the configuration as described above and exemplified by the image above. Imagine that this configuration does not open the first door : then , we discard L and our set is now {4,5,6}.
We continue the procedure and split the set in {4,5} and {6}. If we discover that {4,5} opens the door, than we discard {6}. Then we split {4,5} into {4} and {5} and do the query again.
We continue the procedure until we arrive into a set that contains a single switch. This the base case of our D&C recursion : the final element must be the switch we are looking for.
The analysis of our idea is based on the depth of the recursion tree : because at each step we discard half of the nodes, then the maximal depth if log2(N).
So we arrived at a fast solution to discovering the correct state and switch that opens the first door. However, we still need to take care of the other N-1 doors. This will not be very different from our current idea.
The tweak is indeed very simple : we find the informations for the doors in order (1,2,3 and so on…). When we are doing our queries for the i-th door, we remove the switches that opens the other i-1 doors from the set of candidates and set them to the correct states we discovered in the previous iterations of our algorithm. Therefore, discovering the correct state and switch that opens the i-th door with the information about the i-1 previous doors is equivalent to the problem of solving for the first door.
Here is a code that implements the D&C algorithm and scores 100 points :
