Programming Interview Tanvir Hasan Anick

ইন্টারভিউ সিরিজের আগের লিখাগুলা এই লিঙ্কে পাওয়া যাবে ।

প্রশ্ন ঃ প্রোগ্রামিং কন্টেস্ট এর ব্যাপারে প্রথম কিভাবে জানছিলা মনে আছে ? উত্তরঃ হুম। ভার্সিটিতে ভর্তি হবার আগে হালকা প্রোগ্রামিং শিখে ছিলাম। আমি একটু দেরিতে ভর্তি হবার কারণে আমার অন্যান্য ফ্রেন্ডরা একটু এগিয়ে ছিল। ওইসময় সাস্টের এক ফ্রেন্ড ইভান, (স্কুল ফ্রেন্ড মূলত) ওর কাছ থেকে প্রথম "uva peter smoke" প্রবলেমটার লিঙ্ক পাই।

সেইদিন থেকেই মূলত প্রোগ্রামিং কন্টেস্ট নাম এ কিছু একটা আছে। এই জিনিসটা জানা হয়েছিল।  প্রশ্নঃ প্রথম অনসাইট কনটেস্ট কথা মনে আছে ? 
উত্তরঃ হ্যাঁ ২০১২ সালে। আমার প্রথম অনসাইট ছিল ICPC-2012। ড্যাফোডিল ইউনির্ভাসিটিতে। কোনকিছুই তেমন করি নাই, শুধু এদিক ওদিক তাকিয়ে ছিলাম আর একটা চাইনিজ টিমের সল্ভ করার আনন্দ দেখেছি। প্রশ্নঃ কি টাইপের প্রবলেম সল্ভ করতে বেশি ভাল লাগে ? উত্তরঃ নাম্বার থিউরি আর ডিপি। প্রশ্নঃ কোন প্রবলেম সল্ভ এর সময় "Thinking Process" কি থাকে প্রবলেম পড়ার পর ? উত্তরঃ প্রবলেম পড়ার পরেই প্রথমে আগে ছোট ছোট কেস খাতায় লিখে একটা বেসিক আইডিয়া দাঁড় করানোর চেষ্টা করি। যদি দেখি যে ঠিকঠাক আছে তখন কোড করা শুরু করি। আর যেসব প্রবলেম মনে হয় প্যার্টান আছে, সেইগুলার জন্য আগেই একটা ব্রুটফোর্স কোড লিখে র্স্কিনে কিছু কেস রান করিয়ে খাতা কলম নিয়ে বসি প্যার্টান বের করার চেষ্টায়। প্রশ্নঃ UAP এর এসিএম ট্রনিং কিভাবে হয় ? উত্তরঃ Uap সাম্প্রতি সময়ে কন্টেস্ট এর রেজাল্ট ভাল করার জন্য অনেক আগ্রহী। সেইজন্য বর্তমানে সিনিয়র ও জুনিয়র দুই লেভেলের জন্য আলাদা আলাদা ট্রেইনার নিয়োগ দেয়া হয়েছে। সিনিয়রদের এখন শিপলু স্যার আর জুনিয়রদের সুপ্ত ভাই ট্রেইনিং করাচ্ছে। আর যেহেতু ভার্সিটি এখন পার্মানেন্ট ক্যাম্পাসে আছে, তাই সুযোগ সুবিধা আগে থেকেও এখন অনেক বেশি। প্রশ্নঃ আইওআই যারা না করে ভার্সিটি থেকে কনটেস্ট করে তারা দেখা যায় আইওআই যারা করেছেন তাদের থেকে পিছাইয়া থাকে , অনেক সময়ই পিছাইয়াই থাকে । যারা ভার্সিটি তে মাত্র কনটেস্ট নিয়ে জানল তাদের কি করা উচিত এই দুরুত্ব কমানোর জন্য ? উত্তরঃ যারা ioi করে তাদের জন্য অনেক স্পেশাল ট্রেইনিং হয় যার ফলে তারা স্বাভাবিকভাবে ভার্সিটিতে কন্টেস্ট করে তাদের থেকে অনেক এগিয়ে থাকে। সেই হিসেবে দেখা যায় ভার্সিটির সেই স্টুডেন্টকে তাদের লেভেল এ আসতে আসতে অনেক সময় লেগে যায়। সেই সময়ে হয়ত তাদের ভার্সিটি লাইফও শেষ হয়ে যায়। যেমনঃ আমি tongue emoticon:p আর আমি প্রাইভেট ভার্সিটিতে পড়তে গিয়ে একটা জিনিস দেখেছি, বেশিরভাগ স্টুডেন্ট ভর্তি হয় এখানে একটা হতাশা নিয়ে। তাদের সব-সময় এমন একটা মেন্টালিটি সেট করা থাকে যে আমি পাবলিক ভাল কোথায়ও চান্স পাই নাই তাই আমাকে নিয়ে এইসব কন্টেস্ট টাইপ জিনিস কোনদিন হবে না। তাই যারা ভার্সিটি ভর্তি হয়ে কন্টেস্ট সম্মন্ধে জানল বা কন্টেস্ট করার আগ্রহ আছে, তাদের প্রথমেই সকল হতাশা ঝেড়ে ফেলা উচিত। আর এমন একটা মনোভাব থাকা উচিত আমি পারবই। আর নিয়মিত প্র্যাকটিস। যেটা একটা ফরজ জিনিস কন্টেস্ট এর জন্য। তবে আমার ভার্সিটির অভিজ্ঞতা বলে নতুন যারাই আসে ভার্সিটির প্রথম সেমিস্টারে তারা কিভাবে কিভাবে যেন html css দিয়ে সাইট ডেভেলাপ করা যায় আর তা দিয়ে টাকা আর্জন করা যায় এমন একটা ধারনা পায়। আর পথে হাঁটতে গিয়ে বেশির ভাগ স্টুডেন্ট না শিখে প্রোগ্রামিং না হয় ভাল ডেভেলপার। প্রশ্নঃ tanvir002700.wordpress.com শুরু করার কথা কিভাবে ভাবলা , বাংলায় ব্লগ প্রোগ্রামিং নিয়ে খুব একটা নেই এখন যারা কনটেস্ট করে তাদের ব্লগিং কিভাবে তাদের হ্যাল্প করতে পারে , নতুন যারা ব্লগ লিখছে তাদের জন্য কোন সাজেশন ? উত্তর : tanvir002700.wordpress.com এইটা প্রথমে তেমন মহৎ চিন্তা নিয়ে শুরু করি নাই। প্রথম যখন python শেখা শুরু করি, দেখলাম যে আমরা কন্টেস্ট এ যেসব algorithm ব্যবহার করি সেইগুলা পাইথনে তেমন নেই, বা সহজে পাওয়া যায়। তারপর আমি কিছু algorithm পাইথনে লিখে ফেসবুকে একটা পোষ্ট আঁকারে দেই। ফেসবুক পোস্টে কোড দেয়া অনেক ঝামেলা। তারপর তখন মনে হল ব্লগে লিখি এইগুলা পরে আমি ভুলে গেলে নিজেও দেখতে পারব। তারপর ব্লগ খুলি। তারপর যখন শিপলু স্যারের কাছ থেকে suffix array শিখলাম তখন চিন্তা করলাম এই জিনিসত বাংলায় কোথায়ও ভাল রিসোর্স পাই নাই। এইটা সবার সাথে শেয়ার করি, নিজেও ভুলে গেলে আবার এইখান থেকে দেখে নেয়া যাবে আর অন্যরাও একটু হেল্প পাবে। এইভাবেই ব্লগ লেখা শুরু। যারা নতুন নতুন ব্লগ লেখছ, তাদের জন্য একটা উপদেশ প্রথম প্রথম হয়ত অনেকের কাছ থেকে অনেক কথা শুনবা। অনেকে হয়ত বলবে ফেমাস হওয়ার জন্য করছ। (আমি যে প্রবলেম ফেস করেছিলাম আরকি ) এইসব কান না দিয়ে নিজের মত করে লিখে যাও, কেউ কমেন্টে কোন সাজেশন দিয়ে সেইগুলা গ্রহণ করে লেখা উন্নত কর। জ্ঞান সবার মাঝে ছড়িয়ে দেয়ায় ক্ষতির কিছু নেই। প্রশ্নঃ Quora , Codefight এইসবগুলাতেও তুমি অনেক একটিভ । বাংলাদেশ এর এখনও এইসব সাইট এতটা জনপ্রিয়তা পায় নাই , এইগুলো তোমাকে কোন হ্যাল্প করতেছে ? উত্তরঃ Quora নিয়ে তেমন বিশেষ কিছু বলার নেই। খুব সম্প্রতি Quora তে একটিভ আমি। বাসায় বেকার বসে আছিতো, তাই অলস সময় একটু ইফেকটিভ কিছু করে কাটানোর একটা ছোট চেষ্টা মাত্র।
tongue emoticon আর Codefight, হ্যাঁ এই জিনিসটা আমার কোডের ডিবাগিং এবিলিটি অনেক বাড়িয়ে দিয়েছে। তবে মাঝে দিয়ে এই জিনিসের চরম নেশায় পড়ে গিয়েছিলাম। কোডফাইটের কয়েন দিয়ে টি-শার্ট কেনা যায় সেই টি-শার্টের লোভে সারাদিন ফাইট দিতাম। tongue emoticon তবে Codefight অনেক ভাল একটা জিনিস, যারা সারাদিন ক্ল্যাশ অফ ক্ল্যানে এটাক দাও তারা কিছুদিন Codefight এ ফাইট দিয়ে দেখতে পার, কোডিং ভাল লাগলে এই জিনিসের নেশায় পরে যাবা। আর এই জিনিস রিটার্নে তোমাকে ডিবাগিং এর কিছু এবিলিটি দিবে যেটা হয়ত অন্য গেম দেয় না। সব মিলিয়ে আমার কাছে খুবই ভাল একটা সাইট। প্রশ্নঃ অনেকেই ভার্সিটি লাইফে প্রোগ্রামিং কনটেস্ট এর চেয়ে freelancing এ জোর দেয় অনেক , এইটা আমি খারাপ বলছি না , এতে অনেক টাকাও পাওয়া যায় কিন্ত্ শিখার টাইমটা অনেক নস্ট হয় , এই ব্যাপারে তুমি কি বলবা ? উত্তরঃ freelancing!!! এই ব্যাপারে আমার মতামত খুবই নেগিটিভ। আমার ভার্সিটে দেখা অভিজ্ঞতা যদি বলি, বেশিরভাগ স্টুডেন্ট প্রথমেই সিএসইতে ভর্তি হয়ে যে জিনিসটা যানে সেইটা হল freelancing নামে একটা জিনিস আছে যেটা দিয়ে অর্থ উপার্জন করা যায়। সেই জিনিসের সুবাধে বেশিরভাগ স্টুডেন্ট ভার্সিটির প্রথম সেমিস্টার থেকেই হালকা html css শিখে টাকা কামায়ের ধান্দায় পরে যায়। এইভাবে করে দেখা যায় সে প্রোগ্রামিং এর বেসিক জিনিস ও এ্যালগরিদম ডাটাস্ট্রাকচার এইগুলা কিছুই শেখে না। সুতরাং আমার তবে freelancing করতে হলে ভার্সিটির প্রথম ৩ বছর নয়। ভার্সিটির প্রথম ৩ বছর শুধু cse রিলেটেড জিনিস পত্র শেখায় সময় দেয়া উচিত। প্রশ্নঃ প্রোগ্রামিং কনটেস্ট এ ইন্সপারেশন এর কেউ আছে , কাউকে ফলো করতে ? উত্তরঃ প্রোগ্রামিং কন্টেস্ট এর ইন্সপারেশন হল শিপলু স্যার। আমার ৪ বছরের পুরাটা সময় ধরতে গেলে স্যারের হাত ধরে চলতে শেখা। প্রোগ্রামিং কন্টেস্ট এর বেশিরভাগ জিনিস শিখেছি স্যারের কাছ থেকে। আর সবসময় স্যারকে ফলো করার চেষ্টা করতাম। স্যারের একটা জিনিস ভাল লাগে সেইটা হল কত স্টুপিডের মত কত উল্টাপাল্টা কাজ করেছি, কোনদিন বকা দেয় নাই:P :P প্রশ্নঃ নতুন যারা কনটেস্ট শুরু করতেছে তাদের কোন সাজেশন ? কিভাবে ভাল করবে ? উত্তরঃ যারা নতুন কন্টেস্ট করতেছে, তাদের জন্য সাজেশন হল লেগে থাক। প্র্যাকটিস বন্ধ করিও না, সফলতা আসবেই। প্রশ্নঃ অনেক সময় দেখা যায় কয়েকদিন কারো কনটেস্ট ভাল না হইলে অনেক এ হতাশ হয়ে কনটেস্ট ছেড়ে দেয় বা অন্যভাবেও বলা হয় সব কনটেস্টেন এর লাইফে হতাশার একটা পিরিয়ড থাকে , এই সময় কিভাবে নিজেকে মোটিভেট করা উচিত ? উত্তরঃ কন্টেস্ট ভাল না হওয়া/ আমি যেটাকে বাঁশ বলি tongue emoticon tongue emoticon:P সেইটা কি জিনিস আমার cf আইডি দেখলে বুঝা যায়। তারপর এত এত বাঁশ খাওয়ার পরেও কন্টেস্ট করা বন্ধ করি নাই। হতাশ হওয়া যাবে না। হতাশ হলে উল্টো বিপদ। হতাশ হলে পার্ফমেন্স দিন দিন আরও খারাপ হতে থাকে। যদি কোন কন্টেস্ট খারাপ হয় সেইটায় কি ভুল করেছ, বা যেগুলা সল্ভ হয় নাই সেইগুলা সল্ভ করার চেষ্টা কর। শিপলু স্যার সব সময় একটা কথা বলতেন আমি যখন cf শুরু করি, র‍্যাঙ্ক লিস্ট দেখ না, কন্টেস্ট শেষে তোমার লেভেলের যেসব প্রবলেম ছিল সেইগুলা সল্ভ করতে পেরেছ কিনা সেইটা দেখ। আর আমার মতে একটা অনেক গুলা অনলাইন কন্টেস্ট খারাপ হওয়া মানে, অফলাইন প্র্যাকটিসের অভাব। সুতরাং হতাশ হয়ে কন্টেস্ট অফ করে দিয়ে সেলেন্ডার করার চেয়ে, ভুল খুঁজে বের করে কাম ব্যাক করাই বুদ্ধিমানের কাজ। প্রশ্নঃ প্রোগ্রামিং বাদে কোন হবি ? ফ্রি টাইমে কি কর ? উত্তরঃ প্রোগ্রামিং বাদে আর যদি শখের কিছু থেকে থাকে সেইটা হল সাইক্লিং করা :P tongue emotico আর অবসর সময় দেখা যায় কখনও কোন ব্লগ/বই পড়ি অথবা টিভি সিরিজ দেখি।

