Erisu._.3812's blog

By Erisu._.3812, history, 19 months ago, In English

Hello those who are reading my entry, I have a small problem that i'm kinder curious about my solution.

***The problem is:

You have an array of integers (a[i]<=1e6) sized of n (n<=1e3). You have to split the array m different segment which cover the whole array. An action will take 1 unit of time which let you do 1 of those 2 at a time (each take 1 unit of time):

  • You can minus 1 from a[i]

  • You can plus 1 from a[i]

Your task is to mange to split the segments somehow that all of the value in 1 segment need to be the same by using those action i mention. And also those segment action work separately, which mean the answer would be the maximum action of 1 of those m segments.

Test Case:

Input:

6 2

1 1 2 3 4 3

Output:

1

Explain: 2 segments are 1 1 2 and 3 4 3, you can turn it into 1 1 1 and 3 3 3***

My idea:

Due to the fact that actions need for a subarray is going to be larger if it contains more value (or the subarray is larger) because the action we have to use is abs(a[i]-median) so base on the linear spec, we could use greedy to put as many as we could into a segment so that their action won't exceed the answer (cause we only focus about the max value).

I would use binary search to search for the answer, for each mid I search, I would check it for each segment as I mention to make sure that none of them could exceed by using 2 pointer L and R. For each L, I will find all the median in (L, R) and check to make sure the actions follow the rule by extend the R pointer to the furthest position (rightest what I mean).

And if everything is ok, then just print the answer. However, the time limit could be O(n^2*LogN^2), which mean 20*20*1000*1000 or 400 million calculations, may exceed 1 second limit. Forgot to mention, I use Persistent Data Structures to find the (r-l+1)/2 smallest value to find the median.

time limit: 1s

memory limit: 256mb

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A nicer typesetting and a simplified description could be welcomed.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Adding bulletin in the important points and when you are going for a new line instead of pressing Enter 1 time press it 2 times to reflect a new line in the entry as well.

Hope now you can make your statement readable :)

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems that you got this in the bag! The solution is great, you simply miscalculated the time complexity. From what I understand, it should be O(n*logN^2), so a maximum of 1000*10*10 = 100000 steps.

Explanation: For each mid you pick, you do n iterations. In each iteration, the complexity is O(logN) (for adding an element to some ordered multiset(s) and getting the median value). You also might want to clear the set(s) when you reach a limit (i.e. if you incremented the r, you would do more than mid operations), so another NlogN for each update of mid. logN * N * logN + logN * N * logN = O(N*logN^2).

If you need further explanations, lmk. Bottom line, your idea was great!

  • »
    »
    19 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    One more detail: you can calculate abs(a[i]-median) for all i in current sequence in O(1) using two partial sums: sp[i] = a[1] + a[2] + ... + a[i]; sn[i] = -a[1] — a[2] — ... — a[i]. You will also need to know the median value and exactly how many numbers are >= and < than this value, respectively.