প্রোগ্রামিং কনটেস্ট সমস্যা ও সমাধান

সূচিপত্র
================
০. একটুখানি কথা
১. সহজ কিছু সমস্যা
২. এসটিএল প্র্যাকটিস
৩. গণিত-সম্পর্কিত সমস্যা
৪. ব্রুট-ফোর্স ও ব্যাকট্র্যাক-সম্পর্কিত সমস্যা
৫. ডেটা স্ট্রাকচার-সম্পর্কিত সমস্যা
৬. গ্রিডি
৭. ডাইনামিক প্রোগ্রামিং
৮. গ্রাফ থিওরি
৯. অ্যাড-হক
১০. জ্যামিতি

একটুখানি কথা
===============
প্রোগ্রামিং কনটেস্টের ইতিহাস কিন্তু অনেক পুরোনো। তোমরা কি কেউ আইসিপিসি ওয়ার্ল্ড ফাইনালসের (ICPC World Finals) পুরস্কার বিতরণী অনুষ্ঠান দেখেছ? এখন তো আবার ইন্টারনেটের কল্যাণে সেই অনুষ্ঠান দেখতে সশরীরে হাজির হতে হয় না। তো যা বলছিলাম, সেই অনুষ্ঠানে প্রতিবার ড. বিল পাউচার (Dr. Bill Poucher) প্রতি বছরের বিজয়ীদের নাম বলে আর সেই লিস্ট শুরু হয় 1977 সাল থেকে। তার মানে আজ থেকে প্রায় 45 বছরেরও আগে প্রোগ্রামিং কনটেস্ট শুরু হয়েছে। আজ 2022 সালে এসে প্রোগ্রামিং কনটেস্টের বিভিন্ন প্লাটফর্ম দাঁড়িয়ে গেছে। ICPC World Finals, IOI, Code Jam, Hacker Cup, Atcoder World Tour Finals, Codechef SnackDown এবং আরো অনেক অনসাইট ইভেন্ট হয়। এ ছাড়াও অনলাইনে প্রোগ্রামিং প্রতিযোগিতা করার এবং প্র্যাকটিস করার বহু সাইট আছে। এ ছাড়া আছে প্রোগ্রামিং প্রতিযোগিতা নিয়ে আলোচনা করার অনেক ফোরাম। গত 10 বছরেরও কম সময়ে প্রোগ্রামিং প্রতিযোগিতার যে প্রসার হয়েছে, তা আসলে কথায় প্রকাশ করা যাবে না। কিন্তু কষ্টের বিষয় হলো, আমাদের দেশে সে তুলনায় তেমন প্রসার নেই। আমাদের দেশে গত দশ-পনেরো বছর ধরে গড়ে প্রতি বছর চার-পাঁচটি করে কনটেস্ট হয়। কিছু দিন আগে থেকে (2011 থেকে শুরু) প্রতি বছর প্রোগ্রামিং ক্যাম্প করার চেষ্টা করা হয়। এছাড়াও স্কুল-কলেজ পর্যায়ে NHSPC আয়োজন করা হচ্ছে অল্প কিছু দিন আগে থেকে, তাও আবার নিয়মিত নয়। এতেই সীমাবদ্ধ আমাদের প্রোগ্রামিং কনটেস্ট। সেই তুলনায় রাশিয়া, চীন, পোল্যান্ড যারা কিনা প্রোগ্রামিং কনটেস্টে সব সময় এগিয়ে থাকে, তাদের আয়োজন শুনলে বা দেখলে আমার বেশ খারাপ বা আফসোস লাগে। এজন্য না যে তারা অনেক কিছু করে। বরং তারা আমাদের চেয়ে অনেক কম অনসাইট কনটেস্ট করে। তারা যা করে তা হলো মানসম্মত ক্যাম্প। সেখানে তাদের বুড়ো কনটেস্ট্যান্টরা এসে মানসম্মত ক্লাস নেয় এবং মানসম্মত প্রবলেম নিয়ে আলোচনা করে। ফলে দেখা যায়, আমরা আমাদের দেশের কনটেস্টে দশটি সমস্যার ভেতরে সাত-আটটি করে সমাধান করতে পারলেও তাদের কনটেস্টে যে দশটি সমস্যা থাকে তার দুই বা তিনটি টেনেটুনে সমাধান করতে পারি। তারা ঠিকই আট-নয়টি করে সমাধান করে বসে থাকে। বলার অপেক্ষা রাখে না আমাদের আর তাদের ভেতরে আকাশ আর পাতাল তফাত।

