گزارش سوالات مسابقه ی SPbETU Contest #2 ( سوالات شماره ی 245 الی 255 در SGU )

گزارش سوالات مسابقه ی SPbETU Contest #2 ( سوالات شماره ی 245 الی 255 در SGU )

245 - Black-White Army

لینک سوال: http://acm.sgu.ru/problem.php?contest=0&problem=245

نوع سوال: نظریه ی گراف

توضیح راه حل :

246 - Black & White

لینک سوال: http://acm.sgu.ru/problem.php?contest=0&problem=246

نوع سوال: نظریه ی اعداد

توضیح راه حل : می توان مساله را به این صورت مطرح کرد که “بیشترین تعداد مهره های سیاهی که می توانیم در حلقه قرار دهیم بدون اینکه فاصله ی هیچ کدام از دو تای آنها N شود چیست؟”. اگر این سوال را پاسخ این سوال را پیدا کنیم، پاسخ سوال اصلی یکی بیشتر از این مقدار خواهد بود.

اگر مهره ی i-ام را به مهره ی (i+m+1)~ mod ~(2N-1) وصل کنيم، گرافی بدست می آوریم که در آن نمی توانیم دو راس مجاور را سیاه رنگ کنیم. اگر دقت کنیم، این گراف متشکل از یک یا چند حلقه است، زیرا درجه ی هر راس برابر با 2 است. ماکزیمم تعداد راس هایی که در یک حلقه با راس می توانیم سیاه رنگ کنیم، برابر با x ~div~ 2 است. تعداد حلقه ها نیز برابر با c = gcd(N+1,2N-1) است و طول هر حلقه برابر d = (2N~-~1)/c است. بنابراین جواب سوال برابر خواهد شد با: {c*{d/2}}+1 .

247 - Difficult Choice

لینک سوال: http://acm.sgu.ru/problem.php?contest=0&problem=247

نوع سوال: ریاضی + برنامه سازی پویا + اعداد صحیح با دقت بالا

توضیح راه حل : اگر راه حل بدیهی O(n^3) را پیاده سازی کنید و مقادیر مربوط به جدول برنامه سازی پویا را نگاه کنید، می توان جواب را به راحتی حدس زد (با توجه به این مجموع عناصر سطر آخر جدول برنامه سازی پویا باید برابر با C(n,2n) باشد و عنصر اول 2 تا بیشتر از بقیه ی عناصر دیگر است و سایر عناصر برابر هستند): {C(n,2n)}/{n} + 2 .

248 - Integer Linear Programming

لینک سوال: http://acm.sgu.ru/problem.php?contest=0&problem=248

نوع سوال: نظریه ی اعداد + برنامه سازی پویا

توضیح راه حل : می توان از برنامه سازی پویا مانند مساله Knapsack استفاده کرد و مساله را به راحتی با پیچیدگی زمانی O(NV) حل کرد. راه حلی که از قضایای نظریه ی اعداد استفاده کند نیز وجود دارد، ولی نوشتن کد روش برنامه سازی پویا بسیار آسان تر و کم تر است.

249 - Matrix

لینک سوال: http://acm.sgu.ru/problem.php?contest=0&problem=249

نوع سوال: برنامه سازی پویا + تکرار ساده

توضیح راه حل: برای ساختن جواب، ابتدا کدهای گری حداکثر 19 بیتی را حساب می کنیم. کد های گری دنباله اعدادی هستند که دو عدد پشت سر هم تنها در یک بیت اختلاف دارند و کدهای گری 2^i - 1 ام نیز با با صفر تنها در یک بیت اختلاف دارند.

برای ساختن کد گری -ام، را در مبنای دو می نویسیم، و رقم -ام کد گری برابر خواهد بود با حاصل xor بیت های و j+1 -ام. البته اگر بخواهید کدهای گری را بیت به بیت درست کنید، زمان اجرای راه حل شما زِیاد خواهد شد. ولی با توجه به اینکه کد گری -ام و x/2 -ام تنها در یک بیت تفاوت دارند، می توانید از برنامه سازی پویا استفاده کنید.

پس از پیدا کردن کدهای گری، ساختن جدول دو بعدی که دو سلول مجاور تنها در یک بیت اختلاف دارند، کار سختی نیست. اگر جدولمان دارای n سطر و m ستون باشد، اگر سلول (i,j) را برابر با $gray_{i}*2^m + gray_{j}$ قرار دهيم، هدفمان برآورده می شود.

