BdMO Online Forum

Here is the problemset of BdOI 2010

that's great!

আরে জুবায়ের কোথা থেকে পাইলা এইটা??আমিওতো এইটা খুজতেছিলাম!!

আবির ভাই

I have mbl, so, i cant read the pdf file

কন্টেস্টের সময় ছিল কতক্ষণ?

ভুলে গেছি !! ৪ ঘন্টা মনে হয়

সাকিব ভাইয়ের মনে আছে ?

আমার যতদূর মনে পড়ে ৫ ঘন্টা।
ফলাফল অনেকটা এইরকম ছিল-
১.product sum সমস্যাটা সোজাই ছিল।কিন্তু প্রায় সবাই এইটাতে O(n^2) সমাধান দিছিল যাতে ছিল ১৫ পয়েন্ট।O(n) এ সম্ভবত ৩টা সমাধান ছিল (আমি,জুবায়ের আর ইমরোজ)।
২.Round trip তখন কেউই তেমন কিছু পারেনাই।
৩.Great Win সমস্যাটাই সবাই পারছিল।
৪.Valid number সমস্যাটায় সম্ভবত partial marks পায় সবাই।এতে আমাদের জাজদ্বয় খুবই ক্ষুব্ধ ছিল(আবির ভাইয়া আর মুসা ভাই)।
৫.stone সমস্যায় একমাত্র জুবায়েরই O(n^2) টাইপ কোন সমাধান নিয়ে নাম্বার পাইছিল।(জুবায়ের ওই কন্টেস্টে প্রথম হয়)

যাই হোক জুবায়ের,তোমার কি অবস্থা এখন ওইসব সমস্যায়।আমার তো stone টা এখনও কঠিন কঠিন লাগতেছে।তুমিতো n^2 এ করছিলা আমিতো তাও পারিনাই সেইদিন যখন আবার দেখছি।আর Round Trip এ একটা সমাধান পাইছি কিন্তু তাতেও ১০০% মার্কস হবেনা,নিশ্চিতও না।

সত্যি বলতে কী, এই সমস্যাগুলা নিয়ে contest এর পর তেমন চেষ্টা করা হয় নাই। এর কারণ হইল contest এর পরদিনই আবির ভাইয়ের সাথে সমাধান নিয়ে আলোচনা হইছিল।

Valid number তো মনে হয় prime power factorization দিয়ে করতে হয় ... আমি sure না Round trip টা brute force type এর। প্রথমে চেষ্টা করতে হবে কতভাবে destination এ যাওয়া যায়, তারপর প্রতিক্ষেত্রে আবার কোনভাবে ফেরত আসা যায় নাকি। Code করাটা ঝামেলার ব্যাপার হবে। আমি করি নাই। (সামনে সমাধান নিয়ে কথাবার্তা) Stone এ সবচেয়ে 'ভারী' ascending sequence টা বাইর করতে হয়(not necessarily consecutive)। কারণ এই sequence টা অপরিবর্তিত রেখে বাকি stone গুলা সরাইতে হবে। আমি এইটা বুঝছিলাম আর সেটা $O(n^2)$ এ code করে রেখে আসছিলাম (বা তার চেয়েও খারাপ কিছু... আমার মনে নাই, ঐটা কোনমতে code লিখে আসছিলাম। এমনকি compile করার সময়ও পাই নাই!) । পরে আবির ভাই দেখাইছে যে ascending sequence টা বাইর করার আরো ভাল উপায় আছে।