সবাইকেই কম্পিটিটিভ প্রোগ্রামিংয়ে প্রবলেম ফেইস করতে হয়, এমন কেউ নেই যে এই প্রবলেমটা ফেইস করে না।

1. একটা প্রশ্ন সবার-ই থাকে যে কিভাবে Cp তে ভালো করবো ? -> Practice! Practice! Practice! কম্পিটিটিভ প্রোগ্রামিংয়ে ভালো করার সর্বোত্তম উপায় নিয়মিত অনুশীলন করা। প্রতিদিন অন্তত ২-৩ টা সমস্যা সমাধান করার চেষ্টা করা উচিত। Current Ratings যদি "x" হয়, তাহলে {x+100 to x+300} Ratings এর প্রবলেমগুলো সলভ করা উচিত। রেগুলার কনটেস্ট গুলোতে অংশ নেয়া উচিত কিন্তু যদি রেটিংস বাজে আসে অথবা নেগেটিভ হয়ে যায় তাহলেও Continue করতে হবে এবং যে প্রবলেমগুলো একটুর জন্য সলভ হয় নি, সেগুলো আবারো Try করতে হবে। সলভ করতে গিয়ে ঘন্টার পর ঘন্টা অথবা দিনের পর দিন আটকে থাকলেও হতাশ হওয়ার কিছু নেই, এটা সবার ক্ষেত্রেই হয়। (আমি নিজেও একবার একটা Hard Problem ১ মাস সময় নিয়ে সলভ করেছিলাম)

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

3. এবার আর একটি প্রশ্ন প্রায় অনেকেরই থাকে যে কোন প্রোগ্রামিং ল্যাংগুয়েজ দিয়ে কম্পিটিটিভ প্রোগ্রামিং করা উচিত ? -> অবশ্যই C++ কারণ এটা গতি এবং দক্ষতার জন্য বেস্ট। প্রতিযোগিতামূলক প্রোগ্রামিংয়ে সময় এবং মেমোরির সীমাবদ্ধতা ভীষণ গুরুত্বপূর্ণ সেখানে C++ ব্যবহার বুদ্ধিমানের কাজ। বিশেষকরে C++ এর STL প্রোগ্রামারদের দ্রুত এবং আরও দক্ষতার সাথে কোড লিখতে সাহায্য করে। অনেকেই "Python" Prefer করে, আমি নিজেও করি কিন্তু পাইথনের ধীরগতি অনেক সময়ই কন্টেস্টের জন্য বেশ অসুবিধাজনক হয়ে দাঁড়ায়।

4. এবার আসি কোথায় Practice অথবা Contest করবো ? Beecrowd, HackerRank, Codeforces, Codechef, AtCoder, LeetCode: Beginner to Advance, কে কোন Online Judge ব্যবহার করে প্রবলেম সলভ এবং Cp করবেন ? -> বিগিনার টু এডভান্সড, সিরিয়ালি বলা হলোঃ

4.1. Beecrowd (Former name URI): যারা একেবারেই প্রবলেম সলভিং পারেন না অথবা প্রবলেমটাই বুঝতে পারেন না, প্রবলেম বুঝতে পেইন লাগে তাহলে তাদের জন্য Beecrowd.

4.2. HackerRank: Practice এর জন্য HackerRank বেস্ট বেস্ট বেস্ট! যারা মোটামুটি একটু ভালো প্রবলেম সলভিং পারেন অথবা প্রবলেম বুঝতে অসুবিধা হয় না তাহলে এটা তাদের জন্য।

4.3. Codeforces, Codechef, AtCoder: কনটেস্ট এর জন্য এই তিনটি ওয়েবসাইট বেস্ট। প্রবলেম সলভিং Practice করে তারপর Cp শুরু করে দেয়া উচিত এবং কনটেস্টে রেটিংস যতোই বাজে আসুক, তবুও কনটেস্টগুলো Continue করা উচিত।

4.4. LeetCode: Practice, Contest, Interview Prep -> সব একসাথে করতে পারবেন, All in One.

