Goldbach's Conjecture

Conjecture বা অনুমান হচ্ছে এমন ধারণা যার প্রমাণিত নয়। এ ধরনের অনুমান করা হয় উপলব্ধ তথ্যের উপর ভিত্তি করে। জার্মান গণিতবিদ Christian Goldbach একটি conjecture দেন ১৭৪২ সালে। সেটি ছিলো, 

“যেকোনো জোড় সংখ্যাকে আমরা দুটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতে পারি।” 

সেসময় 1 কে ও  মৌলিক সংখ্যা হিসেবে ধরা হতো। তাই পরবর্তীকালে এই conjecture কে পরিবর্তন করে বলা হয়, 

“2 থেকে বড় যেকোনো জোড় সংখ্যাকে আমরা দুটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতে পারি।”

যেমন, 4 = 2 + 2, 6 = 3 + 3, 8 = 5+ 3 ইত্যাদি। এই conjecture কে বলা হয় Goldbach’s strong conjecture. এই conjecture এর উপর ভিত্তি করে আরও একটি conjecture রয়েছে। সেটি হলো,

“5 থেকে বড় যেকোনো বিজোড় সংখ্যাকে আমরা তিনটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতে পারি।”

এই conjecture টি Goldbach’s strong conjecture এর উপর ভিত্তি করে দেওয়া হয়েছে, তাই এটিকে Goldbach’s weak conjecture বলা হয়। খেয়াল করলে দেখবো, 5 থেকে বড় যেকোনো বিজোড় সংখ্যা n এর জন্য n-3 অবশ্যই 2 থেকে বড় জোড় সংখ্যা হবে। তাহলে আমরা n-3 কে তো দুটি মৌলিক সংখ্যার যোগফল হিসেবে লিখতেই পারছি। এরপর শুধু ওই যোগফলের সাথে 3 যোগ করে দিলেই তো আমরা n পেয়ে যাচ্ছি। 

এবার আমরা এ সম্পর্কিত কিছু সমস্যা দেখবো।

উদাহরণ সমস্যা ১

উৎস: Codeforces Round #324 (Div. 2), Problem D 

সমস্যার Link: https://codeforces.com/problemset/problem/584/D  

একটি বিজোড় সংখ্যা n ( 3 <= n <= 1e9 ) দেওয়া আছে। একে তিন বা তার কম সংখ্যক মৌলিক সংখ্যার যোগফল হিসেবে প্রকাশ করতে হবে। 

n যদি মৌলিক সংখ্যা হয়, তবে একে আর ভাঙার দরকার হবে না। তাই শুরুতে আমরা যাচাই করে নিবো n মৌলিক সংখ্যা কিনা। 

এবার n যদি মৌলিক সংখ্যা না হয়, তাহলে এটি অবশ্যই 9 বা তার চেয়ে বড় হবে। কারণ 3, 5, 7 এরা সবাই মৌলিক সংখ্যা। আমরা 3 কে আউটপুটের একটি  মৌলিক সংখ্যা হিসেবে ধরে নিবো। 

এখন (n-3) হচ্ছে একটি জোড় সংখ্যা এবং 6 <= (n-3) <= 1e9. একটু আগেই তো Goldbach এর conjecture থেকে আমরা দেখলাম এই সীমার মধ্যে জোড় সংখ্যাগুলোকে আমরা দুটি মৌলিক সংখ্যার যোগফল আকারে লিখতে পারি। তাহলে আমরা একটি লুপ চালিয়েই মৌলিক সংখ্যা দুটি বের করতে পারি। 

সমাধান link: https://codeforces.com/contest/584/submission/150913786

অনুরূপভাবে আমরা Timus 1356 সমস্যাটির সমাধান করে ফেলতে পারি। 

Online judge এর বিভিন্ন ধরনের verdict

