C++ CP Guide

Complete Guide to Competitive Programming in C++

ভূমিকা (Introduction): প্রতিযোগিতামূলক প্রোগ্রামিং (Competitive Programming) হচ্ছে একটি মানসিক খেলা যেখানে আপনাকে নির্দিষ্ট কিছু সমস্যা সমাধান করতে হয় কম্পিউটার প্রোগ্রামিং ব্যবহার করে। Codeforces হলো এমন একটি জনপ্রিয় প্ল্যাটফর্ম যেখানে আপনি প্রোগ্রামিং সমস্যা সমাধান করে আপনার দক্ষতা বাড়াতে পারেন। এই গাইডটি আপনাকে C++ ব্যবহার করে প্রতিযোগিতামূলক প্রোগ্রামিং-এর জন্য প্রস্তুত করতে সাহায্য করবে।

Competitive programming is a mental sport where you have to solve specific problems using computer programming. Codeforces is a popular platform where you can solve programming problems to improve your skills. This guide will help you prepare for competitive programming using C++.

পার্ট ১: একদম মৌলিক বিষয়গুলো (Part 1: The Absolute Basics)

This section covers the foundational building blocks of C++. Understanding these concepts of variables, data types, and how to handle input/output is the first and most critical step in your programming journey. Master these, and you'll have a solid base for everything that follows.

1.1 Data Types and Variables

Variables are containers for storing data values. In C++, each variable must have a specified data type, which determines the size and layout of the variable's memory. Here are the most common ones:

int

For whole numbers.

double

For floating-point numbers.

char

For a single character.

string

For a sequence of characters.

bool

For true/false values.

long long

For very large integers.

1.2 Input and Output

For competitive programming, getting input quickly and printing output correctly is crucial. C++ offers two main ways to do this. While `cin`/`cout` are easier, `scanf`/`printf` are often faster and preferred in contests.

// Using cin and cout
#include <iostream>
int main() {
    int a;
    std::cin >> a;
    std::cout << "You entered: " << a << std::endl;
    return 0;
}

// Using scanf and printf (often faster)
#include <cstdio>
int main() {
    int a;
    scanf("%d", &a);
    printf("Number is: %d\n", a);
    return 0;
}

পার্ট ২: গুরুত্বপূর্ণ ধারণাগুলো (Part 2: Essential Concepts)

Now that you have the basics, this section introduces the essential tools for organizing data. Arrays, vectors, and strings are fundamental for handling collections of data, while pointers and structures allow for more complex and efficient memory management and data representation.

2.1 Arrays and Vectors

Both are used to store collections of elements. An array has a fixed size determined at compile time. A vector is a dynamic array from the STL, which can grow or shrink in size. Vectors are generally more flexible and safer to use in competitive programming.

#include <vector>
#include <iostream>

int main() {
    // Array (fixed size)
    int arr[5] = {1, 2, 3, 4, 5};
    
    // Vector (dynamic size)
    std::vector<int> vec;
    vec.push_back(10); // Add element
    vec.push_back(20);
    
    std::cout << "Vector size: " << vec.size() << std::endl;
    return 0;
}

2.5 ASCII Values

Every character has a corresponding integer value under the ASCII standard. This is useful for character manipulation, like converting between uppercase and lowercase letters or checking if a character is a digit.

#include <iostream>

int main() {
    char c = 'A';
    int ascii_value = c; // Implicit conversion
    std::cout << "ASCII for 'A' is " << ascii_value << std::endl; // Outputs 65

    char letter_a = 97;
    std::cout << "Character for 97 is " << letter_a << std::endl; // Outputs 'a'
    return 0;
}

পার্ট ৩: C++ STL (Standard Template Library)

The STL is your best friend in competitive programming. It's a collection of powerful and highly optimized data structures and algorithms that save you from reinventing the wheel. Mastering the key components of the STL is essential for solving problems quickly and efficiently.

Key STL Containers

  • vector: Dynamic array.
  • map: Stores key-value pairs, sorted by key. Slower than `unordered_map`.
  • unordered_map: Stores key-value pairs, unsorted (hashed). Much faster for lookups.
  • set: Stores unique elements, sorted.
  • unordered_set: Stores unique elements, unsorted (hashed).
  • pair: A simple container to hold two heterogeneous objects as a single unit.
  • stack: Last-in, first-out (LIFO) data structure.
  • queue: First-in, first-out (FIFO) data structure.

পার্ট ৪: প্রতিযোগিতামূলক প্রোগ্রামিং কৌশল (Part 4: Strategy)

Knowing the language is only half the battle. This section focuses on the strategic approach to problem-solving. Understanding time complexity is crucial for writing efficient code that passes within the time limits, and learning common algorithmic techniques will provide you with a toolbox for tackling a wide range of problems.

4.1 Problem-Solving Approach

1. Read & Understand
→
2. Think Algorithm
→
3. Analyze Complexity
→
4. Code & Test

4.2 Time Complexity Analysis (Big O)

Understanding how the runtime of your algorithm scales with the input size is the most important skill in competitive programming. This chart visualizes the growth rates of common complexities. An algorithm with O(n²) complexity will be much slower for large inputs than an O(n log n) one.

পার্ট ৫: Codeforces-এর জন্য টিপস (Part 5: Codeforces Tips)

Here are some practical tips specifically for the Codeforces platform. These small adjustments and best practices can make a big difference in contests, from speeding up your program's execution to helping you learn more effectively from your mistakes.

  • দ্রুত I/O (Fast I/O): Always add these lines at the beginning of your `main` function to speed up `cin` and `cout`, which can prevent `Time Limit Exceeded` errors on large inputs. 
    std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
  • ভুলগুলো বুঝুন (Understand Your Mistakes): Don't just move on from a `Wrong Answer` or `Time Limit Exceeded`. Analyze the test case that failed. Try to find the bug or the reason for inefficiency. This is how you truly improve.
  • কোড সাবমিট করুন (Submit Your Code): Don't be afraid to submit. Getting your first accepted solution is a huge milestone. Every submission, even a wrong one, is a learning opportunity.