পৃথিবীতে মানুষ দুই প্রকার, যারা প্রোগ্রামিং পারে এবং যারা প্রোগ্রামিং পারে না! ইংরেজি খুব ভালো না জেনেও জাপানিরা বা রাশিয়ানরা জ্ঞান-বিজ্ঞানে অনেক এগিয়ে আছে, কিন্তু প্রোগ্রামিং না জেনে কোনো জাতি অনেক এগিয়ে গেছে এরকম উদাহরণ সম্ভবত আধুনিক পৃথিবীতে একটিও খুজে পাওয়া যাবে না। জাতীয় হাইস্কুল প্রোগ্রামিং প্রতিযোগিতা(এনএইচপিসি) নিশ্চিতভাবেই বাংলাদেশের ইতিহাসে একটা মাইলফলক হতে চলেছে। গত কয়েক বছর ধরে ইনফরমেটিক্স অলিম্পিয়াড নিয়মিত আয়োজন করা হলেও অনেক সীমাবদ্ধতার কারণে সেটাকে ঢাকঢোল পিটিয়ে আয়োজন করা সম্ভব হয় নি। এবারের প্রতিযোগিতাটার পিছে সে তুলনা প্রস্তুতি অনেক বেশি, প্রচুর ছেলেমেয়ের কাছে এটার খবর পৌছে দেয়া সম্ভব হয়েছে, তাই আশা করা গণিত অলিম্পিয়াডের মত খুবই দারুণ একটা প্রতিযোগিতা হবে এটা।
হাই স্কুল প্রোগ্রামিং কনটেস্টের প্রস্তুতি নিয়ে কিছু কথা বলতে চাই। একটা সময় ছিল যখন আমাদের দেশে শুধুমাত্র বিশ্ববিদ্যালয়ে পড়া ছেলেমেয়েরা প্রোগ্রামিং করতো, স্কুল-কলেজের ছেলেমেয়ে ছিলো হাতেগোণা, এখন সে সংখ্যাটা অনেক বেড়েছে। অনেকেই হয়তো ১-২সপ্তাহ প্রোগ্রামিং শিখে প্রতিযোগীতায় অংশ নিতে চলে আসবে, তাদেরকে এধরণের প্রতিযোগিতার প্রশ্নের ধরণের সাথে কিছুটা পরিচয় করে দিতে চাই।
প্রস্তুতির প্রথম অংশ অবশ্যই প্রোগ্রামিং শেখা। এই প্রতিযোগীতায় সি/সি++ দিয়ে কোডিং করতে হবে। একদম শুন্য থেকে যারা শুরু করছে তাদের জন্য সি/সি++ শেখার দারুণ একটা রিসোর্স হতে পারে সুবিন ভাইয়ের কম্পিউটার প্রোগ্রামিং বইটা, বইটা অনলাইনে পড়তে পারো। যারা একটু গভীরে জানতে চাও তারা হার্ভার্ড শিল্ডের বইটা যোগাড় করে পড়ে ফেলতে পারো। প্রতিযোগীতার সমস্যাগুলো সমাধান করার জন্য লজিক, লুপ, অ্যারে, স্ট্রিং, ফাংশন এসব সম্পর্কে জানতে হবে। তুমি হয়তো বলতে পারো যে আমি জাভা, পিএইচপি, রুবি ইত্যাদি পারি, আমি কি করবো? আমাদের যুক্তি হলো প্রত্যেক প্রোগ্রামারের সি জানা উচিত, এবং সি জানলে অন্য সব ল্যাংগুয়েজ খুব সহজেই শেখা যায়।
প্রোগ্রামিং প্রতিযোগীতার উদ্দেশ্য কিন্তু শুধু তুমি প্রোগ্রামিং জানো কিনা সেটা যাচাই করা না, তুমি যুক্তি দিয়ে সমস্যা সমাধানে কতটা দক্ষ সেইটাই এখানে আসল। বড় বড় প্রোগ্রামাররা ৭০-৮০% সময় চেয়ারে বসে চিন্তা করে বা সাদাবোর্ডের দাগাদাগি করে আর বাকি ২০-৩০% সময় কিবোর্ডে কোডিং করে। তাই কোনো প্রোগ্রামারকে যদি দেখো দিনরাত উদাস হয়ে কি যেন ভাবছে কিন্তু কম্পিউটার ধরছে খুব কম, তাতে অবাক হবার কিছু নাই!
সমস্যাগুলোর ধরণের সাথে পরিচিত হতে আমরা এখন একটা সমস্যা সমাধান করবো। প্রথমে সমস্যাটার সহজ ভার্সন, এরপর একটু কঠিন ভার্সন দেখবো। সমস্যাটি হলো এরকম:
সমস্যার বর্ণনা (Problem description):
দুটি সংখ্যা B এবং E দেয়া আছে। তোমাকে B থেকে E পর্যন্ত সবগুলো সংখ্যার যোগফল বলতে হবে।
এটা হলো মূল সমস্যাটার বর্ণনা। এরপর তোমাকে ইনপুট ফরমেট দেয়া থাকবে। বেশিভাগ সময়ে ইনপুটে শুরুতে কয়টা টেস্ট-কেস সমাধান করতে হবে বলা থাকে, এরপর প্রতিটা টেস্টকেসে বর্ণনা থাকে। এই সমস্যাটির ক্ষেত্রে ইনপুট ফরমেট হতে পারে এরকম:
ইনপুট ফরমেট:
প্রথম লাইনে একটি সংখ্যা T দেয়া থাকবে যেটা টেস্ট কেস সংখ্যা নির্দেশ করে। এরপর T সংখ্যক লাইন থাকবে, প্রতি লাইনে দুটি সংখ্যা B এবং E দেয়া থাকবে।
বিচারকদের কাছে একটি ইনপুট ফাইল থাকে যেটা দিয়ে তোমার কোড পরীক্ষা করা হয়। সেই ইনপুট ফাইলের বর্ণনাই এখানে দেয়া হয়েছে। এরপরে তোমাকে আউটপুট ফরমেট দেয়া থাকবে।
আউটপুট ফরমেট:
প্রতিটা টেস্টকেস এর জন্য তোমাকে টেস্টকেস নম্বর এবং ফলাফল প্রিন্ট করতে হবে। নমুনা আউটপুট দেখো।
বিচারকরা তাদের ইনপুট ফাইল এবং তোমার কোড ব্যবহার করে একটা আউটপুট ফাইল তৈরি করবেন। তারপর নিজেদের সমাধান ফাইলের সাথে তোমারটা মিলিয়ে দেখবে। তোমাকে একদম ঠিকঠাক মত আউটপুট ফরমেট মেনে চলতে হবে, ভুল ফরমেটে সঠিক আউটপুট প্রিন্ট করলেও বিচারক বলবে ‘Wrong answer’। কিছু নমুনা ইনপুট-আউটপুটও দেয়া থাকবে:
নমুনা ইনপুট(Sample Input):
3
1 3
10 15
20 23
নমুনা আউটপুট(Sample Output):
Case 1: 6
Case 2: 75
Case 3: 86
নমুনা গুলো দেয়া থাকবে যাতে তুমি বিচারকদের ইনপুট-আউটপুট ফাইল কিরকম সেটা বুঝতে পারো এবং সাবমিট করার আগে তোমার কোড পরীক্ষা করে দেখতে পারো।
আরেকটু খুবই গুরুত্বপূর্ণ অংশ হলো ইনপুট সীমা এবং টাইম লিমিট। এই সমস্যার ক্ষেত্রে সেগুলো এরকম:
Time limit: 2 seconds
1<=T<=1000
1<=B<=E<=100
এটার মানে হলো তোমার কোডকে ২সেকেন্ডের ভিতর ফলাফল দিতে হবে। এবং টেস্টকেস থাকবে সর্বোচ্চ ১০০টা, B আর E এর মান ১ থেকে ১০০ এর মধ্যে থাকবে। আমরা প্রতি কেস এর জন্য যদি লুপ চালিয়ে যোগ করি তাহলে সমাধানটি হতে পারে এরকম:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <cstdio> using namespace std; int main() { int t; scanf("%d",&t); for(int case_no=1; case_no<=t;case_no++) { int B,E; scanf("%d",&B); scanf("%d",&E); int ans=0; for(int i=B;i<=E;i++) { ans+=i; } printf("Case %d: %d\n",case_no,ans); } return 0; } |
কিভাবে বুঝবো কোডটা ২ সেকেন্ডে কাজ করবে নাকি? টেস্ট কেস সংখ্যা সর্বোচ্চ ১০০০টা, এবং ভিতরে B থেকে E পর্যন্ত যে লুপটি চালিয়েছি সেই লুপটা প্রতি কেসে সর্বোচ্চ ১০০বার ঘুরতে পারে। তারমানে ইনপুট ফাইল বিচারক যতই বাজে করে বানাক, মোটামুটি ১০০০×১০০ টা ধাপে তোমার কোড সব টেস্টকেসের ফলাফল দিতে পারবে। বর্তমানের বিচারক কম্পিউটারগুলো প্রতি সেকেন্ডে মোটামুটি ১০০০০০০০০ বা ১০^৮টি ধাপ সম্পন্ন করতে পারে, এটা নির্দিষ্ট কোনো সংখ্যা নয়, কম্পিউটারের কনফিগারেশন অনুযায়ী কম-বেশি হতে পারে। তারমানে খুব সহজেই তোমার কোড ২ সেকেন্ডের ভিতর কাজ করবে!
কোড সাবমিট করার আগে অবশ্যই সবথেকে বড় এবং সবথেকে ছোট কেসগুলো দিয়ে তোমার কোড পরীক্ষা করে দেখবে। এগুলোকে প্রোগ্রামাররা কর্নার কেস বলে থাকে, অনেক সময়ই দেখা যায় কর্নার কেসই wrong answer পাবার কারণ। এই প্রবলেমে একটা কর্ণার কেস হতে পারে B=E। বিচারকরা সবধরনের কেস দিয়ে তোমার কোড পরীক্ষা করবেন, তাই সঠিক কোড না লিখলে ধরা খেতেই হবে।
এখন ইনপুট সীমা যদি নিচের মতো হতো তাহলে কি ঘটতো:
Time limit: 2 seconds
1<=T<=100000
1<=B<=E<=100000
এবার কিন্তু আগের কোডে ফলাফল আসতে ১০০০০০×১০০০০০ বা ১০^১০ ধাপ দরকার হবে। সেকেন্ডে ১০^৮ টি ধাপ সম্পন্ন করলে ১০০ সেকেন্ড লাগবে তোমার কোডে ফলাফল আসতে, বিচারকরা জানিয়ে দিবে Time limit exceed(TLE) বা Execution timeout। তখন তোমাকে চিন্তা করতে হবে কিভাবে ধাপ সংখ্যা কমিয়ে আনা যায়।
আমরা একটা অ্যারে নিবো যেটার নাম হতে পারে cumulative_sum, এবং অ্যারেটার সাইজ হলো কমপক্ষে ১০০০০১। সেই অ্যারের i তম ইনডেক্সে আমরা ১ থেকে i পর্যন্ত সবগুলো সংখ্যার যোগফল আগে থেকে সংরক্ষণ করে রাখবো। তাহলে B থেকে E পর্যন্ত সবগুলো সংখ্যার যোগফল হবে cumulative_sum[E]-cumulative_sum[B-1]। কোডটা হবে এরকম:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#define MAX_E 100000+1 int cumulative_sum[MAX_E+1]; int main() { int sum=0; for(int i=1;i<=MAX_E;i++) { sum = sum + i; cumulative_sum[i]=sum; } int t; scanf("%d",&t); for(int case_no=1; case_no<=t;case_no++) { int B,E; scanf("%d",&B); scanf("%d",&E); int ans=cumulative_sum[E]-cumulative_sum[B-1]; printf("Case %d: %d\n",case_no,ans); } return 0; } |
ইনপুট নেয়া শুরু করার আগেই আমরা E এর সর্বোচ্চ মান পর্যন্ত লুপ চালিয়ে i তম ইনডেক্সে ১ থেকে i এর যোগফল সংরক্ষণ করে রেখেছি। এতে করে আমাদের প্রতি টেস্টকেসের ভিতর B থেকে E পর্যন্ত লুপ চালাতে হচ্ছে না! আমরা এখন কোডটাকে একটা কর্ণার কেস দিয়ে পরীক্ষা করবো, কেসটা হলো
1
1 100000
আমরা জানি ১ থেকে n পর্যন্ত সংখ্যাগুলোর যোগফল বের করার সূত্র হলো n*(n+1)/2, সেই অনুযায়ী আউটপুট আসার কথা 5000050000। কিন্তু দেখাচ্ছে 705082704। তারমানে কোথাও গন্ডগোল আছে, এই কোড সাবমিট করলে wrong answer দিবে। সমস্যাটা কি এবং কিভাবে সমাধান করা যায়? (হিন্টস: ইন্টিজার ওভারফ্লো, যোগফল অনেক বড়)
এখন তোমাকে ইনপুট সীমা আরো বাড়িয়ে দেই যাতে উপরের কোডটিও টাইমআউট হয়ে যায়:
Time limit: 2 seconds
1<=T<=100000
1<=B<=E<=1000000000000000
এখন তুমি যোগফল সেভ করে রাখার জন্য এতবড় অ্যারেও নিতে পারবেনা, লুপও চালাতে পারবে না, এত বড় লুপ চালাতে চালাতে কনটেস্টতো শেষ হয়ে যাবেই, আমাদের আয়ুও শেষ হয়ে যাবে। এখন কিভাবে সমাধান করা যায়? খুব সহজ, উপরের সুত্রটা ব্যবহার করলেই হয়! এটার কোড তুমি নিজে লিখবে।
প্রতিযোগীতায় কিছু সমস্যা সাবটাস্ক দেয়া থাকবে। ছোটো ইনপুট সীমার জন্য সমাধান করতে পারলে অল্প পয়েন্ট, বড় ইনপুট সীমার জন্য সমাধান করতে পারলে বেশি পয়েন্ট পাবে। তুমি যদি বড়টার জন্য সমাধান বের করে ফেলতে পারো তাহলে একই কোড দিয়ে ছোটোটাও সমাধান করা যাবে, কিন্তু উল্টোটা সত্যি নয়। তোমার যদি মনে হয় বড় সাবটাস্ক সমাধান করতে দেরি হয়ে যাবে তাহলে ছোটোটা সমাধান করে ঝটপট কিছু পয়েন্ট তুলে নিয়ে তারপর বড়টা নিয়ে চিন্তা করাই হবে বুদ্ধিমানের কাজ।
দুইজন সমান সমস্যা সমাধান করলে কে কয়বার ভুল কোড সাবমিট করেছে এবং কত তাড়াতাড়ি সমাধান করেছে এগুলো দিয়ে টাইব্রেক করা হয় তাই কোন সমস্যা কখন সমাধান করবে সেসব ব্যাপারে তোমার স্ট্রাটেজিই জয়-পরাজয় নির্ধারণ করে দিতে পারে। এছাড়া wrong answer বা TLE বা Runtime error পেলে কি করবে সেটা নিয়ে চিন্তাভাবনা করে রাখা উচিত। কোনো সমস্যা কয়েকবার চেষ্টা করার পরও সমাধান করতে না পারলে সেটা সরিয়ে রেখে অন্য সমস্যা সমাধান করে আবার আগেরটায় ফিরে আসা একটা ভালো কৌশল, অনেকেই একটা সমস্যা নিয়ে আটকে থেকে পুরো কনটেস্ট শেষ করে ফেলে, এটা কিছুতেই করা যাবে না। Ranklist এর দিকে সবময় একটা চোখ রাখতে হবে, যে সমস্যাটা বেশি মানুষ সমাধান করছে সেটা সহজ হবার সম্ভাবনাই বেশি। হবে তুমি যদি সেটা না পারো তাহলে ঘাবড়ে যাবার কিছু নেই, মাথা ঠান্ডা করে অন্য সমস্যা সমাধান করতে থাকো, পরে সেটায় ফিরে আসো।
সমস্যাগুলোর বর্ণনা বা ইনপুট-আউটপুট ফরমেট ঠিক এই লেখাটার মত হবে এমন কোনো কথা নেই, মনযোগ দিয়ে সমস্যা পড়ে তোমাকে বুঝতে হবে। কোনোকিছু বুঝতে সমস্যা হলে সাহায্য করার জন্য বিচারকরা এবং ভলান্টিয়ারাতো আছেই। প্রতিযোগীতার প্রস্তুতি নিতে লাইটওজের বিগিনার সেকশনের কিছু সমস্যা সমাধান করতে পারো। এছাড়া UVA অনলাইন জাজেও সমাধান করতে পারো, সেখানে কিভাবে সমাধান করতে হয় সেটা নিয়ে আমি লিখেছি এখানে। এছাড়া সুবিন ভাইয়ের বইয়ের যে লিংকটা উপরে দিয়েছি সেখানেও সহজ কিছু সমস্যা দেয়া আছে অনুশীলনের জন্য। মৌলিক সংখ্যা, উৎপাদকে বিশ্লেষণ, গসাগু বের করা, সহজ কিছু জ্যামিতির সমস্যা, সংখ্যাকে ছোট থেকে বড় সাজানো, বাইনারি সার্চ এ ধরণের কিছু সহজ বিষয়ের কোড যদি নিজে নিজে লিখতে পারো তাহলে প্রতিযোগিতায় অনেক কাজে লাগবে, প্রতিযোগিতায় হয়তো এসব বিষয় থেকে কোনো সমস্যাই আসবে না কিন্তু তোমার চর্চাটা যেকোনো সমস্যা সমাধান করতে কাজে লাগবে। অফিসিয়াল ওয়েবসাইটেও দরকারি অনেক তথ্য পাবে(http://www.nhspc.org/how-to)।
স্কুল-কলেজে যারা এরকম একটা প্রতিযোগিতায় অংশ নিতে পারছো তারা সত্যি ভাগ্যবান। আশা করছি প্রতিযোগিতাটা তোমরা উপভোগ করবে। সবার জন্য শুভকামনা থাকলো, দেখা হবে ৮ তারিখ ঢাকা বিশ্ববিদ্যালয়ে!
(এই লেখাটি অফিসিয়াল ওয়েবসাইটে দেয়া কোনো তথ্যের বিকল্প নয়।)
প্রোগ্রামিং নিয়ে যেকোনো সাহায্যের জন্য যোগাযোগ করতে পারো: shafaet.csedu@gmail.com
ফেসবুকে মন্তব্য
Powered by Facebook Comments
my hobby is programming!!!
আমি কলেজের শিক্ষার্থী । আমার কলেজে আমি ছারা কেউ প্রোগ্রামিং পছন্দ করে না । আমি একা কী অংশগ্রহন করতে পারব অন্য কোন কলেছে বা আয়োজনে।