5. কম্পিটিটিভ প্রোগ্রামিং কেন গুরুত্বপূর্ণ ? -> এটা সমস্যা সমাধানের দক্ষতা, যৌক্তিক যুক্তি এবং বাক্সের বাইরে চিন্তাভাবনা বৃদ্ধি করতে সহায়তা করে। জবের ক্ষেত্রেও কোডিং ইন্টারভিউয়ের জন্য বেশ বড় একটা অবদান রাখে। সাথে আত্মবিশ্বাস বাড়ায় কারণ চ্যালেঞ্জিং সমস্যাগুলো সফলভাবে সমাধানের মাধ্যমে আত্মবিশ্বাস অনেকটাই গ্রো করে।

6. যারা Debugging করতেও হিমশিম খায়, তাদের কি করা উচিত ? -> Practice! Practice! Practice! বেশি প্র্যাকটিস না করার ফলে অনেক অভিজ্ঞ প্রোগ্রামাররা ও ডিবাগিংয়ে দুর্বল থাকে, That's why Practice More!

Simple Tips: আমি কোডের মধ্যে ভুল সিলেক্ট করার সময় কোড উপর থেকে নিচে, এভাবে না পড়ে উল্টোভাবে পড়ে Debugging করি। (সবার ক্ষেত্রে প্রযোজ্য নাও হতে পারে)

1. DSA Foundations: Time & Space Complexity Analysis, Recursion, Divide & Conquer. (Essential for understanding the efficiency & structure of algorithms)

2. Basic DSA: Arrays, Stack, Queue, Binary Search, Sorting, Hashing, Two pointers, Backtracking.

3. Intermediate DSA: String Manipulation, Bit Manipulation, Greedy, Set, Map (Hash Map, Tree Map), Heap (Priority Queue), Graph (DFS, BFS, Shortest Paths), Disjoint Set (Union-Find). (Crucial for solving more complex problems & optimizing solutions)

4. Advanced DSA: DP, Game Theory, Tries, Segment Trees, Fenwick Trees (Binary Indexed Trees), Suffix Tree, Suffix Array, Heavy-Light Decomposition, Graph Coloring, Network Flow (Max Flow/Min Cut), Sqrt Decomposition.

1. Fundamentals:

   • Binary Exponentiation
   • Euclidean Algorithm (GCD, LCM)

2. Prime Numbers:

   • Sieve of Eratosthenes
   • Prime Factorization
   • Miller-Rabin Primality Test

3. Number Theory:

   • Euler's Totient Function
   • Fermat's Little Theorem
   • Wilson's Theorem
   • Modular Inverse (using Fermat’s Little Theorem & Extended Euclidean Algorithm)
   • Number of Divisors / Sum of Divisors
   • Mobius Function

4. Modular Arithmetic:

   • Chinese Remainder Theorem
   • Exponentiation by Squaring

5. Linear Algebra:

   • Matrix Multiplication and Inversion
   • Vectors, Eigenvalues, and Eigenvectors

6. Geometry:

   • Basics: Points, Lines, Circles, Distance, Angles
   • Computational Geometry: Convex Hull, Line Intersection
   • Coordinate Geometry: Point-Line Relationship, Polygon Area, Point in Polygon
   • Misc. Geometry: Orientation, Circle Intersection

7. Combinatorics:

   • Permutations, Combinations
   • Binomial Theorem & Coefficients
   • Pigeonhole Principle (used in distribution and arrangement problems)
   • Stars & Bars
   • Inclusion-Exclusion Principle
   • Lucas' Theorem (rare but useful)

8. Probability:

   • Basics
   • Expected Values (1D & 2D)

9. Misc/Miscellaneous:

   • Fast Fourier Transform (FFT)
   • Polynomial Multiplication
   • Random Number Generation
   • Line Sweep

1. Compilation Error (CE): Your program didn't get compiled successfully. Common reasons like Syntax Error, Missing Imports, Using restricted functionalities.

2. Wrong Answer (WA): Your program ran successfully but returned a different output. Common reasons like Incorrect interpretation of problem, Incorrect solution, Bug in the code, Edge cases(multiple test cases).

