IIITBH - Editorial

PROBLEM LINK:

Practice

Contest

Author: Subash Chandra Manohari

Tester: D Teja Vardhan Reddy

Editorialist: Subash Chandra Manohari

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Segment tree

PROBLEM:

The problem is to find the difference between the IDs of the students having same score in a given range [L,R].

EXPLANATION:

For this interval type of queries, we can think of solving it using segment trees.

We can make a node which can store the minimum and maximum indices of a given mark. If the range represented by a node is completely within the given range, return the node which has the minimum and maximum indices of marks in the range. And if the range represented by a node is partially inside and partially outside the given range, return node of the left child and the right child.

Using this, both Update and Query operation can be done in O(Log n) time and the building of tree will take O(n) time. So the overall time complexity of the solution will be O(n Log n)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here. (Alternate solution)

Alternate solution without using segment tree.
Used sets to store id of students having a particular score.
https://www.codechef.com/viewsolution/22915966