usureluflorianr's blog

By usureluflorianr, history, 5 weeks ago, In English,

Hi! Is anybody who can give me a solution for this? We have an array with n elements and a number k. We are asked to calculate in how many continuous strings of size exactly k (k is even), the element at the i-th position is in the second half if we sort that continuous string (all values are different). We want to calculate this value for every single position*. Example: n=6, k=4, the array: 1 4 2 5 9 3, the output will be like this: 0 1 0 3 2 0

 
 
 
 
  • Vote: I like it  
  • +13
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Why wouldn't on your example ans[1] be 1? If you take the subarray 1 4 2 5, then the element that used to be at 1st position would be in the first half. BTW, you may want to add that you want to compute that for any i, I couldn't infer that until I saw the example

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Second half*, the post has been edited. The problem was given at AGM and I want to see different approaches.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by usureluflorianr (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Alright so I have a solution, but I'm pretty tired and wouldn't be at all shocked to see that I overcomplicated it. Let's index the n — k + 1 possible subarrays by their left index (i refers to [i, i + k — 1]).

Let's incrementally activate values in the array in increasing order. When considering an element, we first compute its answer = the number of subarrays that contain it that currently have at least k / 2 activated elements. If we manage to keep track of the subarrays with at least k / 2 activated elements, then we can use a segment tree to update the indices of such subarrays with a +1 and query [pos — k + 1, pos]. It's clear that every subarray will start having at least k / 2 elements from some point till the end, because elements are just getting activated and never being deactivated. Assume you've already determined what's for every subarray the exact point it reaches the k / 2 activated elements. Then all you need to do is to merge these "update subarray" events with the query events.

Now, how to determine when a subarray first reaches the milestone? Well that's given by (k / 2)th smallest element from that range. We can compute that for all subarrays by sweeping from the first one till the last one and keeping a set with the values in the current range, together with the current median. It's easy to initialize it for the first subarray as you can do it in O(KlogK). Then, how to sweep from a subarray to the next one? You just erase an element and insert another one. Comparing the inserted/erased value with the old median tells you whether you should increase or decrease the iterator that pointed to the median, and so you can keep it updated.

It's not terribly difficult to code. The sweeping is just a set and the actual computing of the answer is either a Fenwick tree or a segment tree, both of which are pretty basic. The overall complexity is N(logK+logN) = NlogN (since K can get as large as N I suppose)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you for staying awake and creating this nice solution! This really helped me. :D