شاززز-وبسایت آزاد المپیاد کامپیوتر

۱۳

ارديبهشت

کانتست های روزانه شاززز

سلام به همگی. خوبین؟ خوش میگذره؟

توی این پست قراره از یکی از جذاب ترین کار ها در تاریخ شاززز رو نمایی بکنم!

احتمالا همه شما با این مشکل زیاد مواجه شدید که سوال خوب برای حل کردن گیر نمیارید و اینکه باید به سال بالایی ها یا معلم ها بگید که بهتون سوال بدن! حالا بیاید تصور کنید که یه معلم دارید که هر روز بهتون 3 تا سوال جذاب می ده. از اون بهتر تصور کنید که اون معلم هر روز امتحانی برگزار می کنه که داخلش 3 تا سوال خوب هست و بعد سوالاتون رو تصحیح میکنه و شما با یه جامعه آماری بزرگ سنجیده میشین!

چرا این خیلی رویایی به نظر می رسه؟ چون هیچ معلمی وقت و حوصله همچین کاری رو نداره. اگر هم داشته باشه بعد از یکی دو هفته یا خسته میشه یا سوالاش تموم میشه.

حالا فرض کنید این معلم انسان نیست بلکه یه برنامه هست که نه خسته و نه سوالاش تموم میشه! در واقع کاری که ما کردیم این بود که پارامتر های زیادی رو از سوالات سایت codeforces جمع آوری کردیم بعد روشی برای اندازه گیری جذابیت و آموزنده بودن سوال ها ارائه دادیم. نتیجه واقعا راضی کننده بود (در واقع برای من خیلی بیشتر از راضی کننده بود D: ).

از روز یکشنبه این هفته هر روز یک کانتست در Shaazzz Group برگذار میشه. شما می تونید انتخاب کنید که در یکی از ۴ سطح Beginners, Specialists, Candidate Masters, GrandMasters شرکت کنید. پیشنهاد می کنیم که سوالای سطح های دیگه رو هم ببینید! (یعنی لزومی نداره که grandmaster باشید که توی این سطح شرکت کنید).

آزمون هر روز صبح ساعت 9 صبح شروع میشه و شما تا ساعت 12 شب وقت دارید که سوالات هر روز رو حل کنید. در نهایت آخر هر هفته لیست نفرات برتر آزمون همان هفته رو اعلام می کنیم.

در واقع ایده این کار حدودا یک هفته پیش وقتی من و میکاییل قربانی داشتیم صحبت می کردیم به ذهنمون رسید (بعدش هم اکثر کار ها رو میکاییل کرد ) . به شدت امیدواریم که برای همتون مفید باشه.

آپدیت ۱ :

خب یک هفته گذشت...
قرار بود آخر هفته ها رتبه بندی ها رو منتشر کنیم. برای دیدن رتبه بندی ها به کانال تلگرامی CodeforcesMashup مراجعه کنید.

ضمنا برای اینکه به ما کمک کنید سطح کارمون رو بهتر کنیم و بیشتر نیاز های شما رو بفهمیم حتما حتما در این نظرسنجی شرکت کنید.

آپدیت ۲:

خب الان میریم که هفته پنجم رو شروع کنیم! ولی قبل از اون یه سری اتفاقات جالب افتاده که باید بگم‌ :

