TSECJ04 - Editorial

PROBLEM LINK:

Contest link

Editorialist: Kaustubh Khavnekar

DIFFICULTY:

Medium

PREREQUISITES:

Map data structure

PROBLEM:

The individual connections between devices A and B in a Rube Goldberg machine are given. Your task is to find the overall path of the Rube Goldberg machine.

QUICK EXPLANATION:

Express connections from A to B and to B from A as two different maps. Find device which is in forward map but not reverse map and construct path starting from that device.

EXPLANATION:

Each connection consists of two parts, A and B. The problem can be solved in linear time using a map data structure. Note that the starting device will not appear as the second part in any connection, since no other device has a connection to that device. We can find this device by first making two maps, from A to B (forward map) and then from B to A (reverse map). Then we iterate through all forward mappings, and find a device which has a forward mapping but no reverse mapping. This is the starting device. Starting from this device, we can traverse all edges in order using the forward mappings.

SOLUTION:

Solution can be found here.

//