Problem Link: ZIO 2004 Problem 5
PREREQUISITES: Diagrammatical representation of the problem and basic logic.
Explanation:
Understanding the problem:
- Each teleport on one planet has a single one-way connection to teleport on the other planet.
- Every teleport has exactly one such outgoing connection but may have any number of incoming connections.
- Given the available connections for each teleport of both planets, we need to determine the connection mode of each teleport, that is, Sending or Receiving.
Constraints:
-
If a teleport on one planet is set to Sending Mode then there must be a teleport on another planet set to the opposite mode that is, Receiving Mode and vice versa, just like sending and receiving files by Bluetooth between two devices.
-
Determining the connection mode should be such that all the teleports of both planets remain usable.
Diagrammatic representation of the problem:
First of all, we need to represent the connections of teleports given in the subtask, in such a way that we could easily determine the connection mode of each teleport.
Step 1: List all the teleports of the planet Aleph in a column on the leftmost and also list the teleports of the Gimmel planet on rightmost in a column.
Step 2: Map the outgoing connections from each teleport of planet Aleph to the respective teleports on the planet Gimmel as given in the subtasks, like A1 → G1.
Step 3: Now map the outgoing connections from the teleports of planet Gimmel to the respective teleports on the planet Aleph as given in the subtasks, like G2 → A7.
Method to solve the problem:
After drawing a diagram for a given subtask and keeping the constraints in mind, now we could determine the connection mode of each teleport.
-
We determine the connection mode of the teleports of planet Gimmel by determining the connection mode of the teleports of planet Aleph or you can also do it in the other way around by determining the connection mode of teleports of planet Aleph, by determining the connection mode of the teleports of planet Gimmel. For instance, if a teleport of the Aleph planet is set to Sending mode, then the connection mode of the respective teleport of the opposite planet must be set to Receiving mode and vice versa, which in means the connection mode of teleports of planet Gimmel is kind of dependent of the connection mode of the teleports of planet Aleph, satisfying the first constraint.
-
We also need to carefully determine the connection mode of each teleports of planet Aleph such that no other teleports of planet Aleph, as well as the teleports of planet Gimmel, remain unusable in the end.
Subtask 1:
Given the data:
Diagrammatic representation:
- The \color{red}{red} arrows represent the outgoing connections through the teleports of planet \color{red}{Aleph} to the teleports of planet Gimmel.
- The \color{green}{green} arrows represent the outgoing connections through the teleports of planet \color{green}{Gimmel} to the teleports of planet Aleph.
Solving the problem:
-
We could see that A1 has an outgoing connection to G1, and G1 has an outgoing connection to A5 but in order to make A1 remain usable, it must be set to Sending mode and now since A1 is set to Sending mode, G1 must be set to Receiving mode.
-
Now moving down to A2, we see, it has an outgoing connection to G2, G2 has an outgoing connection to A7 but in order to make A2 remain usable, it must be set to Sending mode and now since A2 is set to Sending mode, G2 must be set to Receiving mode.
-
Moving down to A3, it also has a similar case as in A1 and A2, it has an outgoing to G3 but the only way to make A3 remain usable, it must be set to Sending mode and now since A3 is set to Sending mode, G3 must be set to Receiving mode.
-
Now A4 has an outgoing connection as well as an incoming connection to and from G3 respectively but G3 is already set to Receiving mode, so now A4 can no longer have an incoming connection from G3 but in order to make A4 remain usable, it must be set to Sending mode.
-
Moving down to A5, it also has a similar case as in A4, it has an outgoing connection as well as an incoming connection to and from G1 respectively but G1 is already set to Receiving mode, so now A5 can no longer have an incoming connection from G1 but in order to make A5 remain usable, it must be set to Sending mode.
-
Now coming down to A6, we see it has an outgoing connection to G2 and an incoming connection from G4, now, in this case, A6 can have either possibility, Sending or Receiving, both are valid.
If A6 is set to Receiving mode then the constraints will be satisfied and G4 will be set to Sending mode, but, since G4 is set to Sending mode, but by doing so A7 can’t have the outgoing connection to G4, as well as it can’t have the incoming connection from G2 because G2 is already set to Receiving mode. In this case, A7 becomes useless.
In order to avoid this conflict, we need to set A6 to Sending mode, by doing so A7 can now be set in Sending mode because G4 can now be set at Receiving mode.
At last, we would have the connections:
| A1 = S | G1 = R |
|---|---|
| A2 = S | G2 = R |
| A3 = S | G3 = R |
| A4 = S | G4 = R |
| A5 = S | |
| A6 = S | |
| A7 = S |
Subtask 2:
Given the data:
Diagrammatic representation:
- The \color{red}{red} arrows represent the outgoing connections through the teleports of planet \color{red}{Aleph} to the teleports of planet Gimmel.
- The \color{green}{green} arrows represent the outgoing connections through the teleports of planet \color{green}{Gimmel} to the teleports of planet Aleph.
Solving the problem:
-
We could see that A1 has the one and only outgoing connection to G5 and G5 also has the one and only outgoing connection to A1. So, in this case, A1 can either be set to Sending mode or Receiving mode and G5 would also be in either Receiving mode or Sending mode accordingly, that is if A1 is set to Sending mode then G5 would be set to Receiving mode and vice versa. So let’s say we set A1 to Sending mode and G5 to Receiving mode.
-
Moving down to A2, we see that A2 has an outgoing connection to G2 as well as it has three incoming connections from G2, G7, and G8. So here A2 can either be set to Sending mode or Receiving mode but we need to be careful as we have to make sure that no teleport of either planet remains useless. So now if we set A2 to Sending mode then G2 would be set to Receiving mode but by doing so the teleports G7 and G8 would remain useless because unlike G2 they only have an outgoing connection to A2, in other words, they are a kind of dependent on A2 in order to be useful, so we must set A2 to Receiving mode and teleports G2, G7, and G8 to Sending mode so that all the teleports remain useful.
-
Moving down to A3, we see A3 has an incoming connection from G1 as well as an outgoing connection to G4. Unlike the case of A2, the teleport G1 and G4 do not depend on the connection mode of A2 (in order to be useful), because G1 has an incoming connection from A4 other than the outgoing connection to A3 they can be set in either way. Let’s say we set A3 to Receiving mode and G1 to Sending mode.
-
Moving down to A4, we see it has an outgoing connection to G1 as well as an incoming connection from G4 but G1 is already set to Sending mode in the previous step so now A4 can no longer have an outgoing connection to G1, so A4 is left with the only option to be set to Receiving mode and then G4 will be set to Sending mode.
-
Now moving down to the last one we see that A5 has an incoming connection from G3 and G6 as well as it has an outgoing connection to G8 but G8 is already set to Sending mode in the 2nd step so now A5 can no longer be set to Sending mode, which means A5 now, of course, has to be set to Receiving mode else G3 and G6 won’t be kept usable. So then G3 and G6 will now be set to Sending mode.
At last, we would have the connections:
| A1 = S | G1 = S |
|---|---|
| A2 = R | G2 = S |
| A3 = R | G3 = S |
| A4 = R | G4 = S |
| A5 = R | G5 = R |
| G6 = S | |
| G7 = S | |
| G8 = S |
Subtask 3:
Given the data:
Diagrammatic representation:
- The \color{red}{red} arrows represent the outgoing connections through the teleports of planet \color{red}{Aleph} to the teleports of planet Gimmel.
- The \color{green}{green} arrows represent the outgoing connections through the teleports of planet \color{green}{Gimmel} to the teleports of planet Aleph.
Solving the problem:
-
We could see that A1 has an outgoing connection to G9 as well as two incoming connections from G2 and G8, but in this case, A1 must be set to Receiving mode because G2 is kind of dependent on A1 in order to remain useful as G2 has no other connection other than an outgoing connection to A1. So we set A1 to Receiving mode and G2 and G8 to Sending mode.
-
Moving down to A2, we see it has an outgoing connection to G4 as well as an incoming connection from G9 but since we already had set A1 to Receiving mode so now A2 it can no longer have an outgoing connection to G9, which means G9 has an only outgoing connection to A2, so in order to keep the teleport G9 working, we must set A2 to Receiving mode. So we set A2 to Receiving mode and G9 to Sending mode.
-
Coming down to A3, we see it has one and only outgoing connection to G5. So in order to keep the teleport A3 working, we must set A3 to Sending mode and G5 to Receiving mode.
-
Moving down to A4, we see that it has two incoming connections from G4 and G6 as well as an outgoing connection to G5 but if we look carefully then we could see that G6 has the one and only outgoing connection to A4, so we just blindly set A4 to Receiving mode and the teleports G4 and G6 to Sending mode because it is the only way by which we could make the teleport G6 to remain usable.
-
Moving down to A5, we see that it has three incoming connections from G5, G3, and G1 out of which G5 is already set to Receiving mode in step 3 so it can no longer have a connection with A5 and besides, A5 also has an outgoing connection to G8 but since we already set G8 to Sending mode in step 1 so A5 is now only left with the incoming connections from G1 and G3 only. So all together we could say that in order to remain G1 and G3 useful, the teleport A5 must be set to Receiving mode and the teleports, G1 and G3 must be set to Sending mode.
-
Now moving down to the last one, we see A6 has an outgoing connection to G7 as well as an incoming connection from G7, so it’s easy to determine the mode in this case. A6 can either be set to Sending mode or Receiving mode and accordingly G7 would also get adjusted. Let’s say we set A6 to Sending mode and G7 to Receiving mode.
At last, we would have the connections:
| A1 = R | G1 = S |
|---|---|
| A2 = R | G2 = S |
| A3 = S | G3 = S |
| A4 = R | G4 = S |
| A5 = R | G5 = R |
| A6 = S | G6 = S |
| G7 = R | |
| G8 = S | |
| G9 = S |
Thanks @sudheerays123 for helping me out through this 