3. Time Limit Exceeded (TLE): Your program didn't complete execution in the alloted time. Your program gets a predefined time limit for every test case. Common reasons like Solution isn't optimal, Infinite Loop.

4. Memory Limit Exceeded (MLE): Your program tried to allocate more memory. Common reasons like Declaring large arrays/lists, Adding a lot of data, Stack Overflow Error.

5.1. Runtime Error (SIGSEGV/Segmentation Fault): Your program tried to access or write to a memory that, it can't access or is invalid. Common reasons like Accessing array/string index outside its range, Using too much memory in some languages, Uninitialized/Incorrectly initialized pointers.

5.2. Runtime Error (SIGFPE): Your program encountered a floating-point error. Generally caused if you do an invalid math operation. Common reasons like Division by zero, Square Root/Log of negative numbers.

5.3. Runtime Error (SIGABRT): Your program aborted the program due to fatal error. Common reason like Using assert/abort in the code.

5.4. Runtime Error (NZEC/Non-Zero Error Code): Your program didn't return a zero-error code from the main method & didn't fall into any of the above buckets. Common reasons like Not returning 0 from main method, Not catching exceptions.

6. Presentation Error (PE): Your program ran successfully & and the output's correct but the output format's incorrect. Normally due to "a missing space, newline, an extra space or newline."

In problem-solving, TLE (Time Limit Exceeded) means the program took too long to run within the allotted time. To understand when and where to use different types of algorithms, you need to understand the algorithm's time complexity. Time complexity is primarily about calculating how much time an algorithm takes to run, which helps compare multiple solutions to a problem.

Here are some common Time Complexities:

1. O(1): Constant Time Complexity

The algorithm's runtime doesn't depend on the input size n, it always performs a constant number of operations.

2. O(log n): Logarithmic Time Complexity

The runtime grows logarithmically relative to the input size n, typical of algorithms that divide the problem size in half at each step. (like Binary Search)

3. O(n): Linear Time Complexity

The runtime increases linearly with the input size n, this's common in algorithms that iterate through each element of an array or list.

4. O(n log n): Linearithmic Time Complexity

The runtime grows in proportion to n multiplied by the logarithm of n, this's often seen in efficient sorting algorithms. (like Merge & Quick Sort)

5. O(n^2): Quadratic Time Complexity

The runtime is proportional to the square of the input size n, typical of algorithms with nested iterations over the input. (like Bubble, Selection & Insertion Sort)

6. O(n^3): Cubic Time Complexity

The runtime grows with the cube of the input size n, occurring when there're three nested loops iterating over the input.

7. O(2^n): Exponential Time Complexity

The runtime grows exponentially with the input size n, this's common in algorithms that solve problems by exploring all subsets or combinations. (like Brute-force)

8. O(n!): Factorial Time Complexity

The runtime grows factorial with the input size n, typically seen in algorithms that generate permutations or combinations of a set.

9. O(sqrt(n)): Square Root Time Complexity

This complexity occurs in algorithms where operations are performed up to the square root of the input size n, it's less common but can appear in certain mathematical algorithms or optimizations.

How to calculate algorithms time complexity:

1. Identify the basic operations performed by the algorithm.

2. Count the number of times each operation is executed in terms of the input size n.

3. Express this count as a mathematical function of n.

4. Simplify the function to focus on the term with the largest growth rate.

5. Use "Big O Notation" to describe the asymptotic upper bound of the algorithm's time complexity.

Topics:

1. Brute Force, Searching.
2. Sorting (Language Library Function)
3. Strings
4. Number Theory like Floor, Ceil, Modulo, Divisors, Factorization.
5. Time Complexity
6. STL (Language Library)
7. Binary Search
8. Two Pointers
9. Binary + Bitwise Stuff
10. DP
11. Combinatorics
12. Prefix Sums (Basic Range Queries)
13. Modular Arithmetic, GCD/LCM, Prime Factor Rep.
14. Recursion
15. Graphs, Trees
16. DSU/UFDS
17. Segment Trees
18. String Algorithms (Hashing)
19. Proofs
20. Constructive Algorithms
21. Combinatorial Techniques, Probability, Expected Value.
22. Game Theory
23. Advanced Graph Techniques like Shortest paths, MST.

