سال نو مبارک!‍

:: سال نو مبارک!‍

اگر بخواهم صادق باشم از ته دلم خوشحال نیستم رفتن زمستان که خوشحالی ندارد. زمستانم رفت  :'( و تا ۹ ماه دیگر برنمی گردد و تابستان در راه ، اصلا هوا هر چه قدر هم که سرد باشد لذت بخش است در حالی که یک ذره گرما هم تمام سلول های بدنت را موجی می کند ای کاش همیشه هوا سرد و ابری بود البته بدون برف و باران، روزای ابری تصاویر خوب و واضحی توی ذهنم دارند امیدوارم تو بهار هم چند تا داشته باشیم.

لذت یک لیوان بزرگ چایی توی سرما لذتی که حالا حالا ها تکرار نخواهد شد حداقل تا ۷ ۸ ماه دیگر :) اصلا چایی های روز های دیگر مزه چایی نمی دهند ، الان که یاد آن چایی ها افتاده ام اشک در چشمانم حلقه زده :))

بگذریم تقدیر است دیگر از قسمت بدش که بگذریم قسمت های خوب هم دارد سال ۹۴ برای من یکی از بهترین و خاطره انگیز ترین سال هایی بود که تا الان تجربه داشته ام سالی پر از سکانس های به یاد ماندنی که دوست داشتم توصیف مناسبی از همه شان داشته باشم اما خب همه شان را نمی توان بازگو کرد :)

اصلا از همان اول بهار خوب شروع شد و کلی خاطره برایم گذاشت از همان شروع عید نوروز ۹۴ کلی الگوریتم جدید یاد گرفتم که هنوزم باهام هستن و تا همین آخرین ساعات سال که کلی خوش گذشت و آخرین چیزی پارسال خوردم یک ظرف بزرگ سیب زمینی سرخ کرده با بهترین دوستان بود اونم تو مغازه ای که تازه همون روز افتتاح شده بود و کلی از حضور ما ساعت ۱۲ و نیم شب خوشحال شد و سیب زمینی داغ داغ در دم برایمان پخت :)

سالی پر از مسئله ها و الگوریتم های قشنگ و کلی درس ریاضی جدید که دیدگاهمو نسبت به خیلی چیزها تا حد خوبی متحول کردند کلی لذت بردم ، پیاده روی های طولانی تو شب ، شب های پرخاطره تابستان ، روزهای خوب و حساس ، دقایق مهم ، چایی توی سرما با تیشرت ، سالی پر از محبت و....

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

باید از همین الان برای ساختن سالی بهتر تلاش کرد خدا هم مثل همیشه هوایمان را خواهد داشت.

سال خوبی داشته باشین‌ :)

منبع : محمد مهدی طاهریسال نو مبارک!‍
برچسب ها : سالی ,چایی ,داشته ,گذشت ,جدید ,الان

جریان ریاضی در رگ های من

:: جریان ریاضی در رگ های من
عجب عنوان ادیب دانانه ای از آب در اومد ;) (به یاد یک دوست)

و اما جریان از چه قراره؟
امروز ۲۵ بهمن یکی از مهم ترین روز های دوران تحصیل من بود روزی که مدت های زیادی در انتظارش بودم... از خان هفتم دورشته ای کردن گذشتم و رسما دانشجوی رشته ریاضی دانشگاه شهید باهنر شدم زمان انتخاب رشته سال ۹۳ ریاضی را هم به اندازه علوم کامپیوتر دوست داشتم و ۷۰ انتخاب اولم فقط علوم کامپیوتر و ریاضی بود هر چند که همان انتخاب اولم را قبول شدم ، اما زمانی که وارد دانشکده ریاضی شدم و با ریاضیات دانشگاهی بیشتر آشنا شدم علاقه ام به رشته ریاضی خیلی بیشتر از قبل شد چرا که دیدگاه صحیح تری نسبت به ریاضی پیدا کرده بودم و در دو رشته ای کردن مصمم تر شدم تا این که بالاخره بعد از اتمام ترم ۳ و کسب شرایط لازم معدل رسما دانشجوی رشته ی ریاضی به عنوان رشته دوم شدم.
خیلی ها پرسیده اند که چرا با ریاضی دو رشته ای کرده ای؟ و خب اصلی ترین دلیل علاقه بود نه می توانستم از علوم کامپیوتر صرف نظر کنم نه از ریاضی و هر دوی آن ها را دوست داشتم هر چند که هر دو از یک خانواده اند.
تصمیم گرفتم چند خاطره از دوران کودکی ام را بیان کنم که تا به حال برای کسی تعریفشان نکرده ام، اکثرا بعدها متوجه شدم که در واقع یک جور بازی کردن با ریاضیات بوده اند و بعضی از آنها نشان می دهند که چه قدر ریاضیات در رگ های من جریان دارد :) فکر و دیدگاهم بسیار ریاضی گون می باشد :-"