از الان دیگه ریتینگ داریم و نیازی به کانال تلگرامی برای اعلام رتبه های برتر نیست! می تونید ریتینگ ها رو از طریق training.shaazzz.ir ببینید! به طور کلی این ریتینگ قراره نشون بده چقدر دست شما گرم هست. پس هر چی سوالات سخت تری حل کنید ریتتون زیاد تر میشه و همچنین اگر تنبلی کنید و سوال نزنید از ریتتون کم میشه (ربطی به اینکه توی کانتست ثبت نام کردید یا نه هم نداره).
دقت کنید که فقط سوالات کانتست همون هفته توی ریتینگ شما اثر گذار هستن. یعنی اگر الان هفته پنجم باشه و سوالی از کانتست مربوط به هفته اول رو حل کنید ریتتون تغییری نمی کنه. ولی مثلا اگر امروز چهارشنبه باشه و شما سوالی رو حل کنید که روز شنبه همون هفته توی کانتست اضافه شده روی ریت شما اثرگذار هست.
بعد از نظرسنجی که گذاشتیم دیدیم که عده ای گفتن تعداد از سوالات براشون تکراری هست.
از الان می تونیم این تضمین رو بدیم که اگر عضو فعال یک کانتست باشید در آن کانتست سوال تکراری نخواهید گرفت. در اینجا عضو فعال یک کانتست یعنی کسی که از آخرین ۳ سوال یک کانتست حداقل یک سوال را اکسپت کرده باشد (اگر اعمال این محدودیت موجب این شد که نتونیم سوالات خوب انتخاب کنیم مجبور خواهیم بود که این رو حذف کنیم).
از این به بعد برنامه زمانی و تگ های سوالات هر هفته رو می تونید از اینجا ببینید.
ما به این نتیجه رسیدیم که اگر تعداد آزمون هایی که از افراد با سطح بالاتر می گیریم کمتر باشه، کانتست ها مفید تر خواهند بود.

نویسنده :‌ شایان پردیس

۱۳ نظر

طلاهای دوره ۲۹

۱۲

فروردين

آپدیت بات تلگرامی سوالات شاززز

سلااام

قبل از هر چیز باید از استقبال شما از بات تلگرامی سوالات شاززز تشکر کنیم! (هم اکنون بیش از ۶۰۰ یوزر از آن استفاده می کنند و دارای حدود ۱۰۰ سوال هست).

ضمنا ۵ نفر اول (از نظر تعداد سوال اضافه شده) به صورت زیر هستند :

- شاهین شاهنواز : ۱۲
- الهه توحیدی : ۸

- ASHKAN JOFREI : ۵

- علیرضا کشاورز : ۵

- پارسا قلی پورشهرکی : ۴

و همونطور که قول داده بودیم یک عدد پیتزا به شاهین شاهنواز تعلق می گیره :))

به عنوان عیدی شاززز تصمیم گرفتیم تعدادی قابلیت به بات اضافه کنیم :

- از الان به بعد لازم نیست توی قسمت های متن،هینت یا جواب سوال تایپ کنید. فقط کافیه به جای هر قسمت یک عکس بفرستید!!

- می تونید نظرتون راجع به هر سوال رو با اموجی بیان کنید. (مثلا اگه یه سوال خیلی لایک داشت نتیجه میشه که سوال خوبیه)

- بعد از اینکه توی قسمت "سوال بگیر" برای ما سوال فرستادید در صورت رد شدن سوال دلایل ادمین ها برای رد کردن سوالتون بهتون گفته میشه. (ببخشید این قابلیت باید خیلی وقت پیش اضافه می شد‌!‌ )

اگر ایده ای برای بهتر کردن بات دارید با ما در میون بگذارید!
امیدواریم که مفید واقع شده باشه :))

۰ نظر

طلاهای دوره ۲۹

۰۵

فروردين

پروژه GTOI

سلااااام عیدتون مبارک

ما (جمعی از طلا های ادوار مختلف نه لزوما ۲۹) پروژه GTOI رو از حدودا یک ماه پیش شروع کردیم.

حالا این GTOI یعنی چی؟

این کلمه مخفف graph theory for olympiad in informatics هستش. در واقع ما تصمیم گرفتیم یک کتاب گراف مخصوص المپیاد کامپیوتر بنویسیم که بتونه جایگزینی باشه برای وست.

دلایلمون برای این کار رو می تونم توی این چند خط بگم.

