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

×

NOV17 Video Tutorial - CSUBQ

14
4

Its beautiful how a simple data structure, especially Segment Tree, can be used to solve such a variety of problems.
Can you count the number of subarrays that lie in range [l,r] having maximal element in range [L,R]?

The problem was solved using 2 segment trees built on binary arrays i.e all elements are 0 or 1 and were used to query the number of subarrays in range [l,r] consisting of only 1s.

Check out the video to learn:
CSUBQ Tutorial - NOV17 Long Challenge

Here is yet another application of Segment Trees in solving another medium-hard problem from Codechef NOV17 Long Challenge.

Keep sharing, keep loving.

asked 13 Nov '17, 21:55

rachitiitr's gravatar image

6★rachitiitr
1.7k520
accept rate: 0%

edited 13 Nov '17, 21:56

Your video editorial are just amazing i tried this problem for 3 days but didnt able to get the trick for 100. But finally after this video get it completely. Thanks for this video editorial.☺️

(13 Nov '17, 22:35) droy05284★

@droy0528 Thanks :)

(14 Nov '17, 12:16) rachitiitr6★

One other possible approach using segment tree could to maintain 5 values in every node. Invalid (greater than R) value from right, Invalid (less than L) from right, Invalid (greater than R) value from left, Invalid (less than L) from left and answer for node. Merging can be done by taking union of all valid subarrays while merging. Link

link

answered 14 Nov '17, 06:16

givingmybest's gravatar image

3★givingmybest
1014
accept rate: 28%

edited 14 Nov '17, 06:22

good work (y)

link

answered 14 Nov '17, 17:43

vidyut_1's gravatar image

5★vidyut_1
1444
accept rate: 20%

@vidyut_1 thanks

(16 Nov '17, 21:26) rachitiitr6★

good work (y).

link

answered 14 Nov '17, 17:43

vidyut_1's gravatar image

5★vidyut_1
1444
accept rate: 20%

I solved it using just one segment tree.here

link

answered 15 Nov '17, 01:18

robinhoodakash's gravatar image

3★robinhoodakash
212
accept rate: 0%

A very nice and clear explanation sir. Just awesome

link

answered 20 Nov '17, 02:36

saurabh0612's gravatar image

2★saurabh0612
102
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:

×1,582
×627
×300
×68

question asked: 13 Nov '17, 21:55

question was seen: 1,953 times

last updated: 20 Nov '17, 02:36