আমার কাছে মনে হয়েছে সমস্যা সমাধানের দুটি হাতিয়ার আছে। এক জ্ঞান, দুই চেষ্টা। তুমি যদি না জানো BFS কী বা DP কী, তাহলে তো সে-সম্পর্কিত সমস্যা সমাধান করা কঠিন। হয়তো BFS বা DP আসলে বেশ সহজ জিনিস, কেউ বই না পড়েই নিজে নিজে শিখতে পারবে বা নিজে থেকেই সেসব সমাধান বের করতে পারবে। কিন্তু FFT বা KMP বা Convex Hull ইত্যাদি-সম্পর্কিত অ্যালগরিদম বা থিওরি এসব যদি তুমি না পড়ো, না শেখো, না জানো, তাহলে সেসব-সম্পর্কিত সমস্যা সমাধান করা খুবই কঠিন হবে। সেজন্য প্রথমত জ্ঞান দরকার। আর দ্বিতীয় জিনিস হলো চেষ্টা। তোমাকে সমস্যায় বলা থাকবে না যে এই সমস্যা BFS দিয়ে সমাধান হবে। তোমাকে নানা কিছু চিন্তা করে, বিভিন্নভাবে এগিয়ে বুঝতে হবে যে এটা এভাবে করে BFS করলে সমাধান হবে। চেষ্টাকে চাইলে প্রবলেম সলভিং স্কিলও বলা যায়।

