Help in proof for the the Topcoder problem "MoveStones"

Правка en1, от bclassrank7, 2019-12-11 04:58:34

This is the Div1-250 level problem of SRM-683 :- There are n piles of stones arranged around a circle. The piles are numbered 0 through n-1, in order. In other words: For each valid i, piles i and i+1 are adjacent. Piles 0 and n-1 are also adjacent. You are given two vector s a and b, each with n elements. For each i, a[i] is the current number of stones in pile i, and b[i] is the desired number of stones for this pile. You want to move some stones to create the desired configuration. In each step you can take any single stone from any pile and move the stone to any adjacent pile. Find and return the smallest number of steps needed to create the desired configuration, or -1 if the desired distribution of stones cannot be reached.

In the editorial of the problem it is mentioned — "The solution to this cyclic version comes upon realizing that the stones don't need to move between more than n stacks, the moves in such a situation would be redundant. So there will be two adjacent stacks that don't need to share stones at all. Those two stacks can be used as the start and the end stacks of a solution like the division 2 version. "

My doubt is that how do we proof that in case of minimum moves, there will exist two adjacent piles such that no transfer of stones happens across their partition.

Thanks in advance :)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский bclassrank7 2019-12-11 04:58:34 1404 Initial revision (published)