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.

.

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.

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

What do you mean by

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

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.

Binary Search ???

can u give me a detail solution, i havenot came up with anything about BNS.

What is the output for this test?

Is it

`3.5`

or`4.3333`

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

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

thinkI have found a solution. I'll share it once you share the link.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/

(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$$$which is the same as

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

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 thatwhich can be rewritten as

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

.

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

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