وست انگلیسی هست و ترجمه اش هم ظاهرا چنگی به دل نمی زنه.
شیوه بیان وست دانشگاهی هست و یه مقدار دور از فضای المپیاد هست. این باعث میشه ارتباط برقرار کردن باهاش یه مقدار سخت باشه.
در نهایت وست الگوریتم محور نیست. به عبارتی ما قراره از گرافی که یاد میگیریم توی کد هم استفاده کنیم ولی وست از این لحاظ محتوای چندانی نداره.

پیشرفت پروژه رو می تونید از طریق این لینک مشاهده کنید همچنین مطالبی که تا الان نوشتیم (و بعدا خواهیم نوشت) رو هم می تونید از طریق این لینک ببینید.

اگر پیشنهادی در مورد اضافه یا کم کردن مباحث داشتید یا ایرادی دیدید حتما به ما خبر بدید.

در نهایت امیدواریم که حاصل کار کتابی باشه که برای همه مفید باشه!

آپدیت ۱‌ :

با توجه به اینکه همه هدف ما کمک به شما هست با خودمون گفتیم که می تونیم از کمک های خودتون (برای کمک به خودتون) استفاده کنیم.

حالا چه شکلی می تونید کمک کنید؟‌ همونطور که می دونید داشتن مجموعه خوب از سوالات یکی از اولویت های ما (و طبعا هر کتاب المپیادی دیگه) هست.

شما می تونید سوالاتی که به نظرتون برای کتاب مناسب هست رو از طریق بات تلگرامی سوالات شاززز برای ما بفرستید. قبل از اقدام به اینکار به چند تا نکته توجه کنید.

برای اینکه ما بفهمیم سوال ارسالی شما برای کتاب هست یا نه و برای چه قسمتی از کتاب هست باید تگ سوال را به فرم GTOIx.y انتخاب کنید (به فاصله نگذاشتن و نقطه توجه کنید) که x عدد فصل و y عدد زیربخش فصل هست. به عنوان مثال اگر سوال شما مربوط به فصل درخت ها و زیربخش خاصیت های مقدماتی است تگ سوال باید GTOI2.1 باشه.
می توانید قسمت هینت رو خالی بگذارید. (مثلا فقط بنویسید خالی!) اما در قسمت راه حل خلاصه ای خیلی کلی از حل مسئله رو بیان کنید که اولا اگر ابهامی توی صورت سوال وجود داشته باشه برای ما رفع بشه ثانیا مطمئن بشیم سوال سرکاری نیست و حل میشه. بنابراین لازم نیست قسمت حل رو خیلی دقیق و کامل بنویسید. فقط طوری باشه که ما (طلا ها) متوجه منظورتون بشیم.
ترجیحا صورت سوال متن (نه عکس) باشه که بتونیم کپی کنیم.

پس منتظر کمک های شما هستیم :))

۴ نظر

طلاهای دوره ۲۹

۱۷

اسفند

هفته ای با شاززز

سلاااام!

ما توی هفته ای که گذشت هر شب یک سوال برای شما گذاشتیم (هم تئوری هم عملی).

ولی خب از اونجایی که هیچ چیز موندگار نیست ما هم به دلیل اینکه استقبال لازم و کافی از سوالامون نشد تصمیم گرفتیم این کار رو بیشتر از یک هفته ادامه ندیم!

همینطور تصمیم گرفتیم سوالات رو اینجا قرار بدیم تا برای آیندگان هم بمونه (سوالات آموزنده و جالبی هستن).

پی دی اف سوالات رو می تونید از اینجا دریافت کنید : سوالات شبانه شاززز

جا داره یه تشکر ویژه بکنیم از علی صفری به خاطر اینکه مسئولیت آماده سازی پی دی اف ها رو بر عهده گرفت!

۲ نظر

طلاهای دوره ۲۹

۲۹

بهمن

آزمون عملی دو

سلام!!

دومین کانتست عملی شاززز جمعه این هفته برگذار میشه! مثل کانتست قبلی میتونید در هر بازه ی 5 ساعته ای که می خواید در آزمون شرکت کنید.