Greedy Part - 3

greedy Algorithm এর উপর লিখা আমার আগের  পোষ্টগুলা এই লিঙ্ক এ পাওয়া যাবে ।

এই post এও কিছু interesting greedy problem নিয়ে  আলোচনা করর ।


Eternal Victory ::

এই প্রবলেমটাতে আসলে যা বলা হইছে আমাদের একটা ট্রি দেওয়া আছে (বিভিন্ন সিটি নিজেদের মধ্যে কনেক্টেড হয়ে ট্রি করছে ) । এই ট্রি এর সবগুলো নোডে আমরা মিনিমাম কত cost এ visit করতে পারি । আমরা ১ নাম্বার নোড থেকে যাত্রা স্টার্ট করব এবং যেকোন নোড এই থামতে পারব ।

যেহেতু এইটা ট্রি এর মানে হইল আমাদের কোন লুপ নেই । লুপ না থাকার কারণে আমরা জানি যে যেকোন একটা লিফ নোড এ আমরা থামব এবং  এইখানে কতগুলো রাস্তা আমাদের দুইবার যাতায়াত করতে হবে । যেহেতু আমরা সব থেকে মিনিমাম cost বের করছি আমরা চাব ১ নাম্বার নোড থেকে এর সব থেকে দুরের নোডে যেতে যে যে রাস্তা দিয়ে যাইতে হয় তারা যেন একবারই ভিজিট হয় আর বাকি সব নোড হবে দুইবার করে ।




