LIKECS02 - Editorial

Problem Link

Practice

Contest

Author: Bhuvnesh Jain

Tester: Hasan Jaddouh

Editorialist: Bhuvnesh Jain

Difficulty

EASY

Prerequisites

Maths, Looping Techniques, Constructive Algorithms

Problem

Construct an array of size N, such that the mean of median of all subarrays lies between [N-1, N+1].

Quick Explanation

Try to think about the sum of all integers from l to r.

Explanation

As multiple solutions exist, we should try to think how to approach the problem. Since we need to find median of the every subarray, what if the subarray was already sorted. This would easily reduce our task at hand. We can simply find the middle elements. Since, we want all subarrays to be sorted, which means the full array should be sorted as well.

Now, we want that the mean of every subarray should lie between [x, y] where x and y are any integers. So, what we can do is simply, chose any random number, not far away from x or y and then try to add a number such that mean (average) of these 2 numbers lies within our range. If we have only one number of chose, then we can simply chose the integer which lies in the middle of x and y.

With these 2 above observations, we now try to construct some solution and prove that it is correct. Now, since we want increasing numbers and all of them should be distinct as well and mostly equidistant from (N-1) and (N+1) (x and y in the problem), we try to take numbers as simply A[i] = 2*i, the list of even numbers.

You can easily prove using formula of sum of consecutive numbers that the median of the above array construct will always be (N+1). The intuition of chosing only even numbers is basically the formula easy as the sum of numbers in range require the factor of 2 in the denominator. Also, in the case the median of every subarray will be integer only, even if the size of subarray is even. Thus, this type of solution, basically easies out appraoch to the solution. To verify, you can simply write a brute force code and test it locally or prove using mathematical formulas.

One other solution is simply the list of odd numbers, i.e. A[i] = 2*i - 1. In this case, the median of the array will always be (N-1).

Since, we wanted any solution, odd or even to pass and not restrict thinking of user to any particular direction, we made the range [N-1, N+1] in the problem, even though solution with exact boundary ranges exist as shown above.

Since many solutions exist in the problem, feel free to discuss your approach in the comments below.

Bonus problem

Try to write a test judge for the problem.

Time Complexity

O(N)

Space Complexity

O(1)

Solution Links

Setterā€™s solution

Testerā€™s solution

2 Likes

Wow, a good amount of thought was put in. Since I did something different-

What I did was to make N middle/one-of-middle element in the array. Every element was at difference of 1, so I used that to immediately find the array. After some work, I was able to derive that all my array should have elements from [\frac{N+1}{2},\frac{3*N-1}{2}] . This guarantees that N is middle element of my array.

My solution-

https://www.codechef.com/viewsolution/15446119

@vijju123 I did almost the exact same thing as you. But I purely did it by observing the pattern. I cannot explain it mathematically. Were you able to derive the correctness?

My solution:

https://www.codechef.com/viewsolution/15448968

1 Like

Yes, thats why it took me time to submit. :stuck_out_tongue: .

Take a case of N=5,6,7,8. You will see a pattern. Although your intuition will say ā€œAnswer is obviousā€ , but you can then replace the numbers with N and with your built intuition, derive the answer. Want me to upload the formal proof?

Bonus Problem:

Considering the constraints (and the hint, median = mean for symmetric distribution), no one can actually make an array where the mean of median of all the sub-arrays satisfies the answer, but is not symmetric in nature.

So for test judge, just take the mean of the array given, if it lies in the [N-1, N+1], then it is correct.

(Still thinking whether an array exist which is not symmetric distributed but still satisfies the answer)

Oh I get it now.

If N is the at the center of our array, and the entire array is in increasing order with equal increments, it becomes the mean of medians of all sub-arrays of a particular length.
eg. for subarrays of length 1, since N is the center element, it becomes the mean. Same for all other lengths of sub-arrays.
This can then be extended to say that N becomes the mean of medians for all lengths of sub-arrays.

Correct me if Iā€™m wrong.
But I now see that I completely ignored the [N-1, N+1] range. Coded it for exactly N :slight_smile:

Yes, almost same. Say for N=5, I made array from [3,7]. 5 subarrays of length 1. Their mean=5. 1 subarray of length 5, mean=5.

4 subarrays of length 2. Sum of medians is 20. Mean =20/4=5 again. 2 subarray of length 4. Again, mean 4. (see, in statement X subarray of length Y, I am able to get same result if i interchange X and Y !!).

For even, this will shift to N+0.5 . Eg, for N=6, my array yields mean of medians as 5.5

Hard to generate by a computer programā€¦ :smiley:

but consider

n = 5

1 4 5 7 8

Even for this the mean of array works :slight_smile:

The array 1 4 5 7 8, might be incorrect as an answer.
If mean of median i.e. [N-1, N+1] must be an integer (nowhere mentioned though) then array must be symmetric.

I am not able to understand the explanation above. Could you please explain in a simpler manner.

What if the constraint on n was n<10^9. This would mean we would have to select increments of 1 in the array only, right?
In that case how would the solution change?

Damn, thatā€™s sweet. Got it now. Thanks for the help.

My mistake :slight_smile:

I did it by Binary Search. First n-1 elements are 1,2,3,ā€¦,n-1. Find last element by binary search.

Link

1 Like

one more way https://www.codechef.com/viewsolution/15453822 just simply satisfying given condition

Canā€™t understand this part of the editorial.

Now, we want that the mean of every subarray should lie between [x,y] where x and y are any integers. So, what we can do is simply, chose any random number, not far away from x or y and then try to add a number such that mean (average) of these 2 numbers lies within our range. If we have only one number of chose, then we can simply chose the integer which lies in the middle of x and y.

by simple maths we can show that the sum of medians of all the subarrays is : (a + 3b + 5c + 3d + e) + (a+b+c+d+e)/2 (for n = 5 and i am assuming that the array is sorted i.e. a < b < c < d < e) so, i simply find the sum of all the subarrays taking first n-1 elements (1, 2, 3 ā€¦n-1) and then just finding the last element by subtracting this by (n^3 + n)/2 (the mean sum as number of subarrays are n*(n+1)/2) .

implementation : https://www.codechef.com/viewsolution/15471696

nowhere in the question it is mentioned that the mean of medians should ā€œstricyly be a INTEGERā€ā€¦
And if we assume that the mean of medians belongs to [N-1, N+1](and not strictly an integer), then the arrays (n-(n-1)/2).....n....(n+(n-1)/2) for n odd and for n even, (n-(n/2)).......n.......n+(n/2)-1 would also be a solution.

@vijju123 "One other solution is simply the list of odd numbers, i.e. A[i]=2āˆ—iāˆ’1. In this case, the median of the array will always be (Nāˆ’1) ".
Can u explain this line . For me this is coming as N only .
Suppose N=3
Odd no will be 1 3 5 . Now in this case N=3 and median is also 3 .Plz explain .