Accepted (AC): কোন problem এর জন্য আমাদের program যদি judge এর সকল test case এর জন্য সঠিক output দেখায়, তাহলে আমরা accepted verdict পাই। অবশ্যই test case গুলো বলে দেওয়া time limit ও memory limit এর মধ্যে pass হতে হবে। Contest এ কোন সমস্যার জন্য আমাদের solution code যদি accepted হয়, তবেই ওই rank list এ ওই সমস্যার জন্য point ও penalty যোগ হয়। প্রতি ভুল submission এর জন্য penalty হয়। আবার যত বেশি দেরিতে submission accepted হয়, তত বেশি penalty হয়। যেমন, ICPC তে প্রতি মিনিট এর জন্য penalty 1 আর প্রতিটি ভুল submission এর জন্য penalty 20 হয়। উল্লেখ্য যে, আমাদের solution code টি accepted না হওয়া পর্যন্ত কোন penalty যোগ হবে না। 

Compilation Error (CE): আমাদের submitted code যদি judge compiler সফলভাবে compile করতে না পারে, তবে এই error হয়। তাই code submit করার পূর্বে নিজেদের computer এ program টি compile হচ্ছে কিনা সেটি নিশ্চিত হয়ে নেওয়া উচিত। পাশাপাশি judge compiler এর সাথে নিজেদের IDE এর compiler এর version মিলছে কিনা সেদিকেও খেয়াল রাখা উচিত, নতুবা এমন হতে পারে যে feature টি আমাদের IDE এর compiler এ আছে সেটি judge compiler এ নেই। সেক্ষেত্রে কিন্তু compilation error দেখাবে। 

Wrong Answer (WA): আমাদের program যদি কোন test case এর জন্য ভুল output দেখায়, তবে judge আমাদের Wrong Answer verdict দেয়। এর মানে আমাদের program এর logic ঠিক নেই। হতে পারে সমস্যাটির সমাধান idea ভিন্ন বা আমরা কোন corner case handle করিনি ইত্যাদি। 

Time Limit Exceeded (TLE): সমস্যায় আমাদের একটি time limit দেওয়া থাকে। কোন test case এর জন্য আমাদের program কে এই সময় সীমার মধ্যে output বের করতে হবে। Run করার পর যদি এই সময়ের মধ্যে output না পাওয়া যায়, তবে judge আমাদের Time Limit Exceeded verdict দিবে। 

Memory Limit Exceeded (MLE): Time limit এর মতোই সমস্যায় আমাদের একটি memory limit দেওয়া থাকে। কোন test case এর জন্য আমাদের program এই পরিমাণের বেশি memory ব্যবহার করতে পারবে না। যদি বেশি memory ব্যবহার করতে যায়, তবে judge আমাদের Memory Limit Exceeded verdict দিবে। 

Runtime Error (RE/RTE): Program ঠিকমত compile হওয়ার পর যদি execution এর সময় fail করে, তবে Runtime Error হয়। এই execution failure বিভিন্ন কারণে হতে পারে। যেমন, আমরা যদি কোন array এর invalid index কে access করার চেষ্টা করি, তাহলে judge আমাদের runtime error দিবে। আবার array যদি out of bound হয়ে যায়, অর্থাৎ array size যদি খুব বেশি বড় হয়ে যায়, সেক্ষেত্রে runtime error হয়। 

Presentation Error (PE): যদি আমাদের program সঠিক output দেয়, কিন্তু সমস্যায় বলে দেওয়া output format এর সাথে যদি সেটির presentation যদি হুবহু না মিলে, তবে judge এ ধরনের error দেখায়। সাধারণত ঠিকমত space বা new line (‘\n’) print না করলে এই error আসে। অনেক online judge এ এটিকে wrong answer হিসেবে ধরা হয় এবং contest time এ penalty যোগ হয়। আমার  একবার onsite contest এ line এর শেষে একটি অতিরিক্ত space print করার কারণে penalty খেতে হয়েছিলো। তাই output এ space এর সংখ্যা নিয়ে বিশেষ খেয়াল রাখা উচিত।

Idleness Limit Exceeded (ILE): Program যদি অনেক সময় ধরে idle হয়ে বসে থাকে user interaction থেকে input পাবার আশায়, তবে Idleness Limit Exceeded হয়। 

Prefix Sum Technique

প্রোগ্রামিং প্রব্লেম সল্ভিং এর খুব beginner level এর একটি topic হচ্ছে prefix sum technique. এটি সহজ একটি technique, কিন্তু advanced অনেক সমস্যায় এ এটি কাজে লাগে। 

