### TTMMM's blog

By TTMMM, history, 13 months ago,

Submission ID: 66585414 Problem : 1201/C C. Maximum Median

I am first calculating that for median to be ar[i], can we go there by swapping? Once done, all elements in second half of array are equal and i am still left with k, its easy to increase median by increasing all elements by 1 each. Please tell if this approach is fine or not, Getting WA at test case 6

• +9

 » 13 months ago, # |   0 Auto comment: topic has been updated by TTMMM (previous revision, new revision, compare).
 » 13 months ago, # | ← Rev. 3 →   0 Greedy approach: First sort the given array it's obvious that element from [0,n/2[ have no influence in the final answer. for each element in the second half of the array, you have to make the median equals to a[i+1] if it's possible so you should make all element from [n/2, i] equals a[i+1] (don't forget the case when you still have k and you can make changes) For example/ 9 6 1 2 2 2 5 5 6 6 7 The first step make the array equals to : 1 2 2 2 6 6 6 6 7 then 1 2 2 2 7 7 7 7 7 My submission : 66587248 I found bs approach explained in the editorial much easier.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Thanks bro. This is exactly what I have done. Just that my solution is not getting accepted, but the logic is same. Found now where i had gone wrong.