You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

This question is marked "community wiki".

asked 13 Mar '17, 20:32

wittyceaser's gravatar image

2★wittyceaser
3.4k194377
accept rate: 16%

edited 10 Aug '18, 15:55

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,679
×82

question asked: 13 Mar '17, 20:32

question was seen: 216 times

last updated: 10 Aug '18, 15:55