Competitive Programming

Competitive Programming এবং কিছু প্রশ্নের উত্তর

প্রথমেই বলে নেই যে, Competitive Programming এর ব্যাপারে বাংলাদেশ এই আমার চেয়ে ভাল suggestion দিতে পারবে এমন লোকের (শান্ত ভাই, ফরহাদ ভাই, জামি ভাই,মুস্তাফিয ভাই...) অভাব নেই । বাংলাদেশে খুব কম জায়গা আছে যেখানে আনন্দ এবং প্রতিযোগিতার মাধ্যমে শিক্ষালাভ করা যায়। ঠিক এই রকম একটা ক্ষেত্র হচ্ছে programming. Programming বলতে অনেকে software programming, web programming এসব বুঝলেও Competitive programming নামে একটা ভয়ংকর মজাদার বিষয় আছে তা অনেকেই জানে না, যা CSE পড়ার মজা অনেক গুন বাড়িয়ে দিতে পারে এ ব্যাপারে কোন সন্দেহ নেই। Competitive Programming কে অনেক ACM < code>(আমি নিজেও বলি :P)

বলেন। কিন্তু ACM আসলে একটা company এর নাম। এখানে আমি Competitive Programming বা সংক্ষেপে CP ব্যাবহার করব। আমি যা যা নিয়ে বলব তা হচ্ছে:

  • ১। Competitive programming(CP) কি?
  • ২। Contest কি?
  • ৩। Verdict কি?
  • ৪। CP কেন করব?
  • ৫। CP কারা করবে বা শুধু কি CSE student রা CP করবে?
  • ৬। সব বুঝলাম কিন্তু কিভাবে শুরু করব?
  • ৭। math জানা না থাকলে কি CP তে ভাল করা যায়?
  • ৮। ১০০/১৫০ টা করলাম, এবার কি?
  • ৯। Topcoder, Codeforces, Codechef কোনটা করব?
  • ১০। কত ঘণ্টা কাজ করব? একটা problem এ আটকালে কি করব?
১। Competitive programming(CP) কি?

Competitive programming হচ্ছে একটা মেধাভিত্তিক প্রতিযোগিতা । এখানে বিভিন্ন ধরনের সমস্যা দেয়া থাকে। এবং এসব সমস্যার সমধান করতে হয় Programming Language (C,C++,JAVA..) ব্যাবহার করে । এতে একজন programmer এর programming, algorithm, data structure, mathematical skill পরীক্ষা করা হয়। সবচেয়ে বড় কথা হল এখানে মুখস্ত করতে হয় না। প্রোগ্রামিং সমস্যাগুলো বিভিন্ন site (UVA,Lightoj, Codeforces,SPOJ) ইত্যাদিতে থাকে।

২। Contest কি?
Programming করেছে আর contest এর নাম শুনে নাই, এই রকম লোক নাই । contest এ নির্দিষ্ট সময় বেধে দেয়া হয় এবং কয়েকটা সমস্যা দেয়া হয় । লক্ষ্য থাকে যত কম penalty তে যত বেশি সংখ্যক সমস্যার সমাধান করা । contest ২ ধরনের হয়
  • ১। Online
  • ২। Onsite

নাম শুনেই বুঝা যায় একটা online এ হয় । আর আরেকটা একই জায়গায় lan এর মাধ্যমে হয় । onsite contest এর সময়সীমা সাধারণত ৫ ঘণ্টা । ৮ টা থেকে ১১ টা সমস্যা দেয়া থাকে। online contest এর সময় site অনুযায়ী বিভিন্ন হয়। Onsite contest সাধারনত team (তিন জনের) এ হয়। contest এর সবচেয়ে মজার জিনিস হচ্ছে ranklist. কোন team এর অবস্থা কি, বা কোন সমস্যা সমাধান হয়েছে তা rankilst দেখে বুঝা যায় । স্কুল, কলেজ পর্যায়ে আছে IOI । আর বিশ্ববিদ্যালয় পর্যায়ে সারা বছর জুড়েই বিভিন্ন contest হয়। বিভিন্ন university এসব arrange করে। তবে সবচেয়ে গুরুত্বপূর্ণ হচ্ছে ACM ICPC contest. এটা দুই ভাগে হয়। একটা হচ্ছে regional contest. আর সবচেয়ে বড়টা হচ্ছে World Finals. Regional এ সারা পৃথিবীকে অনেকগুলা region এ ভাগ করা হয়। এইসব region যে contest হয় তাকে regional contest বলে। regional গুলাতে ভাল করা team গুলা World Finals এ যায়। এটা অনেকটা football world cup এর মত । Bangladesh একটা region এর অন্তর্ভুক্ত, এটা হচ্ছে Dhaka regionalRegional গুলোতে foreign team আসে এবং dhaka regional তার ব্যতিক্রম নয় । IOI individual পর্যায়ে হয় । আর বিশ্ববিদ্যালয় পর্যায়ে contest, team এ হয়।

