چند تا سوال برای عید

سیلام علیکم!

عید رو تبریک می‌گم. برای عیدی سه تا از مساله‌های الگوریتمی مورد علاقم رو بهتون تقدیم می‌کنم. این مساله‌ها در اصل مساله‌های برنامه نویسی بودن ولی چون بار تئوریشون از بار عملیشون به مراتب بالا تره همچنین من خعلی دوزشون دارم! ترجیح می‌دم به صورت ۳ تا سوال الگوریتمی مثل همون‌هایی که تو دوره تو آزمون تئوری الگوریتم می‌دن مطرحشون کنم. جواب سوال‌ها رو هم سعی می‌کنم تو تعطیلات عید تو پست بعدی بذارم. امیدوارم لذت کافی رو ببرید. در ضمن، سوال‌ها از آسون به سخت مرتب شدن.

سوال یکم

یک کافی‌نت که یک کامپیوتر متصل به اینترنت بیشتر ندارد را در نظر بگیرید. تعدادی خرگوش می‌خواهند بوسیله این کامپیوتر ایمیل بفرستند و پاسخ ایمیلشان را بخوانند. اگر خرگوشی ایمیلش را در دقیقه i ام بفرستد هیچ کس دیگری نمی‌تواند با کامپیوتر در دقیقه i ام کار کند. همچنین خرگوش دقیقا i+k دقیقه بعد باید پاسخ ایمیلش را بخواند. پس هر خرگوش دو نوبت کامپیوتر را اشغال می‌کند یک بار در دقیقه i‌ و یک بار در دقیقه i+k. در هر دقیقه نیز فقط یک خرگوش حق استفاده از کامپیوتر را دارد. هزینه استفاده از کامپیوتر در دقیقه i ام برابر با C_i می‌باشد و هر خرگوش هزینه دو دقیقه‌ای که از کامپیوتر استفاده می‌کند را می‌پردازد. کافی‌نت از دقیقه ۱ تا n باز است و صاحب کافی‌نت می‌خواهد به مشتریانش طوری نوبت بدهد که درآمدش بیشینه شود شما الگوریتمی از O(n) ارایه کنید که با دریافت n و k و دنباله C_۱, ..., C_n حساب کند در بهترین حالت درآمد کافی‌نت چقدر خواهد بود.

سوال دوم

یک گراف مسطح n راسی و m یالی را در نظر بگیرید. می‌خواهیم تعداد زیر گراف‌های القایی‌اش را که یکریخت با K_۴ (خوشه ۴ راسی) هستند را بشماریم. الگوریتمی از O(n lg n) ارایه کنید که با دریافت n و m و یال‌های گراف این تعداد را حساب کند.

سوال سوم

یک جدول از اعداد صفر و یک را در نظر بگیرید. معکوس کردن یک خانه از جدول به معنای تغییر مقدار آن خانه است (از صفر به یک و بلعکس). چهار نوع حرکت را بر روی جدول تعریف می‌کنیم. در حرکت «بالا» یک سطر از جدول را انتخاب می‌کنیم و تمام خانه‌های این سطر و بالای این سطر را معکوس می‌کنیم. در حرکت «پایین» خانه‌های یک سطر و خانه‌های پایین‌تر از آن سطر را معکوس می‌کنیم. حرکات «راست» و «چپ» نیز به همین ترتیب بر روی ستون‌ها تعریف می‌شوند. به یک جدول «صفر شدنی» می‌گوییم اگر بتوان با حرکات راست، چپ، بالا و پایین طی چند مرحله تمام خانه‌های آن را صفر کرد. یک «زیر جدول» از یک جدول برابر با جدولی است که شامل خانه‌های تقاطع چند سطر متوالی با چند ستون متوالی از جدول اصلی است.

به شما یک جدول n سطری و m ستونی از صفر و یک داده می‌شود. الگوریتمی از O(nm) ارایه کنید که مساحت بزرگترین زیر جدول صفر شدنی این جدول را بیابد.