ধরি, আমাদেরকে একটি integer array দেওয়া আছে। এবার একটি index-range [L,R] (যেখানে L<=R) দিয়ে বলা হলো, এই range এর মধ্যে যেসব element আছে তাদের যোগফল বের করতে। আমরা মাথায় যেটা আসে যে, একটি লুপ ব্যবহার করে array এর L তম element থেকে R তম element পর্যন্ত traverse করবো এবং এদের যোগফলকে একটি variable এ store করে print করে দিবো। 

এখন যদি এ ধরনের query একটি না থেকে অনেক গুলো থাকে, তবে কি প্রতিটি query এর জন্যই আমরা এভাবে একবার করে লুপ চালাবো? না! একটি smart technique আছে, যাকে আমরা prefix sum বা cumulative sum বলি। আমরা এখন সেটি দেখবো। 

প্রথমে আমাদের prefix sum array বানাতে হবে। এই array এর i তম element হবে given array এর প্রথম i সংখ্যক element এর যোগফল। আমরা একটি লুপ চালিয়েই নিচের মতো করে এই কাজটি করতে পারি। 

int arr[100005]; int prefixSum[100005]; int main(){     int n;    cin>>n;     for(int i=1; i<=n; i++)cin>> arr[i];     for(int i=1; i<=n; i++)prefixSum[i] = prefixSum[i-1] + arr[i]; }

কোডে prefixSum[i] বের করার সময় আগের ধাপে বের করে রাখা prefixSum[i-1] এর সাথে arr[i] যোগ করে দিলেই হচ্ছে। তাহলে O(n) time complexity তে আমাদের prefixSum array টি তৈরি হয়ে গেল। 

এবার একটু খেয়াল করলে আমরা দেখবো, prefixSum[R] এ array এর index 1 থেকে R পর্যন্ত element গুলোর যোগফল store করে রাখা আছে। আবার prefixSum[L-1] এ array এর index 1 থেকে L-1 পর্যন্ত element গুলোর যোগফল store করে রাখা আছে। এখন আমরা যদি prefixSum[R] থেকে prefixSum[L-1] কে বিয়োগ করি, তাহলেই তো index L থেকে R পর্যন্ত element গুলোর যোগফল পেয়ে যাচ্ছি, তাই না?

অর্থাৎ কোন query এর জন্য আমরা একটি মাত্র বিয়োগ operation করেই উত্তর দিয়ে দিতে পারছি। পূর্বের পদ্ধতিতে n size এর array আর m সংখ্যক query এর জন্য আমাদের program এর time complexity হতো O(n*m). আর এখন prefixSum array বানানোর জন্য time complexity লাগলো O(n) এবং m সংখ্যক query এর প্রতিটির answer আমরা দিতে পারছি O(1) এ। ফলে পুরো প্রোগ্রামের time complexity দাঁড়ায় O(n+m).

