/Competitive-Programming-Tips

Tips for improvement, resources, DSA, math, verdicts, time complexity, ratings, contest

Competitive Programming (CP): Tips for Improvement in Bangla

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

  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.

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

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

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

DSA for Competitive Programming (CP):

  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.

Math for Coding/Competitive Programming (CP):

  1. Fundamentals: Binary Exponentiation, Euclidean Algorithm, Greatest Common Divisor (GCD), Least Common Multiple (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.

  4. Modular Arithmetic: Modulo Inverse, Chinese Remainder Theorem, Exponentiation by Squaring.

  5. Linear Algebra: Matrix, Vectors, Eigenvalues, Eigenvectors.

  6. Geometry: • Basic Geometry (Points, Lines, Circles), • Computational Geometry (Convex Hull, Line Intersection), • Coordinate Geometry.

  7. Combinatorics: Permutations, Combinations, Binomial Theorem, Pigeonhole Principle.

  8. Misc/Miscellaneous: Fast Fourier Transform (FFT), Polynomial Arithmetic, Random Number Generation.

Understanding the error codes:

  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.

  1. 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."

Time Complexity:

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.

  1. 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)

  1. 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.

  1. 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)

  1. 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)

  1. 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.

  1. 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)

  1. 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.

  1. 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.

Newbie to Candidate Master (CM): Ratings [0-1900]

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.

Programming Contests:

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.