خلاقیت ، معما ، پازل : پازل ها که بهترین و دوست داشتی ترین اسباب بازی های دوران کودکی ام بودند و از زمانی که خیلی کوچک بودم خودم را با آنها سرگرم می کردم یادم می آید سر سفره بعد از این که غذایم را می خوردم یا میل نداشتم سعی می کردم تکه های نانی را پیدا کنم که با هم جفت می شوند و از این که تکه ای خورده شده بود افسوس می خوردم ، حتی پدر و مادرم تعریف می کنند زمانی که خیلی کوچیک بودم و شروع می کردم به شیطنت یا بهانه گیری  کاغذ یا مقوایی را پاره می کردند و تکه هایش را جلویم می گذاشتند تا با کنار هم گذاشتنشان و ساختن کاغذ اولیه سرگرم شوم البته خودم هم چیز هایی یادم هست بزرگتر که شده بودم حوصله ام که سر می رفت کاغذی را به پدرم می دادم و از او می خواستم که برایم به تکه تکه اش کند وقتی درست می شد از او می خواستم تکه هایش را ریز تر کند و این ریز تر کردن را آنقدر تکرار می کردم که دیگر نمی توانستم درستش کنم، پدرم که این علاقه را در من دیده بود برای تولد ۶ سالگی ام یک پازل ۵۰۰ قطعه بهم کادو داد این قدر تصویر پازل را خوب انتخاب کرده بود که توانستم به تنهایی در یک هفته تمام وقت پازل را درست کنم، یادم هست که پیش دبستانی بودم مدرسه که تمام می شد سریع به سراغ پازلم می رفتم و شروع می کردم به درست کردنش خیلی هم حساس بودم که قطعه هایش گم نشوند. این یکی از بهترین و به یادماندنی ترین هدیه های تولدم بود و تقریبا نقش پازل با تمام جزئیات هنوز تو ذهنم هست.
همیشه دوست داشتم یک مکعب روبیک رو از نزدیک لمس کنم همیشه فکر می کردم خیلی جادوییه ولی اون زمان توی هیچ اسباب بازی فروشی وجود نداشت تا این که سوم راهنمایی برای اولین بار باهاش مواجه شدم و سه ماه طول کشید تا درستش کردم و کلی الگوریتم برای حرکت های مختلفش کشف کردم البته بعد ها به کمک اینترنت این الگوریتم ها رو بهینه کردم.
کلا معماهای خلاقانه ریاضی را دوست داشتم مثل مسیر ها و دور های اویلری و همیلتونی در شکل های منظم هندسی (گراف ها)

