TTMMM's blog

Is my Approach wrong?
By TTMMM, history, 5 years ago, In English

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

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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.

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

    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.

    → Reply