SPOJ এর CSUMQ - Cumulative Sum Query (link: https://www.spoj.com/problems/CSUMQ/ ) সমস্যাটি হুবহু একই সমস্যা। আমরা তাহলে একটু চেষ্টা করে কোড লিখে সমস্যাটির সমাধান করে ফেলবো। 

ASCII

ASCII 

আমরা কি কখনো ভেবে দেখেছি, যে কম্পিউটার 0 আর 1 ছাড়া কিছু বুঝে না, সে কিভাবে ‘a’, ‘b’, ‘c’’, ‘#’, ‘?’ ইত্যাদি character গুলো মনে রাখে? আচ্ছা, যেহেতু কম্পিউটার 0 আর 1 বুঝে, তাহলে আমরা এই character গুলোকে যদি 0 আর 1 এর combination হিসেবে কম্পিউটারের কাছে উপস্থাপন করতে পারি। আর এভাবে পেলেই তো সে এদেরকে মনে রাখতে পারবে, তাই না? এইভাবে কোন character কে কম্পিউটারের বোধগম্য সংখ্যাতে উপস্থাপনের ব্যাপারটিকে character-encoding বলে। ASCII হচ্ছে character-encoding এর একটি standard. এর পূর্ণরূপ হলো American Standard Code for Information Interchange.

কোন একটি character এর ASCII value হচ্ছে একটি unique decimal সংখ্যা, যেটিকে কম্পিউটার তার binary representation হিসেবে মনে রাখে। যেমন, lowercase ‘a’ এর ASCII value 97; আবার uppercase ‘A’ এর ASCII value 65. ‘0’ থেকে ‘9’ এই অঙ্কগুলোর জন্য ASCII value হচ্ছে 48 থেকে 57 এর মধ্য। এভাবে 8-bit ASCII তে 28 টি ভিন্ন ভিন্ন characters আছে। 

8-bit ASCII Table

                                                                                                                     [source: https://text-symbols.com/ascii/ ]

কোন character এর ASCII value কে আমরা integer হিসেবে store বা প্রিন্ট করতে পারি। যেমন, ‘a’ থেকে ‘z’ পর্যন্ত character গুলোকে print করার জন্য আমরা নিচের code snippet টি অনুসরণ  করতে পারি। 

for(char c = 'a'; c <= 'z'; c++){       int x = c;       printf("ASCII value of %c is: %d\n",c,x); }

এখন আমরা উদাহরণ সমস্যা হিসেবে atcoder এর “Case Sensitive” সমস্যাটি (link:https://atcoder.jp/contests/past202005-open/tasks/past202005_a ) দেখবো। এই সমস্যায় আমাদেরকে দুটি string দেওয়া হবে যেগুলো শুধু English alphabet এর character গুলো দিয়ে গঠিত। Uppercase এবং lowercase উভয় ধরনের character-ই থাকতে পারে। যদি string দুটি হুবহু মিলে যায়, তবে আমাদেরকে output হিসেবে “same” print করতে হবে। আর যদি হুবহু না মিলে, তবে দুই ধরনের case হতে পারে। যদি string দুটির সবগুলো character কে একই case (uppercase বা lowercase) এ নিয়ে যাওয়ার পর তারা সমান হয়, তাহলে আমাদেরকে “case-insensitive” print করতে হবে, অন্যথায় “different” print করতে হবে। 

আমরা “same” print করার কাজটি একটি if conditional statement ব্যবহার করেই করতে পারি। যদি same না হয়, তবে string দুটির সকল character কে এবার একই case এ নিয়ে যেতে হবে “case-insensitive” কিনা যাচাই করার জন্য। আমরা সবগুলো character কে lowercase এ convert করতে পারি। যেসব character ইতিমধ্যে lowercase এ আছে, সেগুলোকে কিছু করতে হবে না। তবে যেগুলো uppercase এ আছে সেগুলোকে নিয়ে আমাদের মাথা ব্যাথা। ASCII table এ একটু খেয়াল করলে আমরা দেখবো, যেকোন English letter এর uppercase এবং lowercase character এর মধ্যে ASCII value এর পার্থক্য 32. তাহলে, string এর কোন uppercase character এর জন্য তার ASCII value এর সাথে 32 যোগ করে দিলেই আমরা সেটির lowercase character কে পেয়ে যাবো। এভাবে lowercase এ string দুটিকে convert করার পর equal কিনা তা compare করলেই হবে। তাহলে, আমাদের কোড হবে নিচের মতো। 

string s, t;     cin>> s >> t; if( s==t )  cout<<"same\n"; else{           for( int i=0; i<s.size(); i++)   if( s[i] >= 'A' and s[i] <= 'Z' ) s[i] = s[i] + 32;           for( int i=0; i<t.size(); i++)   if( t[i] >= 'A'  and t[i] <= 'Z' ) t[i] = t[i] + 32;                      if( s==t )  cout<<"case-insensitive\n";           else      cout<<"different\n"; }

LCM (Least Common Multiple)

একটি সংখ্যা x কে অপর একটি সংখ্যা y দিয়ে ভাগ করলে যদি ভাগশেষ 0 থাকে, তবে x হবে y এর একটি গুণিতক (multiple). যেমন, 24 সংখ্যাটি 6 দিয়ে নিঃশেষে বিভাজ্য, তাই 6 এর একটি গুণিতক হবে 24. 

এখন দুটি সংখ্যা a ও b এর সাধারণ গুণিতক (common multiple) হবে এমন একটি সংখ্যা যেটি a ও b উভয় দিয়েই নিঃশেষে বিভাজ্য। যেমন, 24 সংখ্যাটি 6 ও 8 উভয় দিয়েই নিঃশেষে বিভাজ্য, 6 ও 8 এর একটি সাধারণ গুণিতক হবে 24.

এবার আমরা ধারণা করতেই পারছি যে, লঘিষ্ঠ সাধারণ গুণিতক (Least Common Multiple) হবে সংখ্যা দুটির সাধারণ গুণিতক গুলোর মধ্যে সবচেয়ে ছোট সংখ্যাটি। যেমন, 6 ও 8 এর গুণিতক গুলো হলো 24, 48, 72, 96 ইত্যাদি। এর মধ্যে সবচেয়ে ছোট গুণিতকটি হলো 24. তাই 6 ও 8 এর LCM (Least Common Multiple) হলো 24.

তাহলে আমরা শিখলাম LCM কী জিনিস। এবার আমরা শিখবো দুটি সংখ্যা a ও b এর LCM কিভাবে বের করতে হয়। LCM বের করার দুটি পদ্ধতি দেখবো আমরা। 

পদ্ধতি ১

প্রথমে আমরা a ও b উভয়ের prime factorization বের করবো। এখন কোনো prime factor p এর জন্য a ও b এর উভয়ের prime factorization এ p এর power যেখানে সর্বোচ্চ সেটিকে আমরা LCM এর prime factorization এ রাখবো। যেমন, 

6 এর prime factorization, 6 = 2 x 3

8 এর prime factorization, 8 = 2^3

তাহলে, এদের LCM এ 2 এর power হবে max (1,3) বা 3. আবার LCM এ 3 এর power হবে max(1,0) বা 1.

অতএব, 6 ও 8 এর LCM = 2^3 x 3 = 24.

পদ্ধতি ২

এই পদ্ধতি গতে দুটি সংখ্যার GCD ও LCM এর মধ্যকার সম্পর্কের উপর ভিত্তি করে আমরা তাদের LCM বের করবো। দুটি সংখ্যার গুণফল, তাদের GCD ও LCM এর গুণফলের সমান। অর্থাৎ দুটি সংখ্যা a ও b এর জন্য, 

a x b = GCD(a,b) x LCM(a,b).

তাহলে আমরা লিখতে পারি,

LCM(a,b) =(a x b) / GCD(a,b)

এখন আমরা যদি a ও b এর GCD জানি, তাহলে খুব সহজেই তাদের LCM বের করতে পারবো। 

উপরের দুটি পদ্ধতির মধ্যে প্রথমটিতে আমাদেরকে প্রদত্ত সংখ্যা দুটির prime factorization বের করতে হচ্ছে, যা খুবই time expensive. অন্যদিকে দ্বিতীয় পদ্ধতিতে GCD বের করলেই কাজ হয়ে যাচ্ছে। Prime factorization বের করার তুলনায় GCD বের করার time complexity খুবই কম। তাই আমরা program এ LCM বের করার প্রয়োজন হলে দ্বিতীয় পদ্ধতি অবলম্বন করবো। 

a ও b এর LCM বের করার code

//LCM(a,b) returns the LCM of a and b. int LCM (int a, int b){            int gcd = __gcd(a,b);      //GCD of a and b            int lcm = (a*b) / gcd;            return lcm; }

এখন আমাদেরকে যদি তিনটি সংখ্যা a,b ও c এর LCM বের করতে বলা হয়, তাহলে? এর জন্য আমরা প্রথমে a ও b এর LCM বের করব, এরপর তার সাথে c এর LCM বের করলেই সেটি হবে a, b ও c এর LCM. ঠিক একইভাবে আমরা n সংখ্যক integer জন্য LCM বের করতে পারি। 

তাহলে আমরা শিখে ফেললাম কিভাবে দুই বা ততোধিক সংখ্যার LCM বের করতে হয়। এবার আমরা একটু মাথা খাটিয়েই BEE 2514 ও BEE 1909 সমস্যা দুটির সমাধান করে ফেলতে পারি, তাই না?

BEE 2514

Problem link: https://www.beecrowd.com.br/judge/en/problems/view/2514

BEE 1909

Problem link: https://www.beecrowd.com.br/judge/en/problems/view/1909