I've come across a question in Codeforces contest 719(Div - 3).
The problem goes like this :
I was able to solve the problem by using another approach but had to use 4*n auxiliary space, where n is the length of the input string however the solution given in the editorial is way more efficient
The editorial goes like this
It basically says to choose the sheep whose number is ⌈k/2⌉ as pivot.(In the editorial they gave it as n/2 which is wrong. Consider it to be k/2, where k is the number of sheep in the given string.)
Here's my doubt Why sheep at present at ⌈k/2⌉ should make 0 moves to get an optimal solution. I've searched the internet but couldn't find the proof. Can someone give me a generalized proof for this?.. Thanks in advance :)
Problem Link :- https://codeforces.com/contest/1520/problem/E
Editorial Link :- https://codeforces.com/blog/entry/90342
Note :- The editorial link has the solutions for all the problems. Scroll down to find the editorial for Arranging the Sheep problem.