راهنمایی سؤالات آزمون ورودی سامرکمپ ستون

سلام!

امیدواریم که از سؤالات آزمون ورودی سامرکمپ ستون لذت برده باشید. در ادامه راه‌حل‌های سؤالات مسابقه توضیح داده شدند.

در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات، سؤالات و ابهام‌های خودتون رو مطرح کنید. همچنین اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.

قاشق و چنگال

اگر بشقاب‌ها را از 1 تا n به‌ترتیب شماره‌گذاری کنیم، برای هر i از 1 تا n، کنار بشقاب iام چنگال یا قاشق t_i و t_{i + n} قرار می‌گیرد. پس زمانی کنار بشقاب i هم قاشق و هم چنگال قرار دارد که t_i \neq t_{i + n} باشد. کافی است این مورد را با ایجاد یک حلقه بررسی کنید.

پیچیدگی زمانی:‌ O(n)

خودپرداز خراب

فرض کنید dp_i کمترین تعداد عملیاتی باشد که برای نوشتن i رقمِ اولِ عدد n نیاز داریم.

به‌عنوان حالت پایه می‌دانیم dp_0 = 0 است. اگر رقمِ iام عددِ n را با n_i نشان دهیم؛ برای هر i از 0 تا n - 1 و هر k از 1 تا بزرگ‌ترین پیشوند مشترک s_{n_{i+1}} و n_{i + 1}, n_{i + 2} \dots رابطه‌ی بازگشتی زیر را داریم:

dp_{i + k} = \min\{dp_{i + k}, dp_i + |s_{n_{i+1}}| - k + 1\}

حال به کمک رابطه‌ی بازگشتی بالا می‌توانید مقدار dp_{|n|} را حساب کنید که پاسخ مسئله است.

سالن سینما

هر بازه در هر ردیف از صندلی‌های سینما که حداقل یک جای خالی دارد را به‌صورت یک سه‌تایی (i, j_l, j_r) در نظر بگیرید. (یعنی در سطر iام همه صندلی‌های ستون j_lام و j_rام خالی است و این بازه نیز قابل گسترش نیست.)

حال به کمک این سه‌تاییِ مرتب می‌توان دو بازه را مقایسه کرد و تشخیص داد که صندلی مناسب‌تر در کدام بازه قرار دارد.

بنابراین کافی است یک ساختمان داده مثل set در نظر گرفته و همه‌ی بازه‌ها را براساس اینکه کدام‌یک جای مناسب‌تری برای نشستن دارند، در آن ذخیره کنیم. سپس هر بار مناسب‌ترین بازه را برداریم و تماشاچی را در صندلی مورد‌نظر (که همواره یا چپ‌‌ترین یا راست‌ترین یا یکی از صندلی‌های وسطی است) برداریم و این بازه را به حداکثر دو بازه‌ی دیگر تقسیم کرده و مجدداً به set اضافه کنیم.

با این کار خواسته‌ی مسئله را شبیه‌سازی می‌کنیم. باتوجه به اینکه حذف و اضافه کردن در set از مرتبه‌ی log تعداد اعضای داخل آن است و چون این تعداد حداکثر nm است، هر حذف و اضافه حداکثر از مرتبه‌ی

O(\log{nm}) = O(\log{n} + \log{m})

است. پس پیچیدگی زمانی در کل برابر است با:

O((nm + k) \times (\log{n} + \log{m}))

هندسی‌وار

اگر یک دنباله مثل a_1, a_2, \dots, a_n هندسی‌وار باشد. عدد صحیح A و عدد گویای q چنان موجود است که:

a_1 = A,\, a_2 = Aq, \, a_3 = Aq^2, \dots, a_n = A.q^{n - 1}

همچنین می‌توان ثابت کرد که اگر یک جدول n \times m «جذاب‌وار» باشد، عدد صحیح A و اعداد گویای p و q چنان موجودند که:

a_{1, 1} = A, \, a_{1, 2} = A.q, \, a_{1, 3} = A.q^2 \dots, a_{1, m} = A.q^{m - 1}
\\
a_{2, 1} = A.p, \, a_{2, 2} = A.p.q, \, a_{2, 3} = A.p.q^2 \dots, a_{2, m} = A.p.q^{m - 1}
\\
a_{3, 1} = A.p^2, \, a_{3, 2} = A.p^2.q, \, a_{3, 3} = A.p^2.q^2 \dots, a_{3, m} = A.p^2.q^{m - 1}
\\
\dots
\\
a_{n, 1} = A.p^{n-1}, \, a_{n, 2} = A.p^{n-1}.q, \, a_{n, 3} = A.p^{n-1}.q^2 \dots, a_{n, m} = A.p^{n-1}.q^{m - 1}