Suppose একটা প্রবলেমে ৫টা আইটেম দেয়া আছে, প্রত্যেকটার একটা Weight & Value আছে। কিছু আইটেম নেয়া যায় আবার কিছু বাদ দেয়া যায়। টার্গেট Total Weight ১০ এর নিচে রেখে Max Value বের করা। এটা অনেকটা ক্লাসিক Knapsack এর মতো শোনালেও, এখানে Twist হচ্ছে: কোন কোন আইটেম অলরেডি নেয়া হয়েছে সেটা Track করতে হবে। ক্লাসিক Knapsack এর O(N × W) এর তুলনায় এটা বেশি Complex কিন্তু Bitmask DP ছোট N এর জন্য বেশি Flexible.

এখন এটা সলভ করতে গিয়ে প্রতিটা আইটেমের জন্য লুপ চালিয়ে একটা অ্যারে দিয়ে Track করা হলে কোডের টাইম কমপ্লেক্সিটি বেড়ে যাবে এবং Complex হয়ে যাবে। আর যদি আইটেমের সংখ্যা ২০ এর বেশি হয় তাহলে TLE খাওয়ার চান্স আছে, আর এখানেই Bitmask DP comes to the rescue!

★ Bitmask DP কীভাবে কাজ করে?

একটা Integer এর বিট ব্যবহার করে পুরো স্টেট রিপ্রেজেন্ট করা যায়। Suppose ৫টা আইটেম আছে, তাহলে একটা ৫ বিটের সংখ্যা দিয়ে ট্র্যাক করা যাবে যে কোনটা নেয়া হয়েছে আর কোনটা নেয়া হয়নি। Example:

1. 00000 মানে কিছুই নেয়া হয়নি।
2. 10100 মানে ২ নং & ৪ নং আইটেম নেয়া হয়েছে।
3. 11111 মানে সবগুলো নেয়া হয়েছে।

এখন DP স্টেট হবে: dp[mask][weight] (2D অ্যারে ব্যবহার করলে), যেখানে mask হচ্ছে বর্তমানে কোন আইটেমগুলো নেয়া হয়েছে। Recursion দিয়ে এটা সলভ করা যাবে।

Suppose আইটেমগুলো:

1. Item 0: Weight 2, Value 3
2. Item 1: Weight 3, Value 4
3. Item 2: Weight 4, Value 5
4. Item 3: Weight 1, Value 2
5. Item 4: Weight 5, Value 6

Here, Total Weight লিমিট ১০.

এখানে dp[mask] দিয়ে Max Value স্টোর করা হবে। Bitmask DP তে সাধারণত dp[mask] (1D অ্যারে) ব্যবহার করা হয়, যদি weight ট্র্যাক করতে হয় তাহলে dp[mask][weight] ব্যবহার করতে হবে।

1. mask = 00001 (Item 0): Weight 2, Value 3
2. mask = 00010 (Item 1): Weight 3, Value 4
3. mask = 00100 (Item 2): Weight 4, Value 5
4. mask = 01000 (Item 3): Weight 1, Value 2
5. mask = 10000 (Item 4): Weight 5, Value 6
6. mask = 00011 (Item 0 + Item 1): Weight (2+3)=5, Value (3+4)=7
7. mask = 00101 (Item 0 + Item 2): Weight (2+4)=6, Value (3+5)=8
8. mask = 01001 (Item 0 + Item 3): Weight (2+1)=3, Value (3+2)=5
9. mask = 11001 (Item 0 + Item 1 + Item 4): Weight (2+3+5)=10, Value (3+4+6)=13
10. mask = 01100 (Item 2 + Item 3): Weight (4+1)=5, Value (5+2)=7

Here, Max Value 13 (যখন Item 0, 1 & 4 নেয়া হয়)

