سلام!
امیدواریم که از سؤالات آزمون ورودی سامرکمپ ستون لذت برده باشید. در ادامه راه‌حل‌های سؤالات مسابقه توضیح داده شدند.
در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات، سؤالات و ابهام‌های خودتون رو مطرح کنید. همچنین اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.
اگر بشقاب‌ها را از 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)
راه‌حل دوم
توجه کنید اگر یک دنباله‌ی هندسی، ناثابت باشد، طول آن نمی‌تواند از ۳۲ بیشتر باشد. بنابراین همه‌ی زیرمستطیل‌های جذاب‌وار سه حالت دارند.
- سطری و ستونی غیرثابت هستند و ابعاد آن‌ها از ۳۲ بیشتر نمی‌شود.
- سطری و ستونی یکی ثابت و دیگری غیرثابت است، در این حالت یکی از ابعاد از ۳۲ بیشتر نمی‌شود و تشکیل یک دنباله‌ی هندسی می‌دهد ولی در بعد دیگر صرفاً کپی شده است.
- سطری و ستونی ثابت است؛ یعنی یک زیرمستطیل است که همه‌ی اعداد آن برابر است.
بررسی ۳ حالت فوق، مشابه مسئله‌ی پیدا کردن بزرگ‌ترین زیرمستطیل است.
لم اول. می‌توان فرض کرد ابتدا همه‌ی عملیات‌های جمع را انجام می‌دهیم و سپس به سراغ عملیات‌های ضرب می‌رویم. پس در واقع باید این n عدد را به تعدادی دسته افراز کنیم و مجموع اعداد هر دسته را در هم ضرب کنیم.
لم دوم. اگر x و y دو عددِ صحیح بزرگ‌تر یا مساوی 2 باشند، می‌توان به‌جای نوشتن جمع آن‌ها (x + y)، ضرب آن‌ها (xy) را نوشت؛ زیرا به عددی بزرگ‌تر یا مساوی می‌رسیم.
لم سوم. اگر همه‌ی اعداد ورودی 1 باشند، بزرگ‌ترین عددی که می‌توان ساخت از تقریباً سه‌تاسه‌تا دسته‌بندی‌کردنِ این اعداد است. به‌طور دقیق‌تر:
- اگر n بر 3 بخش‌پذیر بود، \frac{n}{3} دسته‌ی سه‌تایی می‌سازیم.
- اگر n بر 3 باقی‌مانده‌ی 1 داشت، \frac{n - 4}{3} دسته‌ی سه‌تایی و دو دسته‌ی دوتایی می‌سازیم. (حالت n = 1 را جدا در نظر بگیرید.)
- اگر n بر 3 باقی‌مانده‌ی 2 داشت، \frac{n - 2}{3} دسته‌ی سه‌تایی و یک دسته‌ی دوتایی می‌سازیم.
لم چهارم. طبق لم سوم، هر عدد بزرگ‌تر یا مساوی 2 در یک دسته‌ی جدا قرار می‌گیرد. می‌توان ثابت کرد در حالت بهینه، می‌توان حداکثر یک عدد 1 در دسته‌ی اعدادِ بزرگ‌تر یا مساوی 2 قرار داد.
لم پنجم. ساختن یک دسته با 1ها الویت کمتری نسبت به اضافه کردن 1 به یک دسته‌ی دیگر دارد. همچنین اگر بخواهیم یک 1 به یک دسته اضافه کنیم، بهتر است عدد آن دسته از همه کوچک‌تر باشد.
پیچیدگی زمانی: O(nlog(n))