کانتست از 8 صبح جمعه تا 12 شب دوشنبه برقرار خواهد بود. امیدواریم که از سوالا خوشتون بیاد! =)

لینک ثبت نام

توصیه میکنیم که حتما همه ی سوال ها رو بخونید!

کسری مظاهری

۲۰ نظر

طلاهای دوره ۲۹

۲۰

دی

آزمون شبه مرحله ۱ ای

سلاااااام

توی این روزای دم مرحله ۱ ما براتون یه آزمون شبیه ساز تدارک دیدیم تا از بی آزمونی رنج نبرید !

شما می تونید از اول پنجشنبه تا آخر جمعه این هفته توی یک بازه زمانی 3 ساعته در آزمون شرکت کنید.

پس از پایان وقت آزمون اسامی ده نفر برتر اعلام خواهد شد.

سوالات آزمون هم به شدت جذاب هستن و سعی شده که شبیه به مرحله ۱ باشن پس به دوستانتون هم بگید که شرکت کنند.

آپدیت ۱ :

از طریق بات تلگرام مرحله ۱ شااززز می تونید در آزمون شرکت کنید!

marhale_yek_shaazzz_bot@

با تشکر از حمیدرضا کلباسی و دبیرستان علامه حلی ۱ .

آپدیت ۲ :
زمان آزمون تا انتهای روز شنبه تمدید شد.

آپدیت ۳:

اسامی ۱۰ نفر برتر به این شکل می باشد :

۱ - سیدمحمدحسین حسینی
۲ - سید آریان وهاب پور
۳ - ماردین نیچی
۴ - هادی علی کرمی
۵ - عماد امام جمعه
۶ - سید محمد مهدی مصطفوی اصفهانی
۷ - علی دوستی
۸ - شایان باب المندبی
۹ - بهراد صمیمی
۱۰ - محمد امین درستی

تعداد افرادی که درصد آنها بالای ۶۰ بود : ۲۰ نفر
تعداد افرادی که درصد آنها بالای ۴۰ بود : ۶۹ نفر
تعداد افرادی که درصد آنها بالای ۲۰ بود: ۱۲۶ نفر
تعداد افرادی که درصد آنها بالای ۰ بود : ۳۲۸ نفر

۳۱ نظر

طلاهای دوره ۲۹

۲۷

آذر

سوالات تلگرامی شااززز

آیا از کمبود سوال یا نداشتن سوال تئوری رنج می برید ؟
آیا به دنبال قوی شدن در یک مبحث خاص ( مثلا ناوردایی ) هستید ولی به اندازه کافی سوال برای حل کردن ندارید ؟

ما (‌طلا های دوره ۲۹ ) برای این مشکل راه حلی پیدا کردیم! از این به بعد می توانید به بات تلگرام شااززز سر بزنید و سوال بگیرید.
نکته قابل توجه این است که می توانید از یک تگ ( مثلا استقرا ) یا حتی چند تگ خاص (مثلا استقرا و اکسترمال و لانه کبوتری)‌ سوال بگیرید. در اینصورت سوالاتی که همه این تگ ها را همزمان دارند برای شما نمایش داده می شود.

شما قابلیت ذخیره کردن سوالاتی که روی آنها فکر کردید و حل نشدند را دارید ! پس نگرانی از بابت به فراموشی سپرده شدن سوالات حل نشده وجود نخواهد داشت.

اگر سوالی حل نشد شما می توانید هینت سوال را بخوانید! در صورت تمایل می توانید راه حل سوال را هم بخوانید ولی در فرهنگ المپیادی این کار ( سوزاندن سوال ) کاری بسیار زشت است :))

