Проблема тестирования чипов CLSR

Question

    Finding ONE good VLSI chip in a population of good and bad ones, by using the
 pair test.      
        Chip A      Chip B      Conclusion  
        -------     -------     ----------  
        B is good   A is good  both are good or both are bad  
        B is good   A is bad    at least one is bad  
        B is bad    A is good   at least one is bad  
        B is bad    A is bad    at least one is bad  


    Assumption : number of goods > number of bads
    We can solve this in O(n) time complexity by splitting the population in half 
    every time and collecting one element of the GOOD, GOOD pair. 
     T(n) = T(n/2) + n/2
    But to collect the pairs we need n/2 memory separately. 
    Can we do this in-place without using extra memory ?? 

Answer 1

Алгоритм основан на вопросе "мы можем удалить этот чип?" Таким образом, для удаления каждого чипа мы просто удаляем его из нашего связанного списка на месте (точнее, вообще не на месте).