৩। Verdict কি?

একটা সমস্যা সমাধান করে কেও যদি তা submit করে । তাইলে judge বিভিন্ন মতামত পাঠান। যেমন accepted বা yes (একজন programmer এটার জন্য সব ত্যাগ করতে রাজি :P), wrong answer (ভুল হলে) , TLE বা Time Limit Exceeded (নির্দিষ্ট সময়সীমা এর চেয়ে বেশি সময় ধরে program run করলে ) এবং আর অনেক কিছু । এইসব মতামত কে verdict বলে । ভাল programmer রা অনেক সময় verdict দেখে program এর ভুল বের করতে পারে।

৪। CP কেন করব?

সত্য কথা হল যারা CP করে তারা মজা থেকেই করে। CP করলে ভাল job পাওয়া যায় বা career এর জন্য ভাল হয় শুধুমাত্র এসব চিন্তা করে যারা CP শুরু করে, তাদের আমি CP না করতে বলব। কারন, ultimately interest না থাকলে CP continue করা যায় না । আমার মতে মুলত ২ কারনে CP করা উচিত । প্রথমত Fun, যেটা আমি আগেই বলছি। একটা প্রবলেম solve না হওয়ার আগ পর্যন্ত যদি শান্তি না লাগে তখনি বুঝবা তুমি programmer হয়ে উঠছ । দ্বিতীয়তটা হচ্ছে Challenge, আমি personally যা দ্বারা বেশি motivated । এই জিনিসটা নিজেকে আর ভাল programmer করতে সাহায্য করে এটা একদম সত্য কথা । আরেকটা minor কারন আছে CPকরার যেটা শুধু মাত্র cse এর student দের জন্য খাটে । সেটা হচ্ছে academic লেখাপড়ায় CP সাহায্য করে। এছারা কেও যদি পরিবর্তীতে software বা অন্য line এ যায় তার জন্য CP সাহায্য করে। তবে শেষ দুই লাইন আমি সবার জন্য লিখি নাই।

৫। CP কারা করবে বা শুধু কি CSE student রা CP করবে?

CP, CSE student রা বেশি করে সেটাই সবাই দেখে আসছে। কিন্তু সত্য কথা হচ্ছে CP শুধুমাত্র CSE এর বিষয় না। এই বাংলাদেশে অনেক WorldFinalist (ওয়াসি ভাই, তাসনিম ইমরান সানি ভাই buet civil এর) আছে যারা অন্য department এর । এমনকি university তে শুরু করতে হবে এমন কথাও নাই। তোমার বাসায় যদি pc থাকে তাহলে তুমি স্কুল,কলেজ থেকেই শুরু করতে পার।

৬। সব বুঝলাম কিন্তু কিভাবে শুরু করব?

প্রথমেই বলে নেই, CP কিন্তু software development নয়। সুতরাং language expert হওয়ার দরকার নাই। মাত্র একটা language মোটামুটি ভাল ভাবে জানা থাকলেই হবে। সেক্ষেত্রে আমি বলব c++ (c,c++ এর সাবসেট) শিখতে । java জানা থাকলেও সমস্যা নাই। আমি শিখেছি Schaum's series এর বইটা থেকে। Herbert Schildt এর বই আছে। বাংলায় সুবিন ভাই এরও বইটা আছে । কেও যদি loop, structure ভাল করে পারে, তার কাজ হবে খুব দ্রুত ১০০-১৫০ টা problem solve করা। UVA আর lightoj এর অনেকগুলা সহজ সমস্যা আছে। সহজ গুলা দেখেই আগে solve করা উচিত। প্রথমে কঠিনে যাওয়ার দরকার নাই। একি সময় basic data structure (stack,queue), basic algorithm (bfs,dfs) দেখা যেতে পারে। schaum's series এর data structure বইটা ভাল। আর algorithm এর জন্য আছে cormen এর Introduction to Algortihm বইটা পড়া যায়। তবে অনেকের কাছে এটা কঠিন মনে হয়। net এ বই এর উপর MIT এর লেকচার আছে। তাছারা প্রত্যেকটা topic এর উপর অনেক content আছে । যে net থেকে search মেরে শিখতে পারে তার জন্য data structure, algorithm শিখা ব্যাপার না।

