من نفهمیدم الگوریتم تون چی بوده میشه به صورت خلاصه بنویسید ش
میشه با همون ۹ تا جعبه اول مثال بزنید!من اصراری روی جوابم ندارم ولی خوشحال میشم می بینم کسی میتونه چیزی بهم یاد بده یا چیزی بیشتر از من از سوال درگیرش شده باشه
در هرصورت خوشحالمون میکنید اگ راه حل تونو با ۹ تا جعبه یا اگ فک میکنید قابل توضیح دادن باشه با ۵ تا جعبه بگید
فقط به این دقت کنید که ما از اینکه چی توی جعبه ها هست خبر نداریم ممکنه ما ۵ تا جعبه باز کنیم و ۱ و ۲ و۳ ۴ و ۵ باشن
ترتیب باز کردن مهمه از نیمه شروع کنیم یا از اول یا اخر شروع کنیم مهمه! فقط بازم به این دقت کنید که شما تا جعبه رو باز نکیند عددشو نمی بینید!
(۲۰ بهمن ۱۳۹۱ ۰۵:۲۲ ب.ظ)fsi2013 نوشته شده توسط: من نفهمیدم الگوریتم تون چی بوده میشه به صورت خلاصه بنویسید ش
میشه با همون ۹ تا جعبه اول مثال بزنید!من اصراری روی جوابم ندارم ولی خوشحال میشم می بینم کسی میتونه چیزی بهم یاد بده یا چیزی بیشتر از من از سوال درگیرش شده باشه
در هرصورت خوشحالمون میکنید اگ راه حل تونو با ۹ تا جعبه یا اگ فک میکنید قابل توضیح دادن باشه با ۵ تا جعبه بگید
فقط به این دقت کنید که ما از اینکه چی توی جعبه ها هست خبر نداریم ممکنه ما ۵ تا جعبه باز کنیم و ۱ و ۲ و۳ ۴ و ۵ باشن
ترتیب باز کردن مهمه از نیمه شروع کنیم یا از اول یا اخر شروع کنیم مهمه! فقط بازم به این دقت کنید که شما تا جعبه رو باز نکیند عددشو نمی بینید!
توضیح بالا هم کامل بود هم مختصر. یکم الگوریتمش به تمرکز احتیاج داره. اگه خودتون حوصله شو دارید الان همون با ۳۱ جعبه به صورت واقعی حل کنید. مثلاً ۳۱ عدد مختلف رو کاغذ بنویسید. جدا کنید و هم بزنید و برعکس بچینید. و الگوریتم رو روش اجرا کنید. به جواب میرسید. راستش این طوری توضیحش سخته... ولی اگه خودتون فیزیکی اجرا کنید شاید ببینید نتیجشو. بعد بتونین همه حالات رو براش اثبات کنید. اگه بازم مشکلی بود سعی میکنم تو این هفته به صورت مرتب و منظم و با شکل و توضیحات کامل بذارم....
که اگه اشکالی داشت دوستان گوشزد کنند....
هیچ بعید نیست که من اشتباه کرده باشم...
سوال درخت n میشد شک نکنید
سوال مرتب سازی اشتباه بود چون ترتیب ۲و۳و۱و۴ رو نمی تونست مرتب کنه ولی منطور طراح همونی بود که n-1 مقایسه داشت
باقی سوالا یادم نیست ولی فکر کنم اونی که در مورد گراف بود همش درست بود
اون سوالی که گفته بود ۳۱ جعبه داریم جواب میشه ۳۱ دیگه؟ آخه گفته بود برای اینکه عدد داخل جعبه رو بشه دید باید جعبه ها رو باز کرد خوب برای اینکه ببینیم تو همه ی جعبه ها چیه باید همشو باز کنیم که این زمانش میشه برابر هزینه باز کردن کل جعبه ها و مقایسشون که همون ۳۱ میشه.این بدترین حالتشه دیگه حالا اگه حالتای بهتر هست که جدا اما اینجا بدترین حالتو خواسته.اشتباه میکنم؟
سوال اولش ریسکی بود. سوال دومش واضح و بدیهی بود که ۳ تا گزینه با رد گزینه رد می شه و فقط گزینه حالتی وجود داره که به ازای n-1 بار مقایسه رو انجام بده به طور مثال برای اعداد ۴ ۳ ۲ ۱ رو اگه اینطوری بچینیم ۲ ۴ ۱ ۳ که اگه بررسی کنید برای این حالت خاص می شه n-1 بار. در مورد سوال ۳ خودم هر سه گزینه رو زدم درست. اما به گقته یکی از دوستان یک حالت خیلی خیلی خیلی خاص وجود داره که دو از گزینه هاش غلط میشه. من نمیدونم اون گفت سوال آخر هم فکر کنم بشه ۳۱ البته من نزدم....
دوستان بنظرم ۳۱ میشه جواب سوال جعبه ...
شما چون نیاز دارید که هرکدوم با بغلی مقایسه کنید پس مجبور به وارسی هستید کلشو و بدترین حالت حالتیه که دنباله اعداد صعودی باشه ... وقتی ۳۰ امین جعبه رو باز کنید و با شرایط جور نبود ۳۱ امین مسلما هست چون اگه بیشتر باشه که جزو کناره هاست و نیازه از یه طرف ناکمتر باشه که هست یا اینکه کوچکتره و همون عدد ۳۰ ام عدد مورد نظر بوده که از ۲ سمتش ناکمتره و بدین ترتیب باید ما ۳۱ جعبه رو باز کنیم.
البته این ایده من بود
بچه ها من فکر کنم الگوریتمی که swap داشت
میشه ورودی وجود دارد که به n-1 جابجایی نیاز داشته باشد
واسه بقیش مثال نقض هست
(۲۰ بهمن ۱۳۹۱ ۰۴:۵۴ ب.ظ)fsi2013 نوشته شده توسط: منم سوال اولو سه تارو غلط به دست اوردم
سوال MIN و MAX بود راجب یال ها هم یه دونه اش غلط بود
سوال درخت متوازن و نزدم به نظرم تا ON که جواب نمیشد حالا بالاتر و دیگ استددلال ندارم
سوال جعبه ۳۱
سوال ارایه ایندکسی مثال زدم N-1 حرکت
راه حل تونو بنویسید ما هم جایگشت بدیم مثال نقض پیش بیاد می دونین چون راه حل نداده بود هر راه حلی ادم واسش پیشنهاد میداد میشد یه جایگشت پیدا کنی که ۳۱ تارو کامل باید باز شه من اول با ۸ تا جعبه مثال هارو زدم هی میدیدم هر الگوریتمی پیشنهاد میدم خودم مثال نقضشو میاوردم دیگ خسته شدم راستشو بخوای شما راه حل تون بدین!
شاید با الگوریتم تصادفی که دو تارو باز کنه به طور رندوم بشه ولی الان دیگ ذهنم خسته است شما راه حلو بگین اینجا
در مورد حل سوال درخت متوازن این سوال با برنامه نویسی پویا و با o(nlogn)i انجام میشه.سوال جعبه هم ۱۱ یا ۱۲ میشه.من ۱۱ زدم
(۲۰ بهمن ۱۳۹۱ ۱۱:۰۷ ب.ظ)rezareza2 نوشته شده توسط: دوستان بنظرم ۳۱ میشه جواب سوال جعبه ...
شما چون نیاز دارید که هرکدوم با بغلی مقایسه کنید پس مجبور به وارسی هستید کلشو و بدترین حالت حالتیه که دنباله اعداد صعودی باشه ... وقتی ۳۰ امین جعبه رو باز کنید و با شرایط جور نبود ۳۱ امین مسلما هست چون اگه بیشتر باشه که جزو کناره هاست و نیازه از یه طرف ناکمتر باشه که هست یا اینکه کوچکتره و همون عدد ۳۰ ام عدد مورد نظر بوده که از ۲ سمتش ناکمتره و بدین ترتیب باید ما ۳۱ جعبه رو باز کنیم.
البته این ایده من بود
جواب سوال قطعا یا ۱۱ یا ۱۲ با استفاده از باینری سرچ
(۲۰ بهمن ۱۳۹۱ ۰۴:۵۴ ب.ظ)fsi2013 نوشته شده توسط: منم سوال اولو سه تارو غلط به دست اوردم
سوال MIN و MAX بود راجب یال ها هم یه دونه اش غلط بود
سوال درخت متوازن و نزدم به نظرم تا ON که جواب نمیشد حالا بالاتر و دیگ استددلال ندارم
سوال جعبه ۳۱
سوال ارایه ایندکسی مثال زدم N-1 حرکت
راه حل تونو بنویسید ما هم جایگشت بدیم مثال نقض پیش بیاد می دونین چون راه حل نداده بود هر راه حلی ادم واسش پیشنهاد میداد میشد یه جایگشت پیدا کنی که ۳۱ تارو کامل باید باز شه من اول با ۸ تا جعبه مثال هارو زدم هی میدیدم هر الگوریتمی پیشنهاد میدم خودم مثال نقضشو میاوردم دیگ خسته شدم راستشو بخوای شما راه حل تون بدین!
شاید با الگوریتم تصادفی که دو تارو باز کنه به طور رندوم بشه ولی الان دیگ ذهنم خسته است شما راه حلو بگین اینجا
سوالات امسال الگوریتم خیلی تخصصی بود،این سؤال یه سؤال معروف،یه نمونه خیلی قوی تر این سوال در مرحله دوم المپیاد سال ۸۱ اومده
گزینه هایی که من زدم
۴۱:۲
۴۲:۱
۴۴:۴
۴۵:۴
۴۶:۴
۴۷:۴
۴۸:۱
۴۹:۳
۵۰:۳
false 51:4
۵۲:۲
سوال اول تابلو بود هیچکدومش درست نیست.ببینید نماد تتا یعنی تقریبا خود n^2. حالا یه ضریب اینور اونور زیاد تفاوتی نمیکنه.
چون واسه اعداد خیلی بزرگ مساله رو حل میکنیم.
گزینه اول که رشد نجومی داره.پس این خیلی از n^2 بزرگتره.پس رد.
گزینه دوم گفته n،اینم نمیشه.چون اگه بشه باید n^2 رو بریزی دور.گزینه بعدی هم تکلیفش مشخصه.
(۲۰ بهمن ۱۳۹۱ ۰۴:۵۰ ب.ظ)fsi2013 نوشته شده توسط: میخواست طولانی ترین مسیر رو پیدا کنه اگه میگفت طولانی ترین از یه راس مشخص مثلا ریشه با O N میشد ولی من دیدم چیزی اشاره نکرده دیگ بیشتر از این واسش فسفر نسوزوندم ولی امسال کاش ۵ تا دیگ ریاضی میزدم
منم می گم On میشه تنها باید یه dfs بزنی با v+e که میشه همون n برای درخت
چرا سوال به این آسونی رو نزدین؟
برای اون صحبتی که کردین، که شاید ریشه نباشه. خوب اول اون عنصر رو پیدا می کنیم (on) و بعدش همونی که گفتم
سوال ۹۹ هم (گراف )من برای دو بخش اول و سومش مثال نقض پیدا کردم اما بخش دومش چون گفته یه یالی با وزن کمینه در درخت فراگیر کمینه وجود داره که مطمئنا درسته
(۲۱ بهمن ۱۳۹۱ ۰۲:۲۷ ق.ظ)amink_aut نوشته شده توسط: گزینه هایی که من زدند:
بالاخره شما گزینه ها زدید یا گزینه ها شما رو زدند ؟؟؟
(۲۱ بهمن ۱۳۹۱ ۰۲:۲۷ ق.ظ)amink_aut نوشته شده توسط: جواب سوال قطعا یا ۱۱ یا ۱۲ با استفاده از باینری سرچ
آیا شمابه این نکته که همه ممکنه برابر باشند مگر آخرین جعبه ای که باز میشه و این که جعبه ای رومیخواهیم که از مجاور هاش بزرگتر باشه دقت کردید؟ چطور باباینری سرچ شرط مجاورت تامین میشه؟
سوال ۹۹
مورد اول غلطه، فرض کنید یه راس تنها با یال max به بقیه گراف وصل بشه اونوقت اون یال حتما انتخاب می شه.
مورد دوم درسته، برهان خلف فرض کنید که نباشه بعد از اضافه کردن اون یه دور ایجاد می شه، از اون دور بزرگترین رو حذف می کنیم که مطمئنا min باقی می مونه.
مورد سوم درسته، این هم با فرضی مثل بالایی می شه اثبات کرد. دقت کنید گفته یک دور با این خاصیت وجود داره.
اگر بیش از یک دور می بود می شد مثال نقض واسش زد و غلط می شد.
(۲۰ بهمن ۱۳۹۱ ۰۵:۱۵ ب.ظ)somaye_tex نوشته شده توسط:(20 بهمن ۱۳۹۱ ۰۴:۵۴ ب.ظ)fsi2013 نوشته شده توسط: منم سوال اولو سه تارو غلط به دست اوردم
سوال MIN و MAX بود راجب یال ها هم یه دونه اش غلط بود
سوال درخت متوازن و نزدم به نظرم تا ON که جواب نمیشد حالا بالاتر و دیگ استددلال ندارم
سوال جعبه ۳۱
سوال ارایه ایندکسی مثال زدم N-1 حرکت
راه حل تونو بنویسید ما هم جایگشت بدیم مثال نقض پیش بیاد می دونین چون راه حل نداده بود هر راه حلی ادم واسش پیشنهاد میداد میشد یه جایگشت پیدا کنی که ۳۱ تارو کامل باید باز شه من اول با ۸ تا جعبه مثال هارو زدم هی میدیدم هر الگوریتمی پیشنهاد میدم خودم مثال نقضشو میاوردم دیگ خسته شدم راستشو بخوای شما راه حل تون بدین!
شاید با الگوریتم تصادفی که دو تارو باز کنه به طور رندوم بشه ولی الان دیگ ذهنم خسته است شما راه حلو بگین اینجا
شما هر جایگشتی دوست دارین بدین من با این روش براتون حل می کنم.
البته بین ۱۱ و ۱۲ شک دارم. کامل وقت نشد حلش کنم.
راه حل من:
۵ تا جعبه با شماره های زیر رو باز می کنیم:
۱ و ۸ و ۱۶ و ۲۴ و ۳۱
از بین اینها یکی از بقیه بزرگتره. اگه ۱ و ۳۱ باشه بدترین حالت نمیشه . پس به فرض میگیریم شماره ۲۳/ پس حتماً از ۱۶ تا ۳۱ جعبه ای وجود داره که حاوی عددیه که از ۲ جعبه کناریش نا کوچکتر باشه. (البته این وجود یه همچین جعبه ای رو در نیمه اول نقض نمیکنه! ولی در این نیمه هم حتماً خواهیم داشت.....)
لطفاً حالتهای مختلف رو خودتون بررسی کنید چون یه کم توضیحش اینجا سخته. ولی به راحتی قابل اثباته و مثال نقضی وجود نداره!
و سپس ۲۰ و ۲۷ رو باز می کنیم و دوباره از بین این ۵ عدد بزرگترین رو پیدا و دوباره طبق الگوریتم بالا نصف دیگر از جعبه ها رو حذف میکنیم و به همین ترتیب این الگوریتم رو به صورت تکراری انجام میدیم. که برای هر مرحله ۲ جعبه باز می کنیم. به جز اول کار که برای ۵ جعبه باز کردیم.
با یه حساب سرانگشتی جمع جعبه هایی که باز میشه در بدترین حالت اگه جعبه ها رو به صورت هوشمندانه انتخاب کنیم میشه ۱۱ تا!
البته الگوریتم رو از خودم درآوردم ولی فکر میکنم کار میکنه.....
دوست عزیز اگر همه ی این اعداد این جعبه ها که میگید مساوی باشه چی؟؟ بعدش کجا رو باز میکنید؟؟ آخه شما وقتی یه الگوریتمی رو دقیق بیان کنید، من مطمئنم بازم میشه مثال نقض واسش در آورد که مجبور به باز کردن همه ی جعبه ها باشی.. اما شما اعداد رو مینویسی بعد با توجه به اعداد (جعبه های باز شده) الگوریتم رو داری بیان میکنی..
(۲۱ بهمن ۱۳۹۱ ۱۰:۵۲ ق.ظ)mmoharrer نوشته شده توسط:(21 بهمن ۱۳۹۱ ۰۲:۲۷ ق.ظ)amink_aut نوشته شده توسط: گزینه هایی که من زدند:
بالاخره شما گزینه ها زدید یا گزینه ها شما رو زدند ؟؟؟
(۲۱ بهمن ۱۳۹۱ ۰۲:۲۷ ق.ظ)amink_aut نوشته شده توسط: جواب سوال قطعا یا ۱۱ یا ۱۲ با استفاده از باینری سرچ
آیا شمابه این نکته که همه ممکنه برابر باشند مگر آخرین جعبه ای که باز میشه و این که جعبه ای رومیخواهیم که از مجاور هاش بزرگتر باشه دقت کردید؟ چطور باباینری سرچ شرط مجاورت تامین میشه؟
اگر ۳۱ عدد پشت سر هم یک تابع در نظر بگیری در صورتی که صعودی یا نزولی باشد قضیه مساله حل است...عنصر مربوطه در ابتدا یا انتهاست.....اگر تابع صعودی نباشد پس حداقل یک نقطه اکسترمم محلّی دارد....با باینری سرچ میشه اونو پیدا کرد...اون نقطه جعبه مورد نظر است.
ناکوچکتر یعنی بزرگتر مساوی
سوال ۹۷ رو نزدم
سوال ۹۸ بیش ترین تعداد جابه جایی وقتیه که A برعکس مرتب شده باشه
سوال ۹۹ اولی غلط و دومی و سومی درست بود
سوال ۱۰۰ به نظرم راه حلش اینه
واسه بدست آوردن بیش ترین طول باید تا عمق پایین بریم یعنی تا جایی که به یه برگ برسیم logn
و چون تعداد برگ ها n/2 هستش کلا مرتبه میشه nlogn
سوال ۱۰۱ هم بدترین حالت اینه که جعبه ها به ترتیب صعودی باشن.
نظر تون چیه؟