PROBLEM LINK:Author: Ankit Srivastava Tester: Kevin Charles Atienza Editorialist: Vaibhav Tulsyan DIFFICULTY:CAKEWALK PREREQUISITES:None PROBLEM:Given a pattern of arrangement of berths in a train, find the train partner of a given berth number. The pattern repeats for every 8 berths. QUICK EXPLANATION:Maintain a map that stores neighbouring berth of the first 8 berths. For a given berth number $N$, find it's neighbour $M$ that lies in the same compartment, say $C$. In order to do this, find the berth equivalent to $N$ in the $1^{st}$ compartment and it's neighbour $M'$. Add appropriate offset to find equivalent berth of $M'$ in the compartment $C$. The berth number of the number is: $N  N \% 8 + M'$. EXPLANATION:Subtask 1: The approach used for this subtask will be extended and used for subtask 2. From the constraints of Subtask 1, we know that $1 \le N \le 8$. This means that we are dealing with only 1 compartment. Let's store the neighbours of each berth  this can be hardcoded in the program, as there are only 8 berths.
For a given value of $N$, we just need to fetch the value from the neighbours table for $(N  1)$ since our table has 0indexed keys. This can be implemented using a list/array/hashmap. Subtask 2: Note that the pattern repeats after every 8 berths  hence, group of berths [9..16] is identical to group [1..8], and [17..24] is also identical to [1..8]. Thus, all we have to do is find the equivalent neighbour ($M'$) of $N$ in the $1^{st}$ compartment and add an offset to this neighbour. Let's say $N$ was present in compartment $C$. The first berth of that compartment would have the number $N  (N \% 8)$. Hence, the berth number of the neighbour would be: $(N  (N \% 8) + M')$. Note: Since we're working with integers under a given Modulo, we are using 0indexing for our neighbours map for simplicity. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution can be found here. Tester's solution can be found here. Editorialist's solution can be found here.
This question is marked "community wiki".
asked 13 Mar '17, 20:32
