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

×

CDZ14E - Editorial

PROBLEM LINKS:

Practice
Contest

Author: sikander_nsit
Tester: sikander_nsit
Editorialist: sikander_nsit

DIFFICULTY:

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

sikander_nsit's gravatar image

5★sikander_nsit
1.5k82130
accept rate: 0%

edited 18 Apr '17, 22:06

admin's gravatar image

0★admin ♦♦
19.8k350498541


One more way of doing this is using a persistent segment tree.

link

answered 11 Feb '14, 11:34

tinchy_stryder's gravatar image

6★tinchy_stryder
8114
accept rate: 9%

" 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...

link

answered 27 Jun '17, 18:21

sidd845's gravatar image

3★sidd845
254
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,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