در صورت تمایل می توانید به آرشیو سوالات ما سوال اضافه کنید! در اینصورت سوال شما بعد از بررسی ما به لیست سوالات اضافه خواهد شد. همچنین به کسی که بیشترین تعداد سوال را اضافه کند پیتزا تعلق خواهد گرفت! برای فهمیدن اینکه چند تا سوال اضافه کرده اید و نفر چندم هستید می توانید به 'رنکینگ' را ببینید.

https://t.me/ShaazzzProblemBot

با تشکر از دبیرستان علامه حلی ۱ که سرورشان را در اختیار ما قرار دادند.

۷ نظر

شااززز منگولیا

۱۴

آبان

راه حل های آزمون عملی یک

سلام!

خب بدون مقدمه می‌ریم سراغ جواب سوال ها:

سوال ۱ :‌

بلاک های ماکسیمال صندلی ها را در نظر بگیرید که همزمان شامل معلم و دانش آموز نباشند. در بلاک های اول و آخر همه می‌توانند پاپ کرن بخورند ولی در بلاک های وسطی دقیقا یک نفر نمی‌تواند. پس اگر تعداد بلاک های وسطی را x بگیریم جواب سوال n-x میشه.

سوال ۲ :

فرض کنید dp i,rev رو تعریف می‌کنیم مینیمم تعداد حرکات لازم اگر که بخوایم i تا حرف اول رشته رو تبدیل به A کنیم. و rev هم می تونه 0 یا 1 باشه که بهمون میگه قبل از شروع کار ما i تای اول برعکس شده‌اند یا نه.

حالا توجه کنید که اگر تصمیم بگیریم یک حرکت بزاریم که فقط i رو عوض کنه اونوقت مستقل از اینکه خونه i ام چی هست می تونیم فرض کنیم که در آخر می‌تونیم به A تبدیلش کنیم. اگر هم تصمیم بگیریم که تکی i رو عوض نکنیم دو حالت داریم. یا خونه i ام الان برابر با A هست که در اینصورت نباید کاری انجام بدیم. یا اینکه برابر نیست که باید با یک حرکت i تای اول رو عوض کنیم.

فرض کتید change متغیری بولین باشد که نشان می دهد بعد از اعمال rev باز هم باید خانه i ام را تغییر دهیم یا نه.

dp i,rev = min( 1 + dp i-1,rev , change + dp i-1,rev ^ change )

سوال ۳ :

لم : یک عدد بر ۱۱ بخش پذیر است اگر و فقط اگر یکی در میان رقم هایش را جمع و منها کنیم و حاصل بر ۱۱ بخش پذیر باشد!

اثبات :

a1a2a3...an = a1 * 10 ^ (n-1) + a2 * 10 ^ (n-2) + ... + an = a1 * -1 ^ (n-1) + a2 * -1 ^ (n-2) + ... + an (mod 11)

که حکم را ثابت می‌کند.

حالا واضحه که عدد m همیشه بر ۱۱ بخش پذیر خواهد بود. پس کافیه برای عوامل اول ۲ و ۳ و ۵ و ۷ و ۱۱ چک کنیم که آیا m بر اون ها بخش پذیر هست یا نه.

فرض کنید می‌خواهیم باقی مانده m را بر p پیدا کنیم. برای اینکار هم می توانیم از پرارزش ترین رقم شروع کنیم و در هر مرحله باقی مانده تقسیم i رقم اول بر p را حساب کنیم. اگر این باقی مانده تا الان r باشد و رقم i+1 ام x باشد داریم :

r = ( r * 10 + x ) % p

سوال ۴ :

اول از همه اینکه فاصله منهتنی دو نقطه x1,y1 و x2,y2 برابر با |x1-x2| + |y1-y2| هست. می بینیم که ابعاد x و y با هم هیچ ارتباطی ندارند پس می توان آنها را جدا جدا حل کرد و سپس جواب های به دست آمده را با هم جمع کنیم و خروجی بدیم.

