# Proof of Correctness : Arranging the sheep

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.

• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. – D.W. May 11 at 3:25
• I've provided the links for that reason.. One can use those links to search any extra information.. I've deleted the question and reposted it because it was showing that the question is closed and it won't be accepting any answers. – Tejesh Avadanam May 11 at 3:29
• Providing a link to the problem plus an image is not a substitute for transcribing it to a textual format. I've already explained the reasons; it makes it impossible to find this question by searching for terms used in the questions, and it isn't accessible to folks with visual impairments. It's not just about people who find this page being able to find the problem; it's also about others with a similar question about the problem being able to find this page. – D.W. May 11 at 4:21
• Also, links break. – Raphael May 17 at 21:35
• Contest links are preserved for eternity....So I guess there's no chance of breaking – Tejesh Avadanam May 20 at 4:24

The reason is instead of aligning the sheep at the edge, you want to align them at that sheep.

Example:

*.*.*

Here, instead of solution ..*** (3 moves) or ***.. (3 moves), the ideal solution is .***. (2 moves).

Proof:

Clearly, some sheep makes 0 moves in the optimal solution. Assume in the optimal solution, i < m is that sheep, and the solution takes less steps than using m.

Since the solution takes less steps than the m solution, we know m makes at least one step, and all j > m also make at least one step. If instead we use m as pivot, we save either one or zero steps, as now the lower half has to make the same steps instead, but that is at most one more than the upper half had to do (because there is at most one more sheep in the lower half). Together with the step m doesn't need to make, we get the contradiction that the m solution has to be at least as good as the i solution.

• Thanks a lot it helped me in understanding the concept – Tejesh Avadanam May 11 at 8:07
• Clearly, some sheep makes 0 moves in the optimal solution. Why, starting with *..*, wouldn't the two-move solution yielding .**. be minimal? – greybeard May 11 at 18:52
• @greybeard Maybe that sentence is not 100% correct. There always is an optimal solution where some sheep makes 0 moves is more correct and works as well for the proof. – kutschkem May 12 at 6:39