ReplacingDigit ::
টপ কোডারের এই প্রবলেম এ বলা হয়েছে আমাদের কিছু product এর প্রাইজ ট্যাগ দেওয়া হবে এবং সাথে কিছু এক্সট্রা ডিজিট ও দেওয়া হবে আমারা চাইলে আমাদের কোন প্রোডাক্টের প্রাইজ ট্যাগর কোন ডিজিটকে বদলাতে পারি কিন্ত্ আমাদের কোন এক্সট্রা ডিজিট আমরা আমাদের প্রোডাক্টের প্রাইজ ট্যাগর সাথে যোগ করতে পারব না ।আমাদেরকে বলতে হবে হাইস্ট কত আমরা এই প্রোডাক্টগুলো থেকে পেতে পারি । লিমিট এ একটা জিনিস বলা আছে হাইস্ট 10^6 প্রোডাক্টের প্রাইজ হতে পারে ।
যদি ধরে নেই আমরা গ্রিডি সল্ভ করব তাহলে গ্রিডি সলুশ্যন এর সব থেকে গুরুত্বপূর্ণ পয়েন্ট হচ্ছে current stage এর highest possible gain । কি কি ফ্যাক্টর তা আমাদের দিবে এইটা আমাদের বের করতে হবে ।

১। most right digit থেকে আমরা দেখব আমরা কোন নাম্বার চ্যাঞ্জ করে বেশি লাভ করতে পারি কিনা ।
২। যদি পারি তাহলে সবথেকে smallest most right digit কে আমরা all possible extra digit থেকে highest possible value digit দ্বারা replace করব যা আমাদের highest profit ensure করবে ।
৩। একই প্রসেস আমরা সব ডিজিট এর জন্য ব্যাবহার করব ।

