راهنمایی پرسش‌های BWC Beta Round #1

نویسنده: ATofighi
ارسال‌شده در:
دیدگاه‌ها: 2

خب، اینهم راهنمایی برای پرسش‌های مسابقه‌ی BWC Beta Round #1 :)

A - خرس‌بقال و سیب‌ها

اگر $n \leq 3$ باشه که جواب نداره (همه‌ی حالت‌ها رو بنویسید و متوجه بشید.)

برای بقیه‌ی $n$ ها، میشه ارائه ساختار داد مثلا من یک نمونه از ساختار رو میگم،

اگر $n$ زوج بود، $n/2$ رو ابتدای جایگشت و $n/2 + 1$ رو انتهای جایگشت می‌زاریم، بقیه‌ی اعداد رو به ترتیب صعودی توی جایگاه $2$ تا $n-1$ میذاریم.

اگر $n$ فرد بود، اعداد $1$ تا $n-3$ رو در نظر بگیرید، توی جایگاه $i$ ام ($i < n-3$) اگر $i$ فرد بود، $i+1$ رو بذارید و اگر $i$ زوج بود $i-1$ رو بذارید. توی جایگاه $n-3$ عدد $n$ رو قرار بدید، توی جایگاه $n-2$ عدد $n-2$ رو قرار بدید و توی جایگاه $n$ام عدد $n-1$ رو قرار بدید. اثبات اینکه اوکی میشه هم با خودتون :)

که میشه $O(n)$

B - خرس بقال و کاهو

خوب ما برای این سوال باید اشتراک بازه‌هایی که میده رو به دست بیاریم، و میدونیم $A_1 \cap A_2 \cap A_3 \cap ... \cap A_n = (A_1 \cap ... \cap A_{n-1}) \cap A_n$ هست، اگر بازه‌ی امن برای n-1 تای اول رو داشته باشیم میتونیم برای n تای اول هم بازه‌ی اول رو حساب کنیم، حالا اگه کران پایین بازه‌ی n ام بزرگتر از کران پایین جواب برای اشتراک n-1 تای اول باشه، کران پایین n تای اول میشه کران پایین بازه‌ی n ام و چنین چیزی برای کران بالا هم برقراره (توی کران بالا اگه کوچکتر باشه) پس اشتراک این باشه ها میشه : $[max(a_1, a_2, ..., a_n) , min(b_1, b_2, b_3, ... , b_n)]$ حالا در چه صورت جواب نداره؟ اگه این بازه‌ی جواب تهی باشه یعنی کران پایین اش بزرگتر از کران بالاش باشه، اینهم میشه $O(n)$

C - خرس بقال و خرسستان

می‌تونیم کشور رو به یک گراف همبند و ساده متناظر کنیم که راس‌های گراف همان شهر‌ها و یال‌های گراف جاده‌های بین شهر‌هاست. حالا باید حداکثر یال رو حذف کنیم تا گراف همبندی اش رو از دست نده، می‌دونیم یک گراف همبند حداقل $n-1$ یال داره و یک درخت $n$ عضوی نیز $n-1$ یال داره، پس می‌تونیم زیردرخت پوشای این گراف رو پیدا کنیم و بقیه‌ی یال‌ها رو حذف کنیم. برای پیدا کردن زیردرخت پوشا هم می‌تونیم $DFS$ بزنیم :) که میشه $O(n + m)$ البته خودم از map برای حلش استفاده کردم که خودم $O(n + m lg m)$ حلش کردم.

ارسال‌شده در:
Sajil نوشته:
برا سوال یک تو جایگاه n-2 عدد n-2 رو قرار بدیم برای بخش فرد بودن n؟ خب الان n-2 ومین عدد عددش n-2 هست غلطه که
ارسال‌شده در:
ATofighi نوشته:

Sajil نوشته:
برا سوال یک تو جایگاه n-2 عدد n-2 رو قرار بدیم برای بخش فرد بودن n؟ خب الان n-2 ومین عدد عددش n-2 هست غلطه که


‌نه دیگه! :) نگاه کن، توی جایگاه اول n/2 رو گذاشتم، توی جایگاه آخر n/2+1 و بقیه رو توی جاهای باقی مانده مثلا برای n=4 این شکلی میشه:
$$
2, 1, 4, 3
$$
برای n = 6 هم اینجوری:
$$
3, 1, 2, 5, 6, 4
$$
برای n = 8 هم اینجوری:
$$
4, 1, 2, 3, 6, 7, 8, 5
$$
یعنی اگه عدد $i$ که برابر با $n/2$ و $n/2 + 1$ نباشه رو در نظر بگیری، اگه $i < n/2$ باشه، توی جایگاه $i+1$ قرار میگیره و اگه $i > n/2+1$ باشه، توی جایگاه $i-1$ قرار میگیره.