৭। math জানা না থাকলে কি CP তে ভাল করা যায়?

অনেকের মধ্যে এই ধারনা আছে যে math না জানলে CP তে ভাল করা যায় না। একটা minimum level এর math পারতে হয় সেটা ঠিক, কিন্তু math olympiad এর পোলাপানের (respect রেখেই বলছি :P) মত অনেক না জানলেও চলবে। সেই minimum লেভেল হচ্ছে HSC এর basic । শুধুমাত্র যেসব অঙ্ক পরিক্ষায় আসে সেসব করলে হবে না, বইএর কোন অংক বাদ দেয়া যাবে না। বিশেষ করে সমাবেশ-সন্নিবেশ, জ্যামিতি, calculus এর ধারনা CP এর চেয়ে আর কোথাও বেশি কাজে লাগে কি না আমার জানা নাই । এটা ছাড়া কেও যদি discrete math শেষ করে তাইলে অনেক ভাল। math olympiad লেভেলের combinatorics করা থাকলে আরও ভাল ।

৮। ১০০/১৫০ টা করলাম, এবার কি?

এবার কি কি type algorithm বাংলাদেশে আসে তা জানতে হবে। এক্ষেত্রে গত ২ বছর এ বিভিন্ন বাংলাদেশি contest আর lightoj এর category দেখলে ধারণা পাওয়া যাবে। একটা algorithm এর list করে তারপর সেগুলো solve করতে হবে। lightoj থেকে practice করা যেতে পারে। এখানের প্রবলেমগুলা standard আর বাংলাদেশ উপযোগী। আরেকটা বিষয় হচ্ছে এটা যেহেতু একটা team contest সেহেতু team এর বাকি সবাই একি রকম আগাচ্ছে কি না সেটা খেয়াল রাখতে হবে। এবং team এর মধ্যে যে understanding ভাল থাকতে হবে এটা না বল্লেও চলে। একটু advance রা emaxx এর site দেখতে পারে।

৯। Topcoder, Codeforces, Codechef কোনটা করব?

এটার কোন নির্দিষ্ট উত্তর নাই। যার যেটা ভাল লাগে সেটাই করা উচিত। তবে আমি ব্যাক্তিগত ভাবে ৩টা কে ৩ কারনে recommend করব। Topcoder ভাল dp+combinatorics, maths শেখার জন্য । codeforces ভাল graph, data structure এর জন্য, আর আমার কাছে মনে হয় codeforces এর প্রবলেমগুলো icpc standard। ইদানিং codechef জনপ্রিয় হয়ে উঠেছে। এইখানের problem অনেক বেশি standard হয়। অনেক বাংলাদেশি (tasnim imran sunny ভাই) প্রবলেমসেটার সেখানে প্রবলেম set করেন। সুতরাং দেশি বিদেশি সকলের প্রবলেম সেট এর pattern বুঝা যায়। এছাড়া প্রতিবছর একটা নির্দিষ্ট সময়ে google codejam., facebook hackercup, Topcoder open, IPSC ইত্যাদি contest অনুষ্ঠিত হয়।

১০। কত ঘণ্টা কাজ করব? একটা problem এ আটকালে কি করব?

কত ঘণ্টা কাজ করব তার নির্দিষ্ট হিসাব নাই। কেউ ঘণ্টা হিসেব করে কাজ করে। আব্র কেউ টানা কাজ করে আবার টানা বিশ্রাম নেয় । যেভাবেই কর না কেন নির্দিষ্ট একটা লক্ষ্য থাকতে হবে এবং একটা সময়সীমা থাকতে হবে। problem এ আটকালে কয়েকদিন পর এটা আবার try করতে পার। আমি একটা wrong answer folder রেখে দিসি। কয়েকদিন পর আবার try করি। তোমরাও করে দেখতে পার। আর নিজে debug করে একটা code submit করতে পারলে সবচেয়ে ভাল শেখা যায়। প্রথম দিকে একটু কষ্ট হলেও পরে এটা অভ্যাস হয়ে যায়।