PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Aryan, Takuki Kurokawa
Editorialist: Pratiyush Mishra
DIFFICULTY:
Cakewalk
PREREQUISITES:
PROBLEM:
Chef’s professor is planning to give his class a group assignment. There are 2N students in the class, with distinct roll numbers ranging from 1 to 2N. Chef’s roll number is X.
The professor decided to create N groups of 2 students each. The groups were created as follows: the first group consists of roll numbers 1 and 2N, the second group of roll numbers 2 and 2N−1, and so on, with the final group consisting of roll numbers N and N+1.
Chef wonders who his partner will be. Can you help Chef by telling him the roll number of his partner?
EXPLANATION:
Note that the roll numbers form an Arithemetic Progression with a common difference of 1. Consider the following Arithemetic Progression of roll numbers: 1, 2, 3, 4, . . X . . . 2N.
Now, the teacher pairs students from the start and end. By the properties of AP, all the pairs will have sum = 2N+1.
Let Chef’s partner have a roll number y. Thus, the pair will look like (X,y).
\implies X+y = 2N+1
\implies y = 2N+1-X
Hence, chef’s partner has a roll number y, i.e 2N+1-X.
TIME COMPLEXITY:
The above calculation can be done in constant time. Hence, the solution has a time complexity of O(1).
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution