سلام

پاسخ رسمی کمیته ی المپیاد کامپیوتر:

جواب ماشین گاوی را در نظر بگیرید. چون در ماشین او در یک لحظه می تواند در یک خانه بیش از یک مهره باشد، پس می توان فرض کرد که اگر مهره ای با مختصات $(x_1,y_1)$ را بخواهیم به نقطه ای با مختصات $(x_2,y_2)$ انتقال دهیم، می توانیم ابتدا این مهره را به نقطه ی $(x_1,y_2)$ برده و سپس آن را به خانه ی $(x_2,y_2)$ ببریم. به حرکات موجود در انتقال اول، حرکت عمودی و به حرکات موجود در انتقال دوم حرکت افقی می گوییم. به عبارتی ابتدا مهره را با تعدادی حرکت عمودی به سطر مورد نظر انتقال می دهیم و سپس با تعدادی حرکت افقی به ستون مورد نظر می بریم. همچنین به هر مهره زوج مرتب $(c,d)$ را نسبت دهید که در آن $c$ به معنای تعداد حرکت های عمودی لازم برای این نقطه و $d$ برابر با تعداد حرکت های افقی لازم به ازای این نقطه است.

لم 1

به ازای یک بعد سوال درست است. فرض کنید دو مهره در مسیر حرکت خود با هم برخورد داشته باشند (مثلا مهره های $a$ و $b$ که $a$ می خواهد به خانه ی $A$ برود و $b$ به خانه ی $B$). مقصد این دو مهره را با هم عوض کنید ($a$ به $B$ و $b$ به $A$ برود). با این کار حداقل یک واحد از تعداد برخورد ها کاسته می شود. در ضمن می دانیم با این کار جواب ما از حالت قبلی اش بیش تر نمی شود. این کار را آن قدر تکرار کنید که دیگر برخوردی نداشته باشیم. پس جواب ماشین ببعی و گاوی به ازای یک بعد برابر است.

حل نصف نمره

به ازای مهره ی $i$ام ($1 \le i \le n$)$\;$$e_i$ را برابر $max(c_i,d_i)$ تعریف کنید. حال فرض کنید $F=max_{i=1}^n \; (e_i)$. واضح است که $t_1 \ge F$ است. حال جواب ماشین گاوی را در نظر بگیرید. طبق لم 1، ماشین گاوی می تواند به ما جوابی بدهد که هیچ برخوردی بین دو مهره که در حال انجام حرکات عمودی خود هستند رخ ندهد. حال هر مهره ای، حرکت عمودی خود را انجام و صبر کند تا تمامی مهره ها حرکت های عمودی خود را انجام دهند. سپس هر مهره ای حرکت افقی خود را انجام دهد. اکنون هر کس به خانه ی مورد نظر خود رسیده است. حال خواهیم داشت

$$t_2 \le max(c_i)+max(d_i) \le F+F \le t2_1$$

حل کامل

از بین جواب های موجود برای ماشین گاوی جوابی را در نظر بگیرد که $\sum _{i=1}^n\ c_i^2$ در آن کمینه شود. می خواهیم ثابت کنیم که اگر همچین جوابی را در نظر بگیریم، در هیچ لحظه ای دو مهره در یک خانه نخواهند بود. فرض کنید دو مهره در یک ستون باشند و هنگامی که حرکت عمودی انحام می دهند به یک نقطه برسند. فرض کنید مهره ی $a$ بخواهد به نقطه ی $A$ انتقال باید و مهره ی $b$ نیز به خانه ی $B$ انتقال یابد. حال مهره ی $a$ را به نقطه ی $B$ انتقال دهید و مهره ی $b$ را به خانه ی $A$. $c_a$ و $c_b$ هر دو کم تر شده است چون هیچ دو نقطه ی آبی در یک سطر نیستند. پس مجموع مورد نظر ما کم تر شده است. حال فرض کنید دو مهره از دو ستون مختلف به هم برخورد کنند. در این صورت یکی از آن ها در حال انجام حرکت عمودی خود بوده است و دیگری در حال انجام حرکت افقی خودف زیرا اولا هیچ دو نقطه ی آبی ای در سطر یکسانی نیستند، ثانیا این دو مهره در یک ستون نبودند و قرار بود هر مهره ای که می خواهد به مقصد خود برود، اول حرکات عمودی اش را انجام دهد، سپس حرکات افقی اش را. اکنون مقصد این دو مهره را با هم عوض کنید. از آن جایی که این دو مهره در یک زمان در یک نقطه بوده اند و همچنین یکی از آن ها در حال حرکت افقی بوده و دیگری در حال حرکت عمودی، پس جواب ما بیشتر نشده است. همچنین اثبات می کنیم که مجموع مورد نظر ما منتر شده است اگر جهت حرکت های این دو مهرا با هم متفاوت باشد که از $c$ هر دوی آن ها کاسته شده است پس مجموع نیز کم تر شده است (دقت کنید نقطه های نهایی در یک سطر نیستند.). حال اگر جهت حرکت این دو مهره یکسان باشد، بدون این که از کلیت سوال کاسته شود فرض کنید که جهت حرکت هر دوی آن ها به بالا بوده باشد. حال این مهره ها را با 1 و 2 نشان دهید. همچنین فرض کنید:

$$c_1 \lt c_2 \Rightarrow y_1 \gt y_2$$

$$p=c_2+y_2-(c_1+y_1)$$

حال قرار است مهره 1، $c_1+p$ حرکت عمودی انجام دهد و مهره 2، $c_2-p$ حرکت عمودی انجام دهد.

مجموع ما به اندازه ی $2p(c_1+p-c_2)$ است و مجموع ما کمتر شده است. پس اگر مجموع ما کمینه شود، ماشین به ما جوابی را می دهد که در هیچ لحظه ای دو مهره در یک نقطه نباشد که این همان خواسته ی ماشین ببعی است.