250 - Constructive Plan

لینک سوال: http://acm.sgu.ru/problem.php?contest=0&problem=250

251 - Polynomia

لینک سوال: http://acm.sgu.ru/problem.php?contest=0&problem=251

نوع سوال: هندسی

توضیح راه حل : برای n های بزرگتر از 4 جوابی وجود ندارد. برای n = 3 راه حل بدیهی است، و برای n = 4 با در نظر گرفتن چند حالت خاص می توان جواب را پیدا کرد.

252 - Railway Communication

لینک سوال: http://acm.sgu.ru/problem.php?contest=0&problem=252

نوع سوال: نظریه ی گراف + تخصیص بهینه

توضیح راه حل: اگر تنها بخواهیم تعداد مسیرها را کمینه کنیم، با توجه به اینکه گراف بدون دور است، اگر تعداد رئوسی که parent دارند را بیشینه کنیم، تعداد مسیرها (که برابر با تعداد راس های بدون parent است) کمینه خواهد شد. این کار را می توان با استفاده از maximum bipartite matching انجام داد که در یک طرف گرف شهر ها به عنوان parent و در طرف دیگر به عنوان child قرار دارند.

حال اگر بخواهیم هزینه ی یال های انتخاب شده را نیز کمینه کنیم، می توانیم با استفاده از روش بالا و hungarian algorithm، جواب را در گرافی دو بخشی که وزن یال ها به جای عدد صحیح دوتایی مرتب است، بدست بیاوریم.

البته، راه حل دیگری نیز وجود دارد که آن را امتحان نکرده ام: با توجه به اینکه تطبیق بیشینه در گراف دو بخشی را می توان به صورت مساله ی maximum flow مدل سازی کرد، و الگوریتم های خوبی برای حل مساله ی جریان بیشینه با کمترین هزینه داریم، می توان از این الگوریتم ها نیز استفاده کرد.

253 - Theodore Roosevelt

لینک سوال: http://acm.sgu.ru/problem.php?contest=0&problem=253

نوع سوال: هندسه + جستجوی دودوئی

توضیح راه حل: نقطه ای داخل چند ضلعی محدب است که پائین بخش بالای چند ضلعی و بالای بخش پائین چند ضلعی باشد. پس کافی است ابتدا بخش بالا و پائین چندضلعی را جدا کنیم، و سپس برای چک کردن اینکه آیا نقطه ای داخل چند ضلعی است، با جستجوی دودوئی این دو شرط را در O(log n) چک کنیم. پس پیچیدگی زمانی الگوريتم این مساله عبارت خواهد بود از O(n + m log n) .

254 - Strange Random

لینک سوال: http://acm.sgu.ru/problem.php?contest=0&problem=254

نوع سوال: شبیه سازی

توضیح راه حل: اگر به صورت مستقیم و بی هیچ کار اضافی عملیات را در یک آرایه شبیه سازی کنید، در بدترین حالت حدود 4 ثانیه طول خواهد کشید.

به این دلیل که حافظه ای که برای این سوال داریم محدود است، حذف شدن ها را به این صورت نگه می داریم که arr[i] اگر کوچک تر از صفر باشد یعنی حذف شده است و اگر بزرگتر باشد یعنی حذف نشده است.

ولی اگر بعد از تعدادی عملیات حذف کردن، آرایه را دوباره و با دور ریختن عناصر حذف شده بسازیم، الگوریتم به اندازه ی کافی سریع خواهد بود که Accepted شود. مثلا من بعد از هر 100000 عملیات حذف کردن، آرایه را دوباره از اول می سازم و در بدترین حالت 788 میلی ثانیه طول می کشد.

255 - Winsock 3 Beta

لینک سوال: http://acm.sgu.ru/problem.php?contest=0&problem=255

نوع سوال: ریاضی + جستجوی دودوئی

توضیح راه حل: اگر را برای های کوچک حساب کنید، به راحتی می توان حدس زد که $M_{1}=2$ و $M_{i}=M_{i-1}+i$ . با محاسبه ی این مقادیر و جستجوی دودوئی می توان فهمید که آیا مقدار ورودی جزو این دنباله اعداد هست یا نه.