কোডে এটা রিকার্সিভলি চেক করতে হবে প্রতিটা বিটের জন্য - কোনটা নেয়া হবে & কোনটা নেয়া হবে না। এটা করার জন্য Bitwise Operation ব্যবহার হয়। যেমন: কোনো আইটেম i নেয়া হয়েছে কিনা চেক করতে "mask & (1 << i)", যদি ০ হয় তাহলে ঐ আইটেম এখনো নেয়া হয়নি। নতুন আইটেম i যোগ করতে "mask | (1 << i)", এটা mask এ i তম বিটকে ১ করে দেয়।

★ Complexity Analysis

Bitmask DP তে N টি আইটেম থাকলে 2^N সংখ্যক subset (mask) সম্ভব।

Total States: 2^N Each State Process Time: O(N) Total Complexity: O(N × 2^N)

যেহেতু, 2^20 approx 10^6 তাই N = 20 পর্যন্ত এটা Efficiently চলবে কিন্তু N > 25 হলে TLE খাওয়ার সম্ভাবনা বেশি!

NHSPC, BdOI, IOI, APIO, IUPC, NCPC, ACM ICPC, Meta Hacker Cup, ACM ICFP, NGPC.

1. NHSPC: For high school and college students, Polytechnic first & second year.
2. BdOI, APIO, IOI: For school and college students. Language (IOI)-> • For the past sessions (till 2015): C, C++, Pascal. • But (Since 2017): C++, Java, Pascal.
3. NCPC, IUPC, ICPC Dhaka Regional > ICPC Asia West > ICPC World Final - You can't participate in the same year: in more than 2 teams and "at more than 2 regionals.(for Asia)"
4. Meta Hacker Cup: Open to everyone, consists of three rounds: Qualification, Elimination, and Final.
5. ACM ICFP: Virtual coding contest, any programming language can be used.
6. NGPC: For female students in high school, college, and university. Rules similar to ICPC.

Note: Google Code Jam, Hash Code, Kick Start, and TCO (Topcoder Open) contests are no longer held.

1. Turing Completeness: যেখানে একটি প্রোগ্রামিং ল্যাংগুয়েজ দিয়ে সব কিছু Automate করা যায়। মানে একটি ল্যাংগুয়েজ দিয়ে সব ধরনের সমস্যা সমাধান করা যায় (solve any complex computation problem if provided with enough memory & time)

2. Quine: Quine নিজের কোডকে আউটপুট হিসেবে Print করে এবং এই ধরনের কোড লেখা Challenging (takes no input & produces a copy of its own source code as its only output)

3. Algo-Trading: স্টক মার্কেটের জন্য অ্যালগরিদম লিখে অটোমেটেড Trade করা হয়। এখানে কোড Real-Time Data নিয়ে জটিল সিদ্ধান্ত নিতে পারে, যা মানুষের চেয়ে অনেক Fast. (possible to make money with algo-trading)

4. Sorting Algorithms Art: কিছু Sorting অ্যালগরিদম Like QuickSort, MergeSort কে একটি আর্টওয়ার্ক হিসেবে Visualize করা যেতে পারে। ভিজ্যুয়ালাইজেশনে অ্যালগরিদমের আচরণ কিভাবে Data Sort করে সেটা দেখা যাবে, Interesting না ব্যাপারটা ??

5. Recursive Art: রিকার্সিভ ফাংশন ব্যবহার করেও Visual Art তৈরি করা যায়। Notable Example: Fractal Geometry(ফ্র্যাক্টাল জ্যামিতি); যেখানে লুপের মাধ্যমে একটি প্যাটার্ন বাড়াতে বাড়াতে জটিল স্ট্রাকচার তৈরি করা যায়। ○ Base case: Simplest form of the problem that has a direct answer. ○ Recursive case: The step where you break the problem into a smaller, self-similar task.

6. Polyglot Programming: যেখানে একটি কোড একাধিক প্রোগ্রামিং ল্যাংগুয়েজে Run করতে পারে। (the same code can work properly in different languages)