এখন আমাদের এই ব্যাপারগুলাকে  একসাথে merge করে answer বের করতে হবে ।




To Add or Not to Add::
কোডফরসেস এর এই প্রবলেম এ বলা হয়েছে আমাদের একটা N সংখ্যক number এর array দেওয়া আছে এবং সাথে একটা নাম্বার K ও দেওয়া আছে । K এর কাজ হল , আমরা K সংখ্যকবার চাইলে array এর কিছু element ( যদি খালি একটাও হয় ) ১ করে বাড়াতে পারি । আমাদেরকে এই array থেকে highest frequency এর নাম্বার প্রিন্ট করতে হবে , যদি একাধিক থাকে তাওলে সবচেয়ে ছোট নাম্বার প্রিন্ট করতে হবে ।

এই প্রবলেমটা অনেকভাবে সল্ভ করা যেতে পারে  এর মধ্যে two pointer technique use করে আমরা খুব সহজে করতে পারি ( two pointer technique কি এইটা জানা থাকলে এই ব্লগটা আগে পড়ে আসতে হবে ) । এরপর range এর মধ্যে commutative sum এর মাধ্যমে কোন নাম্বার এর জন্য হাইস্ট কতবার নাম্বারটা হতে পারে তা আমরা বের করতে পারি ।

প্রথমে আমরা sort করে নিব array টাকে , sort করাটা important কারন আমরা এর উপর range উপর কোন নাম্বার নিয়ে তা কতটা বানানো সম্ভব query করব , যা শুধু মাত্র একটা নাম্বার বানানোর জন্য এর সমান এবং সামান্য ছোট নাম্বারগুলাকে এর সমান বানাতে minimum কতটা adding দরকার হবে যা sorting sequence থেকেই আমরা পাই ।



two pointer এর মাধ্যমে প্রবলেম সল্ভ এর জন্য আমাদের দুইটা range পয়েন্ট থাকে , starting point and end point . আমরা যেহেতু iterative করে array এর প্রতিটি ভ্যালু নিয়ে দেখছি আমাদের উপরের কোডের 'i' হচ্ছে end point এবং 'p' হচ্ছে আমাদের starting পয়েন্ট । এখন p পয়েন্ট থেকে i পয়েন্ট পর্যন্ত যে নাম্বারগুলা আছে তাদের যদি আমরা 'i' পয়েন্ট এ যে নাম্বারটার সমান করতে চাই তাহলে যতবার adding operation লাগবে তা K( কোডে m ) এর ছোট বা সমান হচ্ছে কিনা তা 26 number লাইনের while loop দিয়ে চেক করা হচ্ছে , পরে answer update করা যায় কিনা check করা হচ্ছে ।

উপরের কোডের একটা মাত্র সাইন চ্যাঞ্জ করলে তা minimum number থেকে maximum number পাওয়া যাবে highest frequency এর জন্য , কোন সাইনটা চ্যাঞ্জ করতে হবে তা পাঠকদের খুঁজে বের করার জন্য ছেড়ে দিলাম ।

এই লিখাটা আর বড় করছি না , আমার মনে হয় প্রোগ্রামিং কনটেস্ট এ আগ্রহ থাকার পরও প্রোগ্রামিং কনটেস্ট এ অনেক এর ভাল করা সম্ভব হয় না quality problem solve না করার কারনে । ১০০টা same logic এর প্রবলেম সল্ভ করে যে লাভ টা হয় না , তার চেয়ে ৫টা different logic এর প্রবলেম সল্ভ করে অনেক কিছু জানা হয় । এখন একজনের পক্ষে হয়তো এই ৫টা different problem এর আইডি জানা কস্টকর , যে কাজটা একজন কোচ হয়তো করে দেন বা কোন সিনিয়র বড় ভাই ভার্সিটির যিনি নিজে অনেক টাইম দিছেন এইসব এর পিছনে । ভাল প্রবলেম এর আইডি মনে রাখা এমন মাঝে মধ্যেই এই প্রবলেম গুলার সল্যুশন লজিক দেখা important . যেইটা আমি নিজে অনেক পরে বুঝেছি বলে এখনও মাঝে মধ্যে আফসোস হয় । সব ভার্সিটির ট্রেনিং প্রসেস এক হওয়া সম্ভব না , এখন আমারা যারা নিজেরা সাফার করছি বা করিও নেই ( অনেক ভাল যারা করেছেন এবং করছেন ) তাদের দায়িত্ব হল এই প্রবলেম গুলার আইডিয়া বলে দেওয়া , সম্ভব হলে কিছু সল্ভ লজিক সহ যেন অন্য যে কেউ তা থেকে নিজে নিজে একটা শিখতে পারে । চীনা এবং রাশিয়ানরা কেন প্রোগ্রামিং কনটেস্ট এ এত ভাল করে তা একটা ভাল কারন ট্রেনিং ম্যাটেরিয়াল নিজেদের ভাষায় অনেক বেশি তাদের , যেইটা এখনও বাংলাতে নেই । যদি আমি গত ৪ বছর যাবত অনেক চ্যাঞ্জ দেখছি , আমি যখন স্টার্ট করি এক ফাহিম ভাইয়া এর ব্লগ বাদে কিছু ছিল না , পরে সাফায়াত ভাইয়া এখন প্রায় ব্যাসিক সব কিছু নিয়ে লিখে ফেলেছেন কিন্ত্ এখনো প্রবলেম ম্যাটেরিয়াল নিয়ে সবাই আগ্রহী না । আমার ব্লগের মাধ্যমে কারো কোন উপকার হইতে এইটা অনুরোধ থাকবে আপনিও বাংলাতে প্রবলেম সল্ভিং নিয়ে লিখা শুরু করুন । ইনশাল্লাহ আইওআই এবং এসিএম এর গোল্ড খুব একটা বেশি দূরে নয় :) 

LIS and variation

