یک نوار $n$‌ خانه‌ای داریم که بعضی از خانه‌های آن سیاه و بقیه سفید هستند. تعدادی بازه متفاوت داریم که هر کدام از این بازه‌ها بیانگر قسمتی از این نوار است. برای مثال بازه‌ی $[i,j]$ نشان‌دهنده خانه‌ی $i$ ام تا خانه $j$ ام نوار است. در هر مرحله می‌توانیم یکی از بازه‌ها را انتخاب کرده و خانه‌های متناظر آن را تغییر رنگ( سفید به سیاه و سیاه به سفید) دهیم (موظف به تغییر رنگ همه‌ی خانه‌ها هستیم). می‌خواهیم ببینیم آیا می‌توان همه‌‌ی خانه‌ها را سیاه کرد یا نه. شما بایستی الگوریتمی با زمان اجرای $O(n^2)$‌طراحی کنید که امکان سیاه کردن تمام خانه‌ها را بررسی کرده و در صورت امکان مشخص کند که چه بازه‌هایی بایستی تغییر رنگ دهند.

• سوال بعد
• سوال قبل