কিছু জ্ঞান, যেমন– BFS, DFS, MST, KMP, DP, GCD ইত্যাদি খুবই সহজ জিনিস। যারা এসব এখনো পারো না, তারা হয়তো আমাকে মনে মনে গালি দিচ্ছ যে কত কঠিন জিনিস, আর আমি কিনা এদের খুবই সহজ বলছি। কিন্তু সত্যি বলতে প্রোগ্রামিং কনটেস্টে আরো অনেক কঠিন কঠিন জিনিস আছে। সেসবের তুলনায় এসব খুবই সহজ। আমার মূল লক্ষ্য ছিল সেসব কঠিন জিনিস নিয়ে বই লেখার। যেমন– FFT, NTT, Persistent Data Structure, Link Cut Tree ইত্যাদি। কারণ আমার মনে হয়েছে, সহজ বিষয়গুলো তো একজন চাইলেই ইন্টারনেট থেকে পড়ে শিখতে পারবে কিন্তু এই কঠিন বিষয়গুলো ইংরেজিতেই ভালো করে নেই। ভালো করে কোথাও থাকলেও এক জায়গায় সব নেই। তাই বাংলায় লিখলে হয়তো যারা বাংলাদেশের অ্যাডভান্সড কনটেস্ট্যান্ট তাদের জন্য ভালো হতো। কিন্তু সেই বই লিখতে গিয়ে মনে হয়েছে যে আসলে সহজ বিষয়ের ওপরেও বই দরকার। এজন্য না যে আমাদের দেশে অ্যাডভান্সড কনটেস্ট্যান্টের সংখ্যা খুবই কম, বরং এজন্য যে আমি যখন অ্যাডভান্সড বিষয়ের ওপর লিখব, তখন যেন এটা মনে না হয়, আরে এই বিষয় কি ওরা জানে? অমুক টেকনিক কি ওরা জানে? এসব ভেবেই আমার প্রোগ্রামিং কনটেস্ট : ডেটা স্ট্রাকচার ও অ্যালগরিদম বই লেখা। বইটি লেখা শুরু হয় 2011 সালে, আর বেশির ভাগ জিনিস লেখা শেষ হয় 2013 সালে। এরপর নানা রকম আলসেমি পার করে 2015-তে তা পিডিএফ আকারে ছাড়া হয়, 2016-তে রাফির কল্যাণে হার্ডকপি হিসেবে। কঠিন বিষয়ের ওপর বই লেখার ইচ্ছা নিয়ে শুরু করে পাঁচ বছর কাটিয়ে দিয়েছি সহজ বিষয়ের ওপর লিখে। কিন্তু সেই বইয়ে শুধু থিওরি ছিল। সেখানে তেমন কোনো সমস্যা নিয়ে আলোচনা ছিল না, প্রবলেমের লিস্টও ছিল না। সত্যি বলতে, ঐ বইয়ে আরো একটি অধ্যায় ছিল, যেখানে প্রায় 300-400 সমস্যা নিয়ে আলোচনা করা ছিল (যতদূর সম্ভব 2013 সালের সব আইসিপিসি রিজিওনালের সমস্যা ও সমাধান নিয়ে ছিল, এমনকি NEERC, CEERC এবং চীনা রিজিওনালগুলোও ছিল)। কিন্তু বইয়ের আকার এত বিশাল হচ্ছিল, আর সেই সমস্যার আলোচনা এত সংক্ষেপে ছিল যে আমি পরে ওই অংশ মুছে ফেলি (এমনিতেই থিওরি আলোচনা সংক্ষিপ্ত বলে যেই পরিমাণ গালাগালি হজম করতে হয়েছে, সে তুলনায় ওই চ্যাপ্টার মুছে দিয়ে ভালোই হয়েছে বইকি!)। প্রথম বইয়ে প্রথম হাতিয়ার (জ্ঞান) নিয়ে কথা হলেও দ্বিতীয় হাতিয়ারের (চেষ্টা বা প্রবলেম সলভিং স্কিল) কোনো কিছুই ছিল না। সেই জন্যই আমার এই দ্বিতীয় বই। আমি নিজে প্রবলেম ক্যাটাগরাইজেশনে অত অভ্যস্ত নই। তাই এই বইয়ে যত সমস্যা আলোচনা করা হয়েছে তার লিস্টগুলো আমি বিভিন্ন সোর্স থেকে নিয়েছি। মূল লিস্ট হলো রুজিয়া লিউ-এর এক নম্বর বই (সহজ বই)-এর লিস্ট। এছাড়াও আমি Timus-এর বিগিনার প্রবলেমের একটি লিস্ট ব্যবহার করেছি। LightOJ-এর টপিকের লিস্ট থেকেও বেশ কিছু সমস্যা আমি ব্যবহার করেছি। জ্যামিতির জন্য বাংলাদেশের জ্যামিতির গুরু নাফির একটি প্রবলেম লিস্ট ছিল আমাদের বুয়েটের গ্রুপে, সেই লিস্ট ব্যবহার করেছি। গ্রিডি (greedy) সমস্যার জন্য কোডফোর্সেস (Codeforces)-এর কিছু সমস্যা ব্যবহার করেছি। এরকম নানা জায়গা থেকে প্রবলেম নিয়ে আলোচনা করা হয়েছে।
এই বইয়ে থাকা প্রবলেমগুলো আশা করি তোমার প্র্যাকটিসে সাহায্য করবে। এ ছাড়াও আশা করি তোমরা উপলব্ধি করবে যে চীনের বাচ্চা কনটেস্ট্যান্টরা রুজিয়া লিউ-এর যেই `সহজ’ বই পড়ে তাতে কী কী সমস্যা আলোচনা করা আছে। যদি সহজ বইয়ে এরকম কঠিন সমস্যা থাকে তাহলে তার কঠিন বইয়ে না জানি কত কঠিন সমস্যা আছে! যদি তোমরা সত্যিকারের ভালো কনটেস্ট্যান্ট হতে চাও, তাহলে এই বইয়ের প্রবলেমগুলোকে তোমাদের কাছে সোজা লাগতে হবে। আর যারা শখের বশে কনটেস্ট করতে চাও, খাটাখাটনি করতে চাও না, তারা এই বইকে নিরাপদ দূরত্বে সরিয়ে রাখতে পারো। আবার চাইলে সেসব সমাধানের চেষ্টাও করতে পারো। চেষ্টা করতে থাকলে এক সময় পারবে। আর যদি নাও পারো, আমার মতে ক্ষতি নেই, এসব করে যে আনন্দ পাওয়া যায় সেটাই প্রধান পাওয়া।
বইটা কীভাবে পড়বে? তুমি একটি করে প্রবলেম দেখো আর নিজেরা তা সমাধান করার চেষ্টা করো। যদি নিজেরা পারো তাহলে তো ভালো কথা, আর না পারলে সমাধান একটু একটু করে পড়ে দেখো। এক লাইন দুই লাইন করে পড়ো আর নিজেরা আবার চিন্তা করো। যদি নিজে সমাধান করতে পারো তাহলেও এই বইয়ের সমাধান পড়ো। কারণ দেখা যাবে, যদিও এই সমস্যা BigO{n^3}-এ সমাধান হয়, কিন্তু এর BigO{n^2} সমাধান হয়তো আমি বর্ণনা করেছি। বা অনেক সময় আমি নানা ছোটোখাটো ট্রিকের কথা বলেছি যা হয়তো অন্য প্রবলেমে কাজে আসবে।

অনেক সময় এটাও হতে পারে যে, তুমি কোনো একটি সমাধান বুঝতে পারছো না। এরকম না হওয়াটাই অস্বাভাবিক (সংক্ষিপ্ত সমাধানের জন্যই হোক বা কঠিন সমস্যার জন্যই হোক)। এখানে অনেক সমস্যা আছে যেগুলো আমার নিজের সমাধান করতে বা অন্যের সমাধান পড়ে বুঝতে চার-পাঁচ দিন করে লেগেছে। সুতরাং তুমি যদি এক দিন ব্যয় করেই হাল ছেড়ে দাও তাহলে হবে না। কাগজে কলমে বিভিন্ন কেস নিয়ে চিন্তা করতে হবে যে আমি কী বলছি, বা তা কীভাবে হচ্ছে বা হতে পারে। সব সমস্যাই যে কঠিন তাও নয়। সুতরাং চাইলে যেগুলো কঠিন সমস্যা সেগুলো পরে পড়বে বলে রেখে দিতে পারো।

অনেকেই বলে বই আরো সহজ করে লিখতে, কিন্তু সত্যি বলতে, এর চেয়েও সহজ করে লেখা একটু কঠিন। আমি যদি আরো সহজ করে আরো অনেক সময় নিয়ে লিখি, তাহলে আমার আসল উদ্দেশ্য (কঠিন বিষয়গুলো শেখা এবং তা নিয়ে লেখা) কখনই পূরণ হবে না। সহজ বিষয়গুলোর ওপর লেখা বা শেখানোর অনেকেই আছে, কিন্তু কঠিন জিনিসগুলো নিয়ে সংক্ষিপ্ত লেখাও নেই। সুতরাং, আমি যদি কখনো আমার লক্ষ্য পূরণ করতে পারি তাহলে হয়তো কোনো দিন আবার এই `কঠিন’ করে লেখা বই রিভাইজ করে সহজ করে আরো ছবি দিয়ে লিখব। কিন্তু আশা করি তত দিনে আমাদের দেশে এত 2400 রেটিংয়ের কোডার থাকবে যে, এই কঠিন বই বুঝতে পারছি না—এ কথা বলা মানুষের পরিমাণ কমে যাবে বা তাদের মধ্য থেকে কেউ সহজ করে বই লিখবে।