LIS ( Longest Increasing Subsequence ) যখন আমাদের কোন লিস্ট দেওয়া হবে যার numerical value আছে প্রতিটা element এর এবং  এই লিস্ট থেকে আমাদের এমন একটা সাব লিস্ট নিতে হবে যেই সাব লিস্ট sequentially increasing order এ হবে ,  যদি আমরা এমন একটা সাব লিস্ট নেই যেইটার length আমাদের all possible chosen sub list এর মধ্যে বৃহত্তর তাহলে সেই সাব লিস্টটাকে LIS বলে । যদি উদারণ দেই , ( 3 , 4 , 1 , 8) যদি আমাদের লিস্ট হয় তাহলে { 3 } , { 4 } , { 1 } , { 8 } , { 3 , 4 } , { 4 , 8 } , { 1 , 8 } , { 3 , 4 , 8 } এইগুলো আমাদের all possible sub list যা increasing order এ আছে এদের মধ্যে { 3 , 4 , 8 } এই লিস্ট এর length সবথেকে বৃহত্তর তাই এইটা আমাদের LIS ।

LIS বের করার জন্য যেহেতু একটা single element এর value ( LIS length ) তার আগের element গুলার উপর নির্ভর করে , LIS কে তাই dynamic programming algorithm ( DP ) বলা যায় । আমার কাছে LIS সবথেকে সহজতর (বুঝার জন্য) ডায়নামিক প্রোগ্রামিং আল্গরিথম । তবে প্রোগ্রামিং কনটেস্ট এ খুব কমই আমরা সরাসরি কোন প্রবলেম পাব যেখানে খালি LIS বের করতে  বলছে । আমাদের অনেক প্রবলেম সল্ভ করতে হবে যেখানে দৃশ্যমান বা অদৃশ্যমান LIS লুকাইয়া থাকবে । এই লিখাটার উদ্দেশ্য হচ্ছে LIS এর সব ধরণের ভ্যারিয়েশন এর একটা প্রাথমিক ধারণা তুলে ধরা ।  

LIS এর সব থেকে naive solution হচ্ছে O(n^2) । আমরা যদি LIS বের করতে চাই প্রাথমিক ভাবে সব element এর LIS length 1 দিব , তারপর iterate করে current element এর অবস্থান থেকে এর আগের সব element এর মধ্যে দেখব কোন element টা আমাদের current element থেকে ছোট বা সমান ( ক্ষেত্রে বিশেষ এ , অনেক সময় বলাই থাকে কোন duplicate element থাকবে না  ) যদি এমন কোন element পাই তাহলে check করে দেখব আমাদের current element এর LIS ভ্যালু আপডেট করা যায় কিনা , এইভাবে আমারা সব element এর LIS ভ্যালু পেয়ে যাব এদের মধ্যে যার ভ্যালু ম্যাক্সিমাম এইটাই আমাদের LIS ।





অনেক ক্ষেত্রেই O(n^2) solution আমাদের জন্য খুব একটা ফলপ্রসূ নাও হতে পারে যদি দেখা যায় আমাদের 10^5 or 10^6 সংখ্যক element এর জন্য LIS বের করতে বলা হচ্ছে তাহলে আমাদের টাইম লিমিট দেখে আরো better কিভাবে আমরা LIS  পাব তা নিয়ে ভাবতে হবে। LIS এর একটা ছোট এবং ফাস্ট একটা সলুশ্যন হচ্ছে C++ এর বিল্ট ইন set ব্যাবহার করে nlg(n) এ সল্ভ করা । তবে এইখানে বলে রাখা ভাল যদি আমরা যদি set use করি তাহলে এইখানে duplicate কোন ভ্যালু LIS এ থাকবে না ।



আমরা একটা উদারন দিয়ে বুঝতে পারি এইটা কিভাবে কাজ করে । ধরি { ১ , ৩ , ২ , ৪ } হচ্ছে আমাদের প্রাথমিক লিস্ট । স্বাভাবিকভাবে আমরা প্রথম element থেকে সামনে আগাবো । প্রথমে আমরা ১ আমাদের সেট এ পুশ করি , তাহলে set এর length হচ্ছে ১ । যদি তা একটা নরমাল array এর সাথে compare করি ( 0 index starting ) তাহলে LIS নামক array এর 0 index এ আছে ১ , এবং যখন আমরা find operation টা করছি  এর মাধ্যমে আসলে আমরা ১ যেখানে আছে এর index খুঁজে বের করছি । যেহেতু ১ এখন ০ নাম্বার ইনডেক্স এ আছে তাই আমরা it value এখন ০ পাব , এখন যদি  এর ভ্যালু ১ বাড়িয়ে দেখি ১ নাম্বার ইনডেক্স এর কোন অস্তিত্ব LIS array তে নাই বা ১ এই হচ্ছে আমাদের সর্বশেষ ভ্যালু যদি আমরা ১ পর্যন্ত প্রাপ্ত সব ভ্যালুকে sorted আকারে দেখি । তারপর ৩ set এ insert করার পরও আমরা একই অবস্থা পাব । তখন { ১ , ৩ } হবে আমাদের set array । কিন্তু যেহেতু set এ সর্ট আকারে সব ভ্যালু থাকে যখন ২ insert হবে আমাদের set array হবে { ১ , ২ , ৩ } এখন যখন আমরা find দিয়ে ২ এর অবস্থান খুজব আমরা পাব ১ নাম্বার ইনডেক্স এবং এর থেকে ১ পজিশন বাড়িয়ে দেখলাম যেমন এখন ২ , ২ নাম্বার ইনডেক্স এর অস্তিত্ব আছে , যাতে আছে ৩ । এর মাধ্যমে আমরা বুঝি আমরা এমন কোন কিছু পেয়েছি যেটার মাধ্যমে আমাদের set array এর length বেড়েছে কিন্তু element টা শেষ পজিশনে আসেনি । অর্থাৎ আমাদের প্রাপ্ত LIS হয়তো আপডেট হবে না কিন্তু এর একটা পজিশনে আমারা কম value এর কিছু insert করতে পারি যা পারে হয়তো আমাদের জন্য পরে লাভবান হতে পারে , তাই আমরা ৩ রিমুভ করে দিব । ফলে set array হবে { ১ , ২ } , এরপর যখন ৪ insert হবে আমাদের set array হয়ে যাবে { ১ , ২ , ৪ } । এইখানে ৩ রিমুভ যদি নাও করতাম তাহলেও তো অনেক এর কাছে লাগতে পারে { ১ , ৩ , ৪ } এমন কিছু পাইতাম যা লেংথ ও ৩ যা এই লিস্ট এর জন্য হাইস্ট । কিন্তু যদি আমাদের লাস্ট element , ৪ না হয়ে ৩ হত তাহলে ??? তাহলে কিন্ত ৩ এর পর কোন আপডেট লেংথ পেতে পাইতাম না , তাই যখনই কোন পজিশনের জন্য আপডেট ভ্যালু পাওয়া যাবে আপডেট করাটা জরুরী ।