Example: একটি কোড এমনভাবে লেখা হতে পারে যা Python, JS, Ruby বা অন্যান্য ভাষায় একইভাবে Run হতে পারে। Interesting না ব্যাপারটা?? ★ But: Polyglot কোড create করা খুব কঠিন কারণ প্রতিটি ভাষার Syntax & Structure Maintain করতে হয়; যা সব ভাষায় একইভাবে Match হয় না। তাই একাধিক ভাষায় কোডটি Run করানোর জন্য Carefully কোড লিখতে হয়।

7. Easter Eggs in Code: অনেক সফটওয়্যার বা কোডে ডেভেলপাররা ইচ্ছা করে কিছু Secret/Funny ফিচার, মেসেজ রেখে দেয়। এগুলো আসলে Surprise Plan!!

Examples:

7.1. Google এর "Do a Barrel Roll": গুগলে এটা লিখে সার্চ দিলে, সার্চ পেজটি 360 ডিগ্রি ঘুরে যায়।

7.2. Chrome Dino Game: ইন্টারনেট কানেকশন না থাকলে একটি ডাইনোসর Game দেখা যায় যা Key Press করলে শুরু হয়।

7.3. Excel 95 এর "Flight Simulator": এক্সেলের Old ভার্সনে Hidden Flight Simulator ছিল।

(these're mainly added as fun elements to entertain users, spark curiosity & encourage them to explore the software further)

8. Genetic Algorithms: এই অ্যালগরিদম "Evolution(প্রকৃতির বিবর্তন)" ধারণা থেকে অনুপ্রাণিত, যা "Survival of the Fittest" ধারণা ব্যবহার করে। যেখানে সমস্যা সমাধানের জন্য বিভিন্ন সম্ভাব্য-সমাধান তৈরি করা হয় এবং বেস্ট টা সিলেক্ট করা হয়। আর এভাবেই এই অ্যালগরিদম পর্যায়ক্রমে Better Solution খুঁজে বের করতে থাকে।

9. Code Golf: কোডিং দক্ষতা এবং সৃজনশীলতার পরীক্ষা (প্রোগ্রামিং চ্যালেঞ্জ); যেখানে একটি নির্দিষ্ট কাজ করতে, সবচেয়ে কম কোড ব্যবহার করে কাজটি করার কৌশল খুঁজে বের করতে হয়। ★ কোডের দৈর্ঘ্য যত কম হবে, তত বেশি স্কোর পাওয়া যায়।

10. Esoteric Programming Languages: যা মজার উদ্দেশ্যে তৈরি করা হয়, কাজের জন্য নয়। এসব ভাষার কোড সাধারণত জটিল, অস্বাভাবিক এবং অদ্ভুতভাবে ডিজাইন করা হয়। এগুলো চ্যালেঞ্জ গ্রহণকারী ব্যক্তিদের জন্য তৈরি করা হয়।

Examples:

10.1. LOLCODE: কোড লেখার স্টাইল "meme" এর মতো; যেখানে কোড হাস্যকরভাবে লেখা হয়।

10.2. Shakespeare: এই ভাষায় এমনভাবে কোড লেখা হয়; যেখানে প্রোগ্রামটি একটি নাটকের স্ক্রিপ্টের মতো দেখায়। কোডের সিনট্যাক্স এমনভাবে ডিজাইন করা হয় যে তা দেখতে অনেকটা শেক্সপিয়ারের নাটকের মতো মনে হয়।

10.3. Piet: প্রোগ্রামিং ভাষা; যা ছবির মতো কোড লেখে, যেখানে প্রোগ্রামটি দৃশ্যমানভাবে একধরনের ছবির আকারে থাকে।

11. Concurrency & Parallelism: প্রোগ্রামিংয়ে কনকারেন্সি এবং প্যারালেলিজম ব্যবহার করলে একসাথে অনেক কাজ করা যায়, যা সিস্টেমের কার্যক্ষমতা অনেক বাড়িয়ে দেয়। ★ Concurrency's about "dealing with" lots of things at once. Parallelism's about "doing" lots of things at once.