نظریه اعداد : عادت کرده بودم زمانی که از یک سمت حیاط به سمت دیگر می رفتم ناخود آگاه حساب می کردم که تعداد ردیف های موزاییکی که طی می کنم بر دو، سه یا پنج بخشپذیر هست یا نه جالب بود که فهمیده بودم چهار زیاد جالب نیست و انگار ردیف های دوتایی را دوتا دوتا طی می کنم و هر زمان که از یک سمت حیات به سمت دیگر می رفتم به طور فرضی ردیف های افقی موزاییک های حیات را دوتا دوتا یا سه تا سه تا یا به ندرت پنج تا پنج تا طی می کردم و به خوبی می دانستم که اگر از موزاییک دوم شروع کنم و سه تا سه تا طی کنم آخرین سه تایی درست لب دیوار تمام می شود (حتی هنوز به خاطر دارم) یا می دانستم که تعداد ردیف ها زوج است و اگر می خواستم دوتا دوتا حیاط را طی کنم از اولین ردیف شروع می کردم در نتیجه تعداد ردیف ها به صورت 3k+1  و 2q بودند و حتی به یاد دارم که بر چهار هم بخشپذیر بودند به همین دلیل چهار برایم زیاد عدد جذابی نبود و به اعداد اول علاقه بیشتری داشتم یک را هم که خیلی عادی می دانستم. اون زمان فکر می کنم حدود ۳ یا ۴ ساله بودم اما تا مدت ها عادت داشتم وقتی روی زمین های موزاییک شده راه می رفتم ردیف ها را دسته بندی کنم و بخشپذیری کل ردیف ها به اعداد اول را ناخودآگاه بررسی کنم و دفعه های بعدی از موزاییک های مناسب تری حرکت را آغاز کنم، این شیوه سرگرم کننده راه رفتنم به راهرو و کلاس دبستانم هم کشیده شده بود و هنوز نقش موزاییک های دبستان را تا حد خوبی توی ذهن دارم. بعد ها که با مفاهیم بخشپذیری آشنا شدم این خواص برایم عادی تر شد تا این که این عادت از سرم افتاد.

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

ترکیبیات : خیلی خوب یادمه زمانی که اول یا دوم دبستان بودم مسئله هایی مرتبا از جایگشت های اعداد یک تا n ذهنم را مشغول می کرد برای مثال سعی می کردم یک جایگشت از اعداد یک تا پنج ارائه دهم که هر عدد با مکانش بیشترین فاصله ممکن را داشته باشد مثلا جایگشت ۳۴۵۱۲ فاصله هر عدد با مکانش از دو طرف حداقل دو می باشد (جایگشت را دوری در نظر می گرفتم) و سعی می کردم برای هر n یک جایگشت با این خاصیت بسازم این جوری انگار عدد ها را اذیت می کردم و دلم خنک می شد یا سعی می کردم جایگشتی بسازم که هیچ دو عدد متوالی کنار هم قرار نگیرند به خوبی یادم هست که برای n=3 فهمیده بودم که امکان پذیر نیست و برای n=4 تعداد کمی جایگشت غیر دوری با این خاصیت وجود دارد و جایگشت دوری وجود ندارد و برای n=5 تعداد این جایگشت های دوری خیلی کم بودند بعضی اوقات این فرض را هم اضافه می کردم هیچ عدد در مکان خودش نباشد بعد ها که با ترکیبیات و جایگشت ها آشنا شدم متوجه شدم اینها همان دوست های قدیمی خودم هستند.

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

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

این ها خاطراتی هستند که به خوبی به یادشان دارم و کلی خاطره دیگر هم هست که الان یادم نمی آید شاید کم کم یادم آمد و پی نوشت کردم.
بالاخره این پست تموم شد :D ولی عجب خل و چلی بودم :))
منبع : محمد مهدی طاهریجریان ریاضی در رگ های من
برچسب ها : ریاضی ,خیلی ,جایگشت ,ردیف ,دوست ,داشتم ,دوست داشتم ,دوتا دوتا ,تعداد ردیف ,علوم کامپیوتر ,کرده بودم

یاد بگیریم از حقمان دفاع کنیم

:: یاد بگیریم از حقمان دفاع کنیم

