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

×

Google Code Jam 2017 Practice Round

Plz tell me the logic to solve this problem Problem link

asked 27 Jun '16, 11:15

arunmittal53's gravatar image

4★arunmittal53
92
accept rate: 0%

edited 27 Jun '16, 11:16


I found this answer on Quora by Raziman T.V.,

This problem can be solved in $O(N \log N)$ per query using binary search.

The problem basically reduces to this:

Given an array of positive integers, what is the sum of the lowest K subarray sums?

Clearly, even generating all the subarray sums is going to take $O(N^2)$, which we would like to avoid. We will overcome this limitation by not generating the subarrays at all but only dealing with their counts and sums. Turns out that this is actually possible to do!

Let the original array be ar[1…N]. We will start by defining the following arrays

  • psum[1…N] : psum[i] = ar[1] + ar[2] + … ar[i] = sum(ar[1…i])

  • qsum[1…N] : qsum[i] = Nar[1] + (N-1)ar[2] + … (N-i+1)*ar[i]

Using these arrays, subarray sums and sums of subarray sums can be computed quickly. Sum(ar[l…r]) is given by psum[r]-psum[l-1]. Similarly, sum(ar[l…l]) + sum(ar[l…(l+1)]) + … sum(ar[l…r]) = qsum[r]-qsum[l-1]-(N-r)(psum[r]-psum[l-1]).

With this, let us tackle the problem. We will solve the problem in two steps: First, we will find the value S of the Kth largest subarray sum. Then we will sum up all the subarrays with sum less than or equal to S. For the first part, we use binary search. All subarray sums will be between 0 and psum[N]. For each x in the range, we want to ask the question : How many subarrays have sum less than or equal to x? We can check this by considering all starting points for the subarrays. From the starting point, we keep moving right till the sum overshoots x. Done naively, this would take $O(N)$ time per starting point which is too much. We can reduce the complexity to $O(\log N)$ per starting point by finding the limit by binary searching on the psum[] array. It is possible to reduce the complexity even further to amortised $O(1)$ by a sliding window/two pointers algorithm. On increasing the value of x, the number of subarrays with sum less than or equal to x increases as well. Thus we can binary search for the value of x which gives exactly K sums (In fact you want to find the x which gives just under K sums and extrapolate the rest).

Once the value of x is found, we find the required subarray sum in the same fashion. For each starting point, the subarray limit can be found as earlier, using binary search or sliding window. The sum of subarray sums for the starting point can be calculated using the qsum[] array defined above.

link

answered 27 Jun '16, 18:29

geek_geek's gravatar image

4★geek_geek
43914
accept rate: 16%

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:

×678

question asked: 27 Jun '16, 11:15

question was seen: 1,456 times

last updated: 27 Jun '16, 18:29