Searching→Wires and Switches (IOI 1995)

You have N wires and M switches. Each wire is connected to some switch, but two wire may be connected to the same switch.


                 Points  Switches
                   .       ./ .--
                   .\      ./ .--|
        --Probe->  ._\__   ./ .--|---
       |           .  \ \__./ .--|   |
       |           .___\_/ ./ .--|   |
       |           .    \__./ .--    |
       |                             |
        -----------------------------

All switches are simultaneously connected to a probe. We can connect a probe to a wire to check if circuit is complete with current values of switches.

Two commands are available to you:

Flip(j) — Flip switch j
Probe(i) — Check if the circuit to wire i is complete

The goal is to determine, for each wire, the switch to which that wire is connected, using no more than 900 of Change and Probe commands. The number of wires and switches is in the range 1..90. Initially, all switches are off (open).

Solution

Brute force algorithm:

Probe wire 1. Close switch 1..M and stop when the probe succeeds.
Probe wire 2. Close switch 1..M and stop when the probe succeeds.
…
Probe wire N. Close switch 1..M and stop when the probe succeeds.

This requires O(M*N) flips and O(M*N) probes --- in the worst case, all wires are connected to switch M.

Better alternative

Useq binary search to find the switch for a given wire — that is,

switch on half the switches and probe the wire
if on, then turn off half the switches
else turn on half the remaining (need not turn off the first half!)

This needs M flips and log M probes. Overall one will need N*M flips, and N*log M probes.

Can we now overlap the searches?

Switch on first half. Probe all wires. This splits the wires into those that fall into the first half and those that fall into second half.

Searches in two halves do not interact: Suppose initially we switch on the first half of switches. After fully exploring all wires that lie in first half, we do not have to reset these switches when we continue our binary search into the second half because, for wires connected to the second half, the switches of the first half have no effect.

This solution can be analyzed to give a very simple algorithm.

Suppose we have 8 switches. We enumerate the binary numbers from 000 to 111 in order and arrange them in a column.

We set the switches according to the columns above and probe each wire once for each column setting. Suppose a wire is connected to switch 4. Then, the 3 experiments will yield answers "011". Thus, for each wire, the result of the experiments gives the binary encoding of the switch to which it is connected.

Analysis:

M/2 log M flips :
there are log M columns and going from one column to another requires flipping half the switches.
N log M Probes :
probe N wires for each column

Indian Computing Olympiad