به نظرتان وقتی سوار اتوبوس می شوید و با کلی صندلی خالی مواجه می شوید یا صندلی های خالی قسمت آقایان خالی نباشند و روی یکی از صندلی های قسمت خانم ها بنشینید چه اتفاقی می افتد؟ احتمالا تمام خانم های داخل اتوبوس به شما اعتراض می کنند که این قسمت برای خانم ها است و شما یک مرد هستید و باید به قسمت آقایان بروید... اما زمانی که یک خانم روی صندلی قسمت آقایان بنشیند تقریبا کسی نیست که به این که قسمت آقایان توسط یک خانم اشغال شده است توجه یا اعتراضی کند. واقعا چرا به یک خانم اجازه می دهیم جای یک مرد را بگیرد در حالی که تعداد زیاد از آقایان توی راهروی اتوبوس ایستاده اند البته در اکثر شهرها مرز محکمی در اتوبوس های شهری وجود دارد که باعث می شود این دو قسمت کاملا از هم جدا شوند اما همه جا این طور نیست :| واقعا چرا باید به راحتی از چنین حق های منطقی ساده ای که داریم بگذریم اسم این دلسوزی نیست بیشتر شبیه حماقت است...

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

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

منبع : محمد مهدی طاهرییاد بگیریم از حقمان دفاع کنیم
برچسب ها : قسمت ,خانم ,صندلی ,آقایان ,اتوبوس ,خالی ,قسمت آقایان

مسئله کوتاهترین مسیر در گراف

:: مسئله کوتاهترین مسیر در گراف

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

و قراره که چند نفری رو دعوت کنم که از این پست استفاده کنند.


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