راه‌حل اول

خانه‌ی سطر iام ستون jام را در نظر بگیرید. U[i][j] یعنی حداکثر چند خانه باید از خانه‌ی سطر iام ستون jام بالا برویم تا دنباله هندسی بماند.

به‌طور مشابه منظور از L[i][j] این است که حداکثر چند خانه از خانه‌ی سطر iام ستون jام به سمت چپ برویم تا دنباله هندسی بماند.

حال اگر یک سر مثل i را فیکس کنیم. با درنظر گرفتن U[i][j]های مختلف، انگار یک هیستوگرام داریم که دنبال بزرگ‌ترین زیرمستطیل آن هستیم.

البته اگر بازه‌ی [j_l, j_r] از ستون‌ها یک کاندید بود، باید دو سطر آن را به کمک آرایه‌ی L بررسی کنید و اشتراک بگیرید که آیا این زیرمستطیل ساختنی است یا نه.

پیچیدگی زمانی:‌ O(nm)

راه‌حل دوم

توجه کنید اگر یک دنباله‌ی هندسی، ناثابت باشد، طول آن نمی‌تواند از ۳۲ بیشتر باشد. بنابراین همه‌ی زیرمستطیل‌های جذاب‌وار سه حالت دارند.

1. سطری و ستونی غیرثابت هستند و ابعاد آن‌ها از ۳۲ بیشتر نمی‌شود.
2. سطری و ستونی یکی ثابت و دیگری غیرثابت است، در این حالت یکی از ابعاد از ۳۲ بیشتر نمی‌شود و تشکیل یک دنباله‌ی هندسی می‌دهد ولی در بعد دیگر صرفاً کپی شده است.
3. سطری و ستونی ثابت است؛ یعنی یک زیرمستطیل است که همه‌ی اعداد آن برابر است.

بررسی ۳ حالت فوق، مشابه مسئله‌ی پیدا کردن بزرگ‌ترین زیرمستطیل است.

جمع یا ضرب

لم اول. می‌توان فرض کرد ابتدا همه‌ی عملیات‌های جمع را انجام می‌دهیم و سپس به سراغ عملیات‌های ضرب می‌رویم. پس در واقع باید این n عدد را به تعدادی دسته افراز کنیم و مجموع اعداد هر دسته را در هم ضرب کنیم.

لم دوم. اگر x و y دو عددِ صحیح بزرگ‌تر یا مساوی 2 باشند، می‌توان به‌جای نوشتن جمع آن‌ها (x + y)، ضرب آن‌ها (xy) را نوشت؛ زیرا به عددی بزرگ‌تر یا مساوی می‌رسیم.

لم سوم. اگر همه‌ی اعداد ورودی 1 باشند، بزرگ‌ترین عددی که می‌توان ساخت از تقریباً سه‌تاسه‌تا دسته‌بندی‌کردنِ این اعداد است. به‌طور دقیق‌تر:

1. اگر n بر 3 بخش‌پذیر بود، \frac{n}{3} دسته‌ی سه‌تایی می‌سازیم.
2. اگر n بر 3 باقی‌مانده‌ی 1 داشت، \frac{n - 4}{3} دسته‌ی سه‌تایی و دو دسته‌ی دوتایی می‌سازیم. (حالت n = 1 را جدا در نظر بگیرید.)
3. اگر n بر 3 باقی‌مانده‌ی 2 داشت، \frac{n - 2}{3} دسته‌ی سه‌تایی و یک دسته‌ی دوتایی می‌سازیم.

لم چهارم. طبق لم سوم، هر عدد بزرگ‌تر یا مساوی 2 در یک دسته‌ی جدا قرار می‌گیرد. می‌توان ثابت کرد در حالت بهینه، می‌توان حداکثر یک عدد 1 در دسته‌ی اعدادِ بزرگ‌تر یا مساوی 2 قرار داد.

لم پنجم. ساختن یک دسته با 1ها الویت کمتری نسبت به اضافه کردن 1 به یک دسته‌ی دیگر دارد. همچنین اگر بخواهیم یک 1 به یک دسته اضافه کنیم، بهتر است عدد آن دسته از همه کوچک‌تر باشد.

پیچیدگی زمانی: O(nlog(n))