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

×

# CDZ14E - Editorial

Author: sikander_nsit
Tester: sikander_nsit
Editorialist: sikander_nsit

MEDIUM

# PROBLEM:

In the problem we had to find the sum of the smallest k elements in the given array range.

# EXPLANATION:

Brute force solution would not work because of the constraints. Segment tree can be used for this.

Each node of the segment tree will consist of two arrays : first is the list of elements in the range in sorted order and the second stores the cumulative sum.

For every query we can find a list of S sorted arrays such that their union is the given range in query [L,R].

 1. Go through all the arrays and if any have length > k, truncate to length k .
2. Identify the largest remaining array A. If more than one, pick one.
3. Pick the middle element M of the largest array A.
4. Use a binary search on the remaining arrays to find the same element (or the smallest element > M).
5. Based on the indexes of the various elements, calculate the total number of elements <= M. This should give you B, the count of numbers <= M.
6. If k < B, truncate all the arrays at the split points you've found and iterate on the smaller arrays (use the bottom halves).
7. If k > B, truncate all the arrays at the split points you've found and iterate on the smaller arrays (use the top halves, and search for element (k-B)). Add the cumulative sums till the split points to the answer.


When you get to the point where you only have one element per array (or 0), make a new array of size n with those data, sort, and calculate the sum of first k elements. Because you're always guaranteed to remove at least half of one array, in S iterations, you'll get rid of half the elements. That means there are S log k iterations. Each iteration is of order S log k (due to the binary searches), so the whole thing is S^2 (log k)^2 in worst case. But the actual performance would be much better than the worst case.

# AUTHOR'S SOLUTION:

Author's solution can be found here.

This question is marked "community wiki".

asked 11 Feb '14, 04:37 1.5k82130
accept rate: 0% 19.8k350498541

 0 One more way of doing this is using a persistent segment tree. answered 11 Feb '14, 11:34 81●1●4 accept rate: 9%
 0 " so the whole thing is S^2 (log k)^2 in worst case. But the actual performance would be much better than the worst case." can anyone explain this why this statements holds? because i followed it and my solution gets accepted in 0.19sec but i am expecting TLE instead... answered 27 Jun '17, 18:21 3★sidd845 25●4 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,852
×2,657
×1,768
×138
×10
×2

question asked: 11 Feb '14, 04:37

question was seen: 1,612 times

last updated: 27 Jun '17, 18:21