আগেই বলেছি, এই বইয়ে UVa, Timus, Codeforces, LightOJ থেকে সমস্যা আছে। আমি প্রবলেমের নাম্বারের পাশাপাশি প্রবলেমের নাম দিয়েছি, যাতে তোমাদের খুঁজে পেতে সুবিধা হয়। বিশেষ করে কোডফোর্সেসের ক্ষেত্রে এই সমস্যা বেশি দেখা যায়, কারণ সেখানে একটি প্রবলেমের নাম্বার দেওয়া বেশ কঠিন (কারণ একই সমস্যার একাধিক নাম্বার আছে)। আর মাঝে মাঝে আমি প্রবলেম স্টেটমেন্ট একটু পরিবর্তন করে নিয়েছি। যেমন, দেখা যাবে মূল প্রবলেমে বলা হয়েছে ছাগলের কাহিনি, আমি লিখেছি গাধার কাহিনি। অনেক সময় মূল প্রবলেমে বলেছে যে অমুক অমুক ডিজিট ব্যতীত অন্য সকল ডিজিট ব্যবহার করা যাবে। কিন্তু আমি প্রবলেমে লিখেছি যে অমুক অমুক ডিজিট কেবল ব্যবহার করা যাবে। এসবের মধ্যে কিন্তু তেমন কোনো তফাত নেই। সুতরাং আশা করি তোমাদের বুঝতে সমস্যা হবে না।

