Harvesting the Farm

Let $y_{\min},y_{\max},x_{\min},x_{\max}$ be the minimum and maximum crop rows and columns.

Initially, the machine occupies only row $S_r$. Harvesting crops in both rows $y_{\min}$ and $y_{\max}$ requires its row segment to contain , , and . Thus, at least extensions are needed.

The machine must also visit both columns $x_{\min}$ and $x_{\max}$. Visit one endpoint first and then the other; choose the shorter of the two orders. The minimum number of moves is

$$(x_{\max}-x_{\min})+\min(|S_c-x_{\min}|,|S_c-x_{\max}|).$$

Extend the machine at its initial column until it covers every crop row. Then move to the nearer endpoint column and traverse to the other endpoint. The machine covers every crop during this process. Hence, both lower bounds are achieved simultaneously, and their sum is the answer.

Subtask 1 needs only the vertical extension cost because every crop is in the starting column. Subtask 2 needs only the horizontal movement cost because every crop is in the starting row. In subtask 3, every crop is in or to the right of the starting column, so the horizontal movement cost is $x_{\max}-S_c$. Use the general formula for the full subtask.

The time complexity is $O(N)$ per case and $O(T+\sum N)$ overall. The extra space complexity is $O(1)$.

Solution written by GPT5