এইভাবে কোড অনেক ছোট হচ্ছে কিন্তু একটা প্রবলেম থেকে যায় এইখানে duplicate ভ্যালু allow না । অনেক এর মনে হতে পারে তাওলে আমরা multiset use করব । আইডিয়া ঠিক আছে multiset duplicate value allow করলেও কিন্তু find আসলে lower_bound হিসাবে কাজ করে যখনই কোন duplicate value পাবে তার পজিশন এর জন্য ঠিক ভাবে কাজ করবে না ।  আমাদের তাই upper_bound ব্যাবহার করতে হবে find এর বদলে । multiset এবং সাথে upper_bound করে আমরা duplicate value এর জন্যও LIS পেয়ে যেতে পারি ।

এখন আমরা LIS দ্বারা কিছু ইন্টারেস্টিং প্রবলেম এর সলুশ্যন ট্যাকনিক দেখব ।

LIS দিয়ে আমরা classical DP problem LCS সল্ভ করতে পারি এবং মজার ব্যাপার হচ্ছে better time limit এ । একটা প্রবলেম দিয়ে দেখি এইটা ।

XMEN
প্রবলেমটাতে আমাদের আমাদের একটা লিমিট N দেওয়া হবে এবং ( 1 - N ) পর্যন্ত দুইটা list দেওয়া হবে এদের মধ্যে থেকে আমাদের common longest sequence এর length বলতে হবে । classical LCS problem , কিন্তু লিস্ট length ( 10^5 )  পর্যন্ত হতে পারে এবং এর জন্য যদি আমারা LCS দিয়ে ট্রাই করি ( O(N^2) ) solution এর জন্য TLE পেয়ে যেতে পারি যা আমরা প্রায় nlg(n) এ LIS দিয়ে করে ফেলতে পারতাম । এই কাজের জন্য আমরা যেকোন একটা list কে base list ধরে ( 1 - N ) পর্যন্ত ভ্যালুর জন্য কিছু dummy value( serial number of that set ) সেট করব যার উপর আমরা যদি অপর লিস্ট এর উপর LIS করি তাহলে আমরা LCS পেয়ে যাব । ব্যাপারটা কিভাবে সম্ভব হবে আমারা একটা টেস্ট কেইজ দিয়ে দেখি । ধরে নিলাম আমাদের দুইটি sequence হচ্ছে { ৪ , ২ , ১ , ৩ } এবং অপরটা হচ্ছে { ১ , ৪  , ২ , ৩ } । যদি আমরা প্রথমটাকে আমাদের বেস ধরি তাহলে ,
৪ -> ১
২ -> ২
১ -> ৩
৩ -> ৪

যদি এই ভ্যালু গুলা দিয়ে সেকেন্ড লিস্টটা রিপ্লেস করি তাহলে { ১ , ৪ , ২ , ৩ } হয়ে যাবে { ৩ , ১ , ২ , ৪ } যার মধ্যে যদি LIS দেখি { ১ , ২ , ৪ } হচ্ছে আমাদের বৃহত্তর sequence যা { ৪ , ২ , ৩ } আমাদের LCS দুইটা sequence এর মধ্যে ।

এমন একটি প্রবলেম হচ্ছে 10635 - Prince and Princess ।

Looking for a Subsequence

এইটা অনেক ভাল একটা প্রবলেম LIS এর উপর । এইখানে আমাদের LIS sequence ও  print করতে হবে , যদি কোন কারনে টাই হয়ে যায় তাহলে আমারা সব সময় left পজিশন এর ভ্যালু নিব । টাই প্রিন্ট এর ব্যাপারটা যদি না থাকত তাহলে আমরা খুব সহজেই হয়তো stack বা list বা vector কোন কিছুতে ভ্যালুগুলো রেখে তা প্রিন্ট করে ফেলতে পারতাম । একটা মজার ব্যাপার দেখি যেকোন LIS sequnce এ যদি আমরা value invert করে দেই তা LDS হয়ে যায় ( Longest decreasing sequence ) যদি LDS কে reverse order represent করি তাহলে কিন্ত্ আমরা আমার LIS order পেয়ে যাই । এইটা একটা fact .যেমন মাইনাস মাইনাস গুন করলে আমরা পজিটিভ কিছু পাব । আমরা তাই reverse order এ LDS করব যা আমাদের প্রতিটা পজিশন এর জন্য LIS এর ভ্যালু দিবে ( অবশ্যই reverse order এ ) । যা থেকে খুব সহজেই আমরা আমাদের sequence print করতে পারি বা দেখতে পারি এমন কোন sequence possible কিনা ।

এই লিখাটা এইখানেই শেষ । কোন প্রশ্ন থাকলে কমেন্ট সেকশনে বা আমাকে সরারসি ফেসবুক , ইমেল এ যোগাযোগ করলেই হবে :)

Programming Interview with A Asif Khan Chowdhury

ইন্টারভিউ সিরিজের আগের লিখাগুলা এই লিঙ্কে পাওয়া যাবে । প্রোগ্রামিং কন্টেস্ট এর ব্যাপারে প্রথম কিভাবে জানছিলা মনে আছে ?

