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

×

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)

This question is marked "community wiki".

asked 07 Feb, 02:06

subash1's gravatar image

4★subash1
11
accept rate: 0%

edited 07 Feb, 20:09

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 07 Feb, 20:50

kartik8800's gravatar image

5★kartik8800
32
accept rate: 0%

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,678
×1,755
×160

question asked: 07 Feb, 02:06

question was seen: 180 times

last updated: 07 Feb, 20:50