ANKTRAIN - Editorial

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.