ANKTRAIN - Editorial

dec16
editorial

#1

PROBLEM LINK:

Practice

Contest

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 hard-coded in the program, as there are only 8 berths.

neighbours = { 0 -> "4LB", 1 -> "5MB", 2 -> "6UB", 3 -> "1LB", 4 -> "2MB", 5 -> "3UB", 6 -> "8SU", 7 -> "7SL" }

For a given value of N, we just need to fetch the value from the neighbours table for (N - 1) since our table has 0-indexed 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 0-indexing 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.