الگوریتم Dijkstra
این الگوریتم مسئله را برای گراف های وزن دار حل می کند.
الگوریتم از یک راس (ریشه) شروع می شود و بعد از اتمام کوتاه ترین فاصله هر راس تا راس ریشه را در یک آرایه ذخیره می کند و در واقع یک درخت می سازد که در این درخت مسیر یکتای هر راس تا ریشه کوتاه ترین فاصله آن راس تا ریشه در گراف اصلی است فاصله هر راس را ریشه را در یک آرایه نگه می داریم که در ابتدا همه ی مقادی مقدار بینهایت می دهیم. (یک عدد خیلی بزرگ که مطمئنیم از بلندترین مسیرمان هم بیشتر است)
ایده حل نسبتا ساده و سرراست است فرض کنید تا این جای کار الگوریتم یک درخت ساخته است و هر یک از راس های این درخت یک کوتاه ترین مسیر تا ریشه دارند (فاصله) بین تمام راس هایی که به راس های این درخت وصل هستند و هنوز در درخت نیستند آن راسی را انتخاب می کنیم که اگر با یک یال به یکی از راس های درخت وصل شود از بقیه کوتاه تر باشد (مجموع وزن یال و فاصله راس داخل درخت که به آن وصل شده است تا ریشه کمینه شود) بدیهی است که چرا این روش گریدی جواب می دهد فرض کنید راسی که کمترین فاصله را تا ریشه با این روش دارد را v بنامیم اگر قرار باشد با مسیری غیر این یال اضافه شده راس v را به درخت اضافه کنیم قطعا فاصله نهایی راس v از فاصله ای که به دست آورده ایم بهتر نخواهد شد زیرا اولین راسی که به جای v‌ اضافه شده فاصله ای بیشتر مساوی تا ریشه نسبت به راس v با یال اضافه شده توسط دایکسترا دارد و در ابتدا هم که درختمان تنها یک راس ریشه را دارد.
توضیحات بیشتر را در ویکی پدیا ببینید.
پیچیدگی : اگر n راس و m‌ یال داشته باشیم و گراف همبند باشد (m>=n-1) می توان پیاده سازی را به شکلی انجام داد که n-1‌ مرحله راس اضافه کردن به درخت دایکسترا داشته باشیم و در هر مرحله راس بهینه برای اضافه کردن به درخت را با log n به دست بیاوریم اگر از درخت دودویی جستجو یا هرم استفاده کنیم می توان الگوریتم را در (O(mlogn حل کرد. که البته با استفاده از هرم فیبوناچی در زمان کمتر هم قابل حله. (این کار زیاد کاربردی نیست! :) )
برای این کار در هر مرحله تمام راس هایی که یک همسایه در درخت مفروض دایکسترا دارند را به محدوده جستجو اضافه می کنیم (درخت دودویی جستجو یا هرم) این اضافه کردن زمانی انجام می شود که همسایه آن به درخت دایکسترا اضافه شده باشد. و هر راس را به صورت یک زوج مرتب (pair در c++) به درخت اضافه می کنیم که عضو اول فاصله آن راس تا ریشه است که برابر است با فاصله همسایه اش (می توان پدر این راس نامید زیرا درختمان ریشه دار است) که باعث افزوده شدن این راس به درخت شده است به علاوه وزن یال بین این دو راس اگر بعد افزودن این راس به درخت قبلا با یک فاصله دیگری در محدوده جستجو وجود داشت و فاصله تولید شده فعلی از فاصله قبلی کمتر بود با log n آن را از محدوده حذف کرده چک کردن با (o(1 انجام می شود (در آرایه فاصله برای هر راسی که در محدوده جستجو است، فاصله ای که با آن در محدوده جستجو قرار دارد و تا به اینجا بهینه است را ذخیره می کنیم) و با فاصله جدید به محدوده با log n اضافه اش می کنم پس هر یال حداکثر یک بار وارد محدوده شده و یک بار خارج می شود.
این سوال می تواند تمرین خوبی برای فهم بیشتر این الگوریتم باشد.

الگوریتم BFS
این الگوریتم مسئله را برای گراف های بدون وزن حل می کند.
در واقع این الگوریتم حال خاص الگوریتم دایکسترا است که همه ی یال ها وزن برابر با یک دارند. و در هر مرحله به جای جستجو در یک درخت دودویی جستجو یا یک هرم می توان قدیمی ترین راسی را اضافه کرد که به محدوده جستجو وارد شده است با کمی بررسی می توانید به راحتی ببینید که این راس در واقع همان راس بهینه در الگوریتم دایکسترا است پس برای این کار از یک صف استفاده می کنیم و راس بهینه را با (O(1 به درخت اضافه می کنیم. پس پیچیدگی آن برابر با (O(E خواهد بود. :)

در هر دو الگوریتم قبلی می توان با روش های مختلف درخت نهایی مسئله را هم ذخیره کرد. و کوتاهترین مسیر بین دو راس را نمایش داد.

الگوریتم Floyed Warshall
این الگوریتم یک الگوریتم داینامیک هست که بعد از اجرا با زمان (O(n^3 کوتاهترین فاصله بین هر دو راس را در یک ماتریس نگه می دارد.
خوبی این الگوریتم این است که کوتاهترین فاصله بین هر دوراس را داریم و بدی آن زمان اجرای بالای آن است.
این فایل خیلی خوب توضیحش داده
در پیاده سازی بالا یک ماتریس دیگر تعریف شده است و آخرین راسی که به وسیله آن فاصله ی بین راس های u و v آپدیت شده است نگه داشته شده است و به وسیله این ماتریس و یک الگوریتم بازگشتی می توان مسیر بین دو راس u‌و v را هم چاپ کرد.
این هم یک سوال نسبتا ساده برای تمرین پیاده سازی این الگوریتم

الگوریتم ‌Bellman Ford
این الگوریتم برای گراف هایی که دور منفی دارند کوتاهترین فاصله برای هر راس از ریشه را به دست می آورد و اگر دور منفی وجود داشته باشد وجود آن را اعلام می کند (اگر در یک گراف دور منفی وجود داشته باشد می توانیم توی آن دور هر چه قدر که می خواهیم دور بزنیم و فاصله بین دو راس را پس از هر دور منفی تر کنیم :D ) چرا که وجود دور منفی مسئله را بی معنی می کند.
توضیحات بیشتر را در ویکی پدیا ببینید که نسبتا خوب توضیحش داده
پیچیدگی : پیچیدگی این الگوریتم از (O(nm است اگر n‌ تعداد راس ها و m‌ تعداد یال ها باشد.
این هم یک تمرین خوب برای فهم بیشتر این الگوریتم
منبع : محمد مهدی طاهریمسئله کوتاهترین مسیر در گراف
برچسب ها : الگوریتم ,فاصله ,درخت ,ریشه ,گراف ,جستجو ,پیاده سازی ,محدوده جستجو ,کوتاه ترین ,درخت دودویی ,الگوریتم مسئله ,درخت دودویی جستجو

پرونده بسته شد!

:: پرونده بسته شد!

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


مسابقه تمرینی

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


مسابقه اصلی

کانتست با استرس شروع شد و طبق معمول باز هم کانتست را بد شروع کردیم و بعد از ۳۰ دقیقه سوال های A و B را اکسپت کردیم (این ضعف همیشه تیم را عقب می انداخت) اشتباه من سر سوال اول باعث شد کمی تایممان خراب شود. اما خدارو شکر با حل شدن سریع H توسط حسین (ششمین تیمی که اکسپتش را گرفت) کمی شروع بدمان جبران شد و خیلی زود به جمع ۱۰ تیم برتر رسیدیم. سعی کردیم تمام سوالات کانتست را خیلی سریع خوانده باشیم به همین دلیل بعد از گذشت تقریبا ۲ ساعت تمام سوالات را خوانده بودیم اما متاسفانه آخرین سوالی که خوانده شد سوال J‌ بود که یکی از اشتباهاتمان بود و بلافاصله بعد از خواندنش راه حل بدیهی با استفاده از ConvexHull را متوجه شدم و نشستم پشت سیستم و متاسفانه سوال به این سادگی تایم اکسپت نسبتا بالایی داشت چرا که زمان آوردن کد از توی نوت هامون یک جایی به جای ۲ نوشته بودم ۱ و حدود ۲۰ دقیقه بعد از پیاده سازی کلا سرکار بودم بعد از تمام شدن کارم با سیستم حسن و حسین که منتظر سیستم بودند تا سوال باگ خور G را با هم پیاده کنند شروع به پیاده سازی G کردند توی این مدت سوال نسبتا بدیهی I را حل کردم اما متاسفانه کد MCMF مان برای گراف های چگال امکان تایم شدنش وجود داشت همچنین پیاده سازی این سوال با توجه به وقت باقی مانده به پایان کانتست و توقعی که از حل دو سوال بیشتر داشتیم چندان کار عاقلانه ای نبود و با توجه به احتمال تایم شدن سوال I را کنار گذاشتم. متاسفانه وقت زیادی این وسط صرف شد تا سوال E حل شود برای پیاده سازی آن تنها ۲۸ دقیقه زمان داشتیم شروع به پیاده سازی کردیم و تقریبا ۵ دقیقه به پایان کانتست پیاده سازی تمام شد سوال را سابمیت کردیم اما متاسفانه همان تست های داخل صورت سوال را رد می کرد و زمان کافی برای دیباگ کردن این سوال را نداشتیم با تمام تلاشی که کردیم برای پیدا کردن اشتباهمان که قطعا اشتباه کوچکی هم بود زمان کانتست به پایان رسید... و تا پایان اختتامیه در شوک از دست دادن با بدشانسی سوال E بودیم... در حالی که با ۶ سوال سهمیه جهانی را گرفته بودند... خدارو شکر تیم های نزدیکمان اکسپت نداشتند و ما همان ۱۰ ام ماندیم...


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


سوالات کانتست امسال

سوالات بسیار خوب بودند و همه به جز دو سوال آخر ک دونستن بعضی از الگوریتم ها تا حد خوبی راه حل را بدیهی می کرد سوالات قشنگ و ایده داری بودند و اگر در مورد سوال H سوتی نداده بودند و به غیر از (O (n^2 و استفاده از ترای سوال اکسپت نمیشد به جمع سوال های خوب کانتست می پیوست نه این که همه بیان با ست و n^3logn اکسپتش کنن ‍٬ کنترل تایم سوال خیلی کار سختی نیست به خدا :| 

ولی در کل از سوالات راضی ام... :) دستشون درد نکنه که از اون ادهاک های کثیف نداده بودن :) وگرنه معلوم نبود چ بلایی سرمون اومده بود...


بدین ترتیب پرونده ۲۰۱۵ برای ما با یک رتبه قابل قبول و امیدوار کننده کاملا بسته شد و پرونده ۲۰۱۶ از همین الان باز شده است...


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


پ.ن: بخش "سوالات کانتست امسال" به پست اضافه شد :)


منبع : محمد مهدی طاهریپرونده بسته شد!
برچسب ها : سوال ,کانتست ,کردیم ,پیاده ,سوالات ,تمام ,پیاده سازی ,سوالات کانتست ,کانتست امسال ,سهمیه جهانی ,پایان کانتست ,سوالات کانتست امسال

حال و روز این روزها...

:: حال و روز این روزها...

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

مدارس و دانشگاه ها دو روز است که تعطیل شده، انواع اقسام شایعات از فایده های لیموترش تا فوت در اثر آنفولانزا در خوابگاه دانشگاه شنیده می شود، همه جا بحث در مورد این بیماری ست، عده ای هم این وسط به فکر سود جویی خودشان هستند برای مثال لیمو ترش را کیلویی ۱۴ هزارتومان می فروشند و قیمت ماسک ها چندین برابر شده است.

البته این ماجرا خوبی هایی هم داشته حداقلش این بود که دانشگاه دو روز تعطیل شد و میانترم ما برگزار نشد یا ترافیک چند وقته اطراف خانه مان بعد از طرح باغملی و آزادی به شکل محسوسی کاهش یافته دیگر فاصله ۵۰۰ متری بین چهارراه اقبال و طهماسب آباد ساعت ۸ شب ۴۵ دقیقه طول نمی کشد.

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

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

خدا به خیر کند...

خب بگذریم


امشب دو دهه از زندگی ام گذشت این ۲۰ سال چه قدر زود گذشت آن قدر زود که تصور سرعتش وحشت زده ام می کند مگر چند تا ۲۰ سال دیگر تا آخر عمرم مانده آیا تمامشان قرار است به همین سرعت بگذرند؟ از ۲۰ سالی که گذشت راضی ام و شکایتی ندارم و همیشه هم بابت همه چی خدا را شکر کرده ام ولی این ۲۰ سال می توانست بهتر از این ها باشد... حالا که دیگر گذشته و از این به بعدش مهم است.


این دو سه هفته خیلی هفته های پر تنشی بوده اند و همچنان هستند، از زحماتی که برای برگزاری کارگاه ACM و مدیریت آن کشیدم تا استرس هایی که قبل از ریجن به سراغم آمده اند...نظیر نتیجه ای که قرار است بگیریم و یا جان سالم به در بردن هر سه مان و ... فقط دو هفته تا دومین ریجن از ۵ ریجنی که می توانم شرکت کنم مانده در حالی که هم نگرانم و هم منتظرم....


حال روز این روزها برایم خیلی عجیب شده...

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

پ.ن۲: هر سالی که تولد آدم می رسه نشون می ده که آدم یک سال پیرتر شده منطقیش اینه که به همدیگه تبریک نگیم روز تولدمون رو ولی نمی دونم چرا بازم به همدیگه تبریک می گیم... :))

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

منبع : محمد مهدی طاهریحال و روز این روزها...
برچسب ها : بیماری ,هفته ,آنفولانزا ,هایی ,خیلی ,مریض ,همدیگه تبریک ,نگران مریض

ریجن 2015

:: ریجن 2015

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


امیدوارم که بتونیم سهمیه دانشگاه رو امسال به 3 تیم افزایش بدیم که دو تا تیم دیگه مون هم بتونن بیان :) در هر صورت ما که هستیم...

پس جا داره سلامی بکنیم به ریجن 2015 :-* تا لرزه ای بر اندام تمام تیم های شرکت کننده شود. :|


امسال قطعا شگفتی ساز خواهیم شد. (عدم تعریف محدوده شگفتی :-")


البته به شرایط امسال سایت تهران چندان خوش بین نیستم. تعداد دانشگاه های کوچیک که متقاضی سهمیه هستند زیاد شدن و سایت تهران نمی تونه با یک کانتست آنلاین سهمیه این دانشگاه ها رو به صفر برسونه و از هر دانشگاه حداقل یک تیم به ریجن می رسه در نتیجه وقوع دوتا اتفاق محتمل هست اول این که سهمیه دانشگاه های بزرگ کم بشه و دوم این که ظرفیت سایت رو ببرن بالا ولی خدا وکیلی کار دوم رو انجام ندید :D تمام مشکلات رو بتونید حل کنید مشکل آمفی تئاترتون رو نمی تونین حل کنید واقعا برای 120 تا تیم جا نداره حتی روی زمینش هم دیگه جا برای تیم ها نخواهد بود :))) اون سلف کوچیک هم دیگه جواب نمی ده :-" (البته زیاد هم بد نیست اگه به 120 تا برسه احتمالا به سهمیه سایت تهران برای مسابقات جهانی یکی اضافه خواهد می شه) .


اسم تیم هم که قرار شد همون پارسالی باشه "!?Heshki heshtow shode" اعضاش هم که همون پارسالی ها هستن فقط همون طور که به دوست خوبمون قول داده بودیم یک عضو به عنوان همراه به تیممون اضافه شده

شاید بخش کوچکی از محبت هایش را جبران کرده باشیم.

می ترکونیم بچه ها.................


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

پ.ن۲: باز هم تیشرت سبز آخه؟! :|

منبع : محمد مهدی طاهریریجن 2015
برچسب ها : سهمیه ,دانشگاه ,ریجن ,سایت ,امسال ,تهران ,سایت تهران ,ریجن پارسال ,همون پارسالی ,سهمیه دانشگاه ,ریجن 2015

غرب زدگی

:: غرب زدگی

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

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

مردم فلسطین سال هاست که به دست یهودیان اسراییل کشته می شوند و این موضوع برایت تبدیل شده فقط به یک خبر تکراری سرتیتر اخبار و تو دم نمی زنی...

عربستان مردم یمن را هر روز بمباران می کند و به هیچ کشوری اجازه نمی دهد که به آنها کمک کنند و تو دم نمی زنی...

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

در حادثه ی صد در صد عمدی منا حدود ۱۳۰۰ مسلمان و ۴۰۰ ایرانی به فجیع ترین شکل ممکن قتل عام شدند و تو دم نزدی...

داعش هزاران شیعه را در سوریه و عراق فقط به خاطر اعتقاداتشان سربرید و هزاران جنایت غیر انسانی مرتکب شد و تو دم نزدی...

و...

انگار که در خواب سنگینی فرورفته باشی.


اما به محض این که در یک شب ۱۵۰ نفر از فرانسویان اروپا به دست همین داعش کشته می شوند لباس عزا به تن می کنی و آه سر می دهی و حس انسانیتت گل می کند حسی که انگار تا به امروز خاموش بوده و الان بیدار شده است ، رنج من از رفتار یکی دو نفر نیست... ای کاش که فقط یکی دو نفر بودند

تنها پس از گذشت ۲ ساعت از حادثه پاریس تمام پروفایل ها و استاتوس هایت در شبکه های اجتماعی شد جمله ی "Pray for Paris" آیا خون این ۱۵۰ نفر از ۴۰۰ هموطنت که در حج امسال کشته شدند رنگین تر است؟ آیا این ۱۵۰ نفر انسان بودند و مردم کشور های خاور میانه که روزانه و هر ساعت در حال قتل عام شدن هستن انسان نیستند؟

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

از مردم غرب توقعی نیست کسانی که ذهنیتی کاملا منفی نسبت به ایران و خاورمیانه دارند ذهنیتی که به وسیله ی رسانه هایشان برایشان ایجاد شده اما تو دیگر چرا؟ تو که در همین ایران و خاور میانه به دنیا آمده ای چرا؟

واژه ای مناسب تر از غرب زدگی نتواستم برایش بیابم.

ای کاش به اندازه جملات "Pray for Paris" جملاتی مشابه برای سایر جنایات غیر انسانی سراسر دنیا شاهد بودیم.

ای کاش خیلی کم تر بودند انسان دوستانی که حس همدردی شان یک شبه با کشتار فقط ۱۵۰ نفر از مردم غرب بیدار شده است.

ای کاش که الان هم بیدار نمی شد......

منبع : محمد مهدی طاهریغرب زدگی
برچسب ها : داعش ,مردم ,کشته ,نزدی ,الان ,بیدار ,خاور میانه ,برای امنیت