তোমরা চাইলে প্রবলেমগুলো নিজে কোড করে সমাধান করতে পারো। বা চাইলে শুধু সমাধান চিন্তা করতে পারো। অনেক সময় এমন হয় যে, আইডিয়া পেলে কোড করতে পারব কিন্তু আইডিয়া পাই না। সেসব ক্ষেত্রে যত বেশি সমস্যা ও সমাধান দেখা যায় তত ভালো।

আর আমরা এই বইয়ে আলোচিত সমস্যাগুলোর কোড রাখার জন্য একটি গিট রিপোজিটরি খুলেছি যার লিংক – github.com/shanto86/problem-book-1-solutions। তোমরা চাইলে তোমাদের অ্যাকসেপ্টেড কোড এখানে পাঠাতে পারো, যাতে অন্যরা তা দেখে শিখতে পারে। আমরা চেষ্টা করব কোনো একটি সমস্যার কেবল একটি সমাধান এখানে রাখার। তবে যদি কেউ সম্পূর্ণ ভিন্নভাবে কোনো সমস্যা সমাধান করে, তাহলে আমরা সেই নতুন সমাধানও রাখতে পারি।

সেই সঙ্গে ধন্যবাদ Nayeem Jahan Rafi, Evan Hossain, Rezwan Arefin, Md Sahedul Islam Sohel, Mohtasim Bellah, Moudud Khan Shahriar, Abdullah Al Raqibul Islam, Imran Ziad এবং Sumit Saha-কে, যারা বইয়ের টেকনিকাল রিভিউ করতে সাহায্য করেছে।

অতঃপর এভাবে কেটে যায় পাঁচ বছর! অর্থাৎ এই বইয়ে যা লেখা হয়েছে তা ২০১৫-২০১৭ সালের, আর এই অনুচ্ছেদ লিখছি ২০২২ সালে। অবশেষে এই বই ছাপানোর উদ্যোগ নেওয়া হয়েছে। যদিও এত লম্বা সময় অতিবাহিত হয়ে গেছে তবুও আমার মনে হয় এই বইয়ের সমস্যাগুলো এখনো বর্তমান সময়ের জন্য উপযোগী আছে। যদিও এখন আইসিপিসি বা ওয়ার্ল্ড ফাইনালসের সমস্যা আর বিভিন্ন অনলাইন প্লাটফর্মের সমস্যা একটু অন্য রকম হয়। সে ভিত্তিতে এই বইয়ের সমস্যাগুলো আইসিপিসি বা ওয়ার্ল্ড ফাইনালসের জন্য বেশি উপযোগী। আশা করি সকল প্রতিযোগীর এই বইটি কাজে আসবে।