ANKTRAIN - Editorial

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.

#include<bits/stdc++.h>
using namespace std;

string partner(int n){
    int x = n % 8;
    string arr[9] = {"", "LB", "MB", "UB", "LB", "MB", "UB", "SU", "SL"};
    if(x == 7) return to_string(n+1) + arr[7];
    else if(x == 0) return to_string(n-1) + arr[8];
    else{
        if(x>3) return to_string(n-3) + arr[x];
        else return to_string(n+3) + arr[x];
    }
}

int main(){
    int n,t;
    cin>>t;
    while(t--){
        cin >> n;
        cout<< partner(n)<<endl;
    }
}