COOK136 Median Minimization

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

Anyone knows what’s wrong with this brute force? suppose to get TLE, but WA

You’re missing out the conditions for consecutive elements.
For sorted array you can get lesser value if you check the difference for two consecutive elements.
All you need to find is for which two consecutive elements it is possible to form the required subsets(It is possible to make the subsets using those two elements).

not quite sure of which conditions are missing as you mentioned.

I think I cover all conditions
for example: this input
1
10
5 7 9 6 8 4 3 2 1 10

all my conditions are here left, right cut, are you able to point out any of the missing conditions?
[5], [7, 9, 6, 8, 4, 3, 2, 1, 10]
[5, 7], [9, 6, 8, 4, 3, 2, 1, 10]
[5, 7, 9], [6, 8, 4, 3, 2, 1, 10]
[5, 7, 9, 6], [8, 4, 3, 2, 1, 10]
[5, 7, 9, 6, 8], [4, 3, 2, 1, 10]
[5, 7, 9, 6, 8, 4], [3, 2, 1, 10]
[5, 7, 9, 6, 8, 4, 3], [2, 1, 10]
[5, 7, 9, 6, 8, 4, 3, 2], [1, 10]
[5, 7, 9, 6, 8, 4, 3, 2, 1], [10]

You can make subsets by randomly selecting the elements from the original. For this case the one possible answer would be [1 2 5 7 8] [3 4 6 9 10].

Oh that’s subsequence generation, I thought is subarray generation. thanks!

1 Like