حالا بررسی کنید که اگر x ما یک واحد زیاد شود جواب چه تغییری می کند. فاصله ما از نقاطی که x کمتر مساوی دارند یک واحد زیاد می شود و از نقاطی که x بیشتر دارند یک واحد کم می شود. مشابها حالتی که x یک واحد کم شود هم قابل بررسی است.

پس اگر بتوانیم در هر مرحله تعداد نقاطی که مختصات x کمتر مساوی از x ارشیا دارند را حساب کنیم می توانیم با این اطلاعات تغییرات جواب را حساب کرده و جواب جدید را به دست بیاوریم. برای این کار کافیه کل x ها را در یک آ رایه سورت شده ذخیره کنیم و با باینری سرچ ( یا تابع lower_bound ) این تعداد را پیدا کنیم.

سوال ۵ :

برای حل این سوال راه حل های متفاوتی وجود داشت از جمله راه هایی با استفاده از ایده هایی مثل sqrt یا centroid.

اما در اینجا راه حلی دیگر را بیان می‌کنیم که احتمالا ایده کلی آن برای شما جدید و جالب و قابل تعمیم است!

سوال معادل این است که یک درخت n راسی وزن دار داریم و q تا کوئری که در هر کدام دو مجموعه نه لزوما مجزا از رئوس به نام های A و B داده می‌شود و هدف پیدا کردن کوتاه ترین مسیری است که یک سر عضو A و سر دیگر عضو B باشد.

ابتدا در نظر بگیرید که می توانیم هر کوئری را O(n) جواب بدهیم. کافیست با یک bfs مینیمم فاصله هر راس از یک راس مجموعه A را به دست بیاوریم و جواب مینیمم این فاصله ها در بین رئوس B خواهد بود.

اجتماع مجموعه های A و B را S بنامید. حالا توجه کنید که برای بسیاری از رئوس به دست آوردن این مقدار لازم نیست! پس هدف ما است که یک درخت کوچکتر بسازیم که در آن به ازای هر راس S راسی معادل وجود داشته باشد و فاصله هر دو راس در S برابر با فواصل معادل های آنها در درخت جایگزین باشد!

لم : اگر مچموعه S از راس های درخت را داشته باشیم که t عضو دارد می توانیم حداکثر t-1 راس به آن اضافه کنیم که مجموعه جدید نسبت به عمل Lca بسته باشد. (به عبارتی Lca هر دو راس مجموعه عضو مجموعه باشد.‌ )

اثبات :

کافیست رئوس را بر حسب استارتینگ تایم صعودی سورت کنید. سپس به ازای هر دو راس متوالی در S مثل a,b ما Lca(a,b) را به مجموعه اضافه می‌کنیم. ( پس حداکثر t-1 عضو اضافه کردیم )

حالا دوباره راس ها را بر حسب استارتینگ تایم صعودی سورت کنید و اگر a,b دو راس متوالی باشند پدر b همان Lca(a,b) خواهد بود! (باید وزن یال بین a,b باید طول مسیر بین a,b در درخت اصلی باشد)

پس به ازای مجموعه S از راس ها می توان درخت جدیدی با تعداد رئوس حداکثر 2 * |S| ساخت و همانطور که در ابتدا کوئری را O(n) جواب دادیم می توان در درخت جدید کوئری را O(|S|) حل کرد!

سوال ۶ ؛

حل کامل سوال در اینجا گفته نمی‌شود. بعد از فهمیدن هینت زیر انقدر به سوال فکر کنید تا حل بشه!

اول از همه اینکه دایسترا بزنید و بعد از داخل درخت دایسترا از گوشه بالا چپ جدول به گوشه بالا چپ همه روستا هایی که باید دورشون دیوار بکشیم یک مسیر بکشید. ( با رنگ سبز در شکل زیر مشخص شده. )

حالا مسئله معادل پیدا کردن یک دور شامل گوشه بالا سمت چپ جدول هست به طوریکه مسیر سبز که کشیدیم را قطع نکند. ( دور با رنگ نارنجی مشخص شده )