প্রোগ্রামিং কনটেস্টের ব্যাপারে শুনছি প্রথম রুয়েটে এসেই। কিন্তু প্রোগ্রামিং ল্যাংগুয়েজ ব্যবহার করে প্রবলেম সলভিং করার ব্যাপারটা জানছিলাম HSC এর প্রথম বর্ষেই। আমার একটা ফ্রেন্ড শুভর মাধ্যমে। সেই প্রথম আমাকে কম্পিউটার সায়েন্সের মজাটা বুঝিয়েছিলো। তার সাথে থেকেই বিভিন্ন ছোটখাটো প্রবলেম সলভ করছিলাম, যদিও তখন competitive programming এর বিশাল জগৎ সম্পর্কে কিছুই জানতাম না। DOS স্ক্রীনে C দিয়ে “Hello World” লিখেই বুঝতে পারছিলাম যে এটা নিয়েই পড়াশুনা করতে চাই।

প্রথম অনসাইট কনটেস্ট কথা মনে আছে ?

আসলে জীবনের প্রথম কনটেস্টই ছিলো ICPC. তখন রুয়েট থেকে আসার মত টীম ছিলো না খুব বেশি। তাই সুযোগ পেয়ে গেছিলাম। ওই সময় কনটেস্ট PC^2 এ হতো। মজার বিষয় হলো আমরা আগে কখনও PC^2 দেখিও না। অনেক সময় গেছিলো PC^2 এ সাবমিট কিভাবে করে সেটা বুঝতে। :D

প্রোগ্রামিং কনটেস্ট এ কোন মজার কোন স্মৃতি আছে যেইটা মনে করলে এখনো হাঁসি পায় ?

মজার একটা স্মৃতি ছিলো ICPC-2013 তে। ঢাবির শাফায়েত ভাইয়াদের টীম কনটেস্ট শেষ হওয়ার এক ঘন্টা আগে ৬ প্রবলেম সলভ করে সবার আগে ছিলো। ভাইয়া আমাদের সামনেই বসেছিলেন, আমি উনাকে উঠে দাড়িয়ে তখনই কংগ্রাচুলেট করা শুরু করছিলাম। ভাইয়া রীতিমত লজ্জায় পড়ে গেছিলেন এটা দেখে। কনটেস্ট শেষ হওয়ার পর দেখি ভাইয়াদের টীম আর একটা সলভ করতে পারে নাই, SUST_Attoprottoyee ৭ টা প্রবলেম সলভ করে চ্যাম্পিওন হয়েছিলো। কনটেস্ট শেষে শাফায়েত ভাই আমার দিকে একটা দৃষ্টি নিয়ে তাকিয়েছিলো সেটা দেখে খুব লজ্জায় পড়ছিলাম। তারপর ভাইয়ার সাথে লজ্জায় আর কখনও কথা বলতে পারি না। কথাগুলো মনে পড়লে এখনও খুব মজা (এবং লজ্জাও) পাই।

কি টাইপের প্রবলেম সল্ভ করতে বেশি  ভাল লাগে ?

DP এবং algorithmic প্রবলেম সলভ করতে খুব বেশি ভালো লাগে। তবে যেকোন টপিকেই নতুন কিছু শিখে ম্যারাথন দিয়ে প্রবলেম সলভ করতে পছন্দ করি।

কোন প্রবলেম সল্ভ এর সময় "Thinking Process" কি থাকে প্রবলেম পড়ার পর ?

শাহরিয়ার মঞ্জুর ভাইয়ের কাছ থেকে প্রবলেম সলভ করার একটা পদ্ধতি শিখছিলাম, LDC (Learn, Divide, Convert). Basically এই পদ্ধতির প্রথম ধাপে প্রবলেমটা ভাল ভাবে শেখা, testcases নিয়ে নড়াচড়া করে দেখা হয় কিভাবে সলুশন আসতেছে। দ্বিতীয় ধাপে প্রবলেমটাকে ছোট ছোট sub-problem এ ভাগ করা হয়। কোন একটা sub-problem যদি মনে হয় সলভ করার আইডিয়া নাই তাইলে প্রবলেম skip করা। তৃতীয় ধাপে আছে convert, এটার মানে হলো sub-problem গুলো known বিভিন্ন প্রবলেমের সাথে মিল রেখে step-by-step সলভ করার চেষ্টা করা।

কোন প্রবলেম Accepted না হলে কি কি ব্যাপার দেখেন ?    

কয়েকটা কাজ করে দেখি যেমন, প্রথমে type check করি, overflow হয় কিনা দেখি, constrains গুলো ভাল ভাবে চেক করি। যদি তাতেও কাজ না হয় তখন প্রবলেমটাতে খুটিনাটি বিষয়গুলো ঘেটে দেখি। তারপর brute force কোড করি তারপর random case এর জন্য brute force আর আমার সুলশনের সাথে মিলিয়ে পার্থক্যগুলো দেখি।

অনেক সময় দেখা যায় কয়েকদিন কারো কনটেস্ট ভাল না হইলে অনেক এ হতাশ হয়ে কনটেস্ট ছেড়ে দেয় বা অন্যভাবেও বলা হয় সব কনটেস্টেন এর লাইফে হতাশার একটা পিরিয়ড থাকে , এই সময় কিভাবে নিজেকে মোটিভেট করা উচিত ?

আমার পরিচিত এমন কোন প্রবলেম সলভার দেখি নাই যারা প্রবলেম সলভিং করতে গিয়ে মাঝপথে হতাশ হয় নাই। Competitive programming এবং হতাশা হাতে হাত রেখে চলে। এই সময় যারা ছেড়ে দিয়েছে তাদের অনেকের সাথে কথা বলে দেখেছি, সবারই একটাই মন্তব্য থাকে তারা এটা ছেড়ে দিয়ে ভুল কাজ করেছে, এই ব্যাপারটা মাথায় রাখলে মনে হয় মোটিভেটেড থাকা যাবে। আবার যারা ফলাফলের আশায় প্রবলেম সলভিং করে তারা আরও বেশি হতাশ হয়। প্রবলেম সলভিং ক্রিকেট-ফুটবল-টেবিল টেনিস ইত্যাদি খেলার মত করেই দেখা উচিৎ। তুমি মজা পাও বলে প্রবলেম সলভিং করো, রেজাল্টের আশায় না। :)

আইওআই যারা না করে ভার্সিটি থেকে কনটেস্ট করে তারা দেখা যায় আইওআই যারা করেছেন তাদের থেকে পিছাইয়া থাকে , অনেক সময়ই পিছাইয়াই থাকে । যারা ভার্সিটি তে মাত্র কনটেস্ট নিয়ে জানল তাদের কি করা উচিত এই দুরুত্ব কমানোর জন্য ?

এটা ঠিক যে তারা পিছিয়ে থাকে। তবে এই পিছিয়ে থাকাটা রিকভার যায় না এটা ভাবাটা ভুল হবে, শুধু dedication টা বেশি থাকতে হবে অন্যদের চেয়ে। বাংলাদেশের competitive programming এ যত কিংবদন্তি আছে তাদের সিংহভাগই তো IOI করেন নাই।

বাংলায় ব্লগ প্রোগ্রামিং নিয়ে খুব একটা নেই , আসিফের হজবরল কিভাবে শুরু করার চিন্তা করলা ? যারা কনটেস্ট করে তাদের ব্লগিং কিভাবে তাদের হ্যাল্প করতে পারে , নতুন যারা ব্লগ লিখছে তাদের জন্য কোন সাজেশন ?

প্রবলেম হলো আমি নতুন কিছু শিখলে সেটা অন্য কাওকে না জানায়ে থাকতে পারি না। :P রুয়েটে তখন খুব বেশি প্রবলেম সলভার ছিলো না এ সব বিষয়ে আলাপ-আলোচনা করার জন্য। তাই কিভাবে জানাবো কি শিখছি? তখন মাথায় আসলো ব্লগিং করার কথা। ব্লগিং করার শুরুটা করি শাফায়েত ভাই, জুবায়ের ভাই এবং ফাহিম ভাইয়ের  ব্লগপোস্টগুলো পড়ার পর। খুবই ভালো লাগতো লিখতে, এবং অন্যদের প্রশ্নের উত্তর দিতে। ব্লগিং করে অনেক ফ্রেন্ড পেয়েছি ভাল ভাল, শিখতে পারছি অনেক কিছু। :)

বাংলায় ভাল ব্লগের খুবই অভাব। তোমরা যারা ব্লগিং শুরু করছো তারা সব সময় মাথায় রেখো যে তোমরা হাতে গোণা কয়েকজন প্রোগ্রামারদের মধ্যে একজন যে নিজেদের জ্ঞান সবার মাঝে ছড়িয়ে দিতে প্রস্তুত আছো। সব থেকে বড় কথা তোমরা যে টপিক নিয়েই লিখ না কেন, লিখলে তোমার জ্ঞান সাধারনের চেয়ে অনেক বেশি বাড়বে কম সময়ে।

প্রোগ্রামিং কনটেস্ট এ ইন্সপারেশন এর কেউ আছে , কাউকে ফলো করতে ?

আমি মোটামুটি সবাইকেই, যারা প্রবলেম সলভ করতে পছন্দ করেন তাদেরকে, ইন্সপারেশন হিসেবে দেখি। তবে তালিকায় প্রথমে যারা আছেন তারা হলেন শান্ত ভাইয়া, শাহরিয়ার মঞ্জুর ভাইয়া, রুয়েটের সামাদ ভাইয়া (তাকে ছাড়া হয়তো আমরা কেও competitive programming জড়িত হইতেই পারতাম না), মইনুল শাওন, সাকিব, মারুফ, ধনঞ্জয়, শাকিল ( :) ), শাফায়েত ভাইয়া, জুবায়ের ভাইয়া, নাফিস এবং আরও অনেককেই।

নতুন যারা কনটেস্ট শুরু করতেছে তাদের কোন সাজেশন ? কিভাবে ভাল করবে ?

আসলে কনটেস্টে ভাল করার কোন শর্টকাট কেও দেখাতে মনে হয় পারবে না। প্রচুর প্রবলেম সলভ করতে হবে ভাল করতে হলে। অনেক টেকনিক আর অ্যালগরিদম শিখতে হবে। আর অবশ্যই যেটা মাথায় রাখতে হবে প্রবলেম সলভাররা অন্যদেরকে সাহায্য করতে সব সময় প্রস্তুত থাকে। একা একা কোন জিনিস শিখতে অনেক সময় লাগতে পারে, সেখানে যারা আরও বেশি এক্সপেরিয়েন্সড তাদের কাছ থেকে শিখে নিলে সময়টা অনেক কম লাগবে। এমনকি প্রবলেম সলভারদের জীবনে করা ভুলগুলো শুনলেও অনেক কিছু শিখতে পারবে, অনেক ভুল আগে থেকেই শুধরে নিতে পারবে। সুতরাং সব সময় শেখার জন্য open mind রাখা উচিৎ।

রুয়েট এর কনটেস্ট কালচার তৈরির জন্য অনেক কষ্ট করছ এবং করে যাচ্ছ। আগামী ২/৩ বছর পর রুয়েটকে কোথায় দেখতে চাও ?

রুয়েট থেকে অনেক কিছু পেয়েছি, শিখতে পারছি। স্বপ্ন ছিল একদিনের যেদিন দেখবো আমারই ছোট ভাইগুলো WF করতেছে। এই স্বপ্নের জন্য যতটুকু করতে পেরেছি ততটুকু করেছি। তবে আরও অনেক কিছু করার ইচ্ছা ছিলো যেগুলো করে যেতে পারি নাই।

রুয়েটের জুনিয়ররা এখন অনেক আগ্রহী কনটেস্ট করতে। এত বিশাল সংখ্যক কনটেস্টেন্ট রুয়েট কখনও দেখে নাই এর আগে। তাদের পরিশ্রম দেখে অনেক ভালই লাগে। ইনশা’আল্লাহ সামনে ১-২ বছরের মধ্যে অনেক ভাল একটা পজিশনে দেখতে পারবো রুয়েটকে। :)

প্রোগ্রামিং বাদে কোন হবি ? ফ্রি টাইমে কি করেন ? 

আমি প্রচুর মুভি আর টিভি সিরিজ দেখি ফাকা সময়ে। ইদানিং youtube এ মুভি ট্রেইলারস, টেক, সায়েন্স videos ইত্যাদি দেখে ফাকা সময় কাটাচ্ছি। :P