Gi4Th4ng_Di77_NLUN's blog

find the subarray with the smallest average
By Gi4Th4ng_Di77_NLUN, history, 5 weeks ago, In English

Hi guys, Im having a problem about the number, but I haven't solved. PLS Help me. The problem is: Given an array a (length 2e5) of positive integer numbers. Chose a subarray from L to R (1 < L <= R < n) Delete all the number from Al -> Ar. Find the min average of the left nums.

Sample INPUT (first number is int n, the n number after that is the array a) 5 `` 5 1 7 8 2 Sample OUTPUT 2.667

Choose L = 3 R = 4 --> sum of the rest number is 5 + 1 + 2 --> average = 2.667

2 subtask: n <= 1e3 and n <= 1e5 I solve the first one, but not the latter.

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

»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Use kadane algorithm to find the maximum sum subarray in the new array b, where b[i] = a[i] — avg(a).

Corner case is when all elements of array are the same in which case you can remove all n elements.

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

I think we can use Binary Search here. Kadane mightn't work in here.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What do you mean by average of the left nums

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sample INPUT 5 5 1 7 8 2 Sample OUTPUT 2.667 L = 4, R = 5 => OUTPUT is 13/4=3.25. Why not?

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      the array is 5 1 7 8 2 --> l = 3,r = 4 --> the average of the left numbers is (5 + 1 + 2) / 3 = 2,667. Im finding the minimum average tho.

      → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Binary Search ???

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

What is the output for this test?

4
6 1 1 6

Is it 3.5 or 4.3333?

→ Reply
»
5 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Binary search on the average ,in the predicate function use a transformed function where bi = ai-(avg.), now using prefix sum ,you can minimize the sum(as sum from L to R = prefix_sum[R] — prefix_sum[L],try to maximize the second term to get the min subarray sum possible).Try this approach .

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi,

It is usually a good idea to include a link to the source. This helps people look at the problem and submit their own code to see if their idea is right. It might also help them find something in the statement that you missed. Most importantly, it would confirm that the question you've asked isn't part of an ongoing contest somewhere!

That said, I think I have found a solution. I'll share it once you share the link.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi cyan, Im so sorry that i could not give u the link, i can give u the explaination. This is a minicontest to practice at my school, after solve it, we send the code to my teacher, then she will give us the mark by a software name Themis, so im so sorry that i couldnot give u a exactly link of the contest, but if u need other proof, i can give u the docx version of the exercise (it is written in Vietnamese) LINK of Themis software: https://dsapblog.wordpress.com/2013/12/24/themis/

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      (Note: to view the following problem you need to register for the ITMO course at codeforces edu). This problem is similar to the problem you have asked. The editorial is available in edu as well (here).

      Binary search works. I have written code below.

      I will just explain def good(x) which checks whether you can make the answer $$$\le x$$$

      let s be the prefix array of a (one indexed for convenience)
      if we remove a[l...r] the average so that average is $$$\le x$$$

      $$$\frac{a[1] + \cdots + a[l - 1] + a[r + 1] + \cdots + a[n]}{n - r + l - 1} \leq x$$$

      which is the same as

      $$$a[1] + \cdots + a[l - 1] + a[r + 1] + \cdots + a[n] \leq x \cdot (n - r + l - 1)$$$

      Now, note that the number of terms on the left hand side is $n - r + l - 1$ which is the number of $$$x$$$ is being multiplied with on the right hand side. We can subtract $$$x$$$ from the equation $$$n - r + l - 1$$$ times to get

      $$$(a[1] - x) + \cdots + (a[l - 1] - x) + (a[r + 1] - x) + \cdots + (a[n] - x) \le 0$$$

      Define b[i] = a[i] - x. We basically want to choose some prefix and suffix of b which don't overlap and have a sum <= 0. This can be done easily. Let pb be the prefix sum array of b. We want to find l, r such that

      $$$pb[n] - pb[r] + pb[l - 1] \leq 0$$$

      which can be rewritten as

      $$$pb[n] \leq pb[r] - pb[l - 1]$$$

      Here the left hand side is a constant. We want to make the right handside as big as possible which is easily done using Kadane's algorithm!

      (keep in mind the restriction that 1 < l <= r < n)

      Here is the code

      a = [0] + list(map(int, input().split()))
n = len(a) - 1

def good(x):
    b = [0] * (n + 1)
    for i in range(1, n + 1):
        b[i] = a[i] - x
    dp = [0] * len(b)
    for i in range(2, n):
        if dp[i - 1] >= 0 and i > 2:
            dp[i] = b[i] + dp[i - 1]
        else:
            dp[i] = b[i]

    return sum(b) <= max(dp[2:n])

lo = min(a) - 1
hi = max(a)
// the answer lies in (lo, hi], we will binary search the range  
// when binary searching the double values it's generally a bad idea to use a while loop like  
// while(lo + delta < hi) do something  
// instead just a run a for loop 100 or so times depending on range of search  

for _ in range(100):
    mid = (lo + hi) / 2
    if good(mid):
        hi = mid
    else:
        lo = mid

print(hi)
      → Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

.

→ Reply
»
5 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

bsearch the result u -> let bi = ai-u

calculate prefixes and suffixes of fhe array b (call them pi and si respectively) then when checking pi -> take the max of suffixes from s[i+2] to sn -> best result when picking from 1..i is p[i] + suffixSuffixMax[i+2]

if its >= 0 then theres an array that you can delete that you can satisfy the condition, otherwise check the next i

flip ai = -ai and finding u in some negative range instead then flipping the result will give the min average

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply