UNIT – V: Competitive Programming and Dynamic Programming

1. Introduction to Competitive Programming

Competitive Programming (CP) is a problem-solving approach where programmers solve

 Logical thinking

 Optimized algorithms

 Efficient data structures

Key Characteristics

 Multiple test cases

 Strict time limits (usually 1–2 seconds)

 Emphasis on time and space optimization

2. Bit Manipulation Techniques

Bit manipulation uses binary representation of numbers to perform operations efficiently.

Common Bitwise Operators

Operator Symbol Description

AND & Sets bit if both bits are 1

OR | Sets bit if at least one bit is 1

XOR ^ Sets bit if bits are different

NOT ~ Inverts bits

Left Shift << Shifts bits to left

Right Shift >> Shifts bits to right

Visualization (Binary Representation)

Number: 5

Binary: 0101

5 << 1 = 1010 (10)

Example: Check if a number is even or odd

#include <iostream>

using namespace std;

int main() {

int n = 7;

if (n & 1)

cout << "Odd";

else

cout << "Even";

return 0;

Application of Bitwise Operator

 Bitwise operations are prominent in embedded systems, control systems, etc where
memory(data transmission/data points) is still an issue.

 They are also useful in networking where it is important to reduce the amount of
data, so booleans are packed together. Packing them together and taking them apart
use bitwise operations and shift instructions.

 Bitwise operations are also heavily used in the compression and encryption of data.

 Useful in graphics programming, older GUIs are heavily dependent on bitwise

3. Divide and Conquer Technique

Divide and Conquer breaks a problem into smaller subproblems, solves them independently,
and combines their results.

Steps

 Divide: Dividing the problem into two or more than two sub-problems that are
similar to the original problem but smaller in size.
  Conquer: Solve the sub-problems recursively.

 Combine: Combine these solutions to subproblems to create a solution to the

Visualization

Array: [8,7,4,2,9,1,5,6]
Example: Merge Sort

#include <iostream>

using namespace std;

void merge(int arr[], int l, int m, int r) {

int n1 = m - l + 1;

int n2 = r - m;

int L[n1], R[n2];

for(int i=0;i<n1;i++) L[i] = arr[l+i];

for(int j=0;j<n2;j++) R[j] = arr[m+1+j];

int i=0, j=0, k=l;

while(i<n1 && j<n2) {

if(L[i] <= R[j]) arr[k++] = L[i++];

else arr[k++] = R[j++];

while(i<n1) arr[k++] = L[i++];

while(j<n2) arr[k++] = R[j++];

void mergeSort(int arr[], int l, int r) {

if(l < r) {

int m = l + (r-l)/2;

mergeSort(arr, l, m);

mergeSort(arr, m+1, r);

merge(arr, l, m, r);

}
}

4. Two Pointer Technique

The Two-Pointers Technique is a simple yet powerful strategy where you use two indices
(pointers) that traverse a data structure—such as an array, list, or string—either toward each
other or in the same direction to solve problems more efficiently

Two pointers is really an easy and effective technique that is typically used for Two Sum in
Sorted Arrays, Closest Two Sum, Three Sum, Four Sum, Trapping Rain Water and many other
popular questions.

When to Use Two Pointers:

 Sorted Input : If the array or list is already sorted (or can be sorted), two pointers can
efficiently find pairs or ranges. Example: Find two numbers in a sorted array that add
up to a target.

 Pairs or Subarrays : When the problem asks about two elements, subarrays, or
ranges instead of working with single elements. Example: Longest substring without
repeating characters, maximum consecutive ones, checking if a string is palindrome.

 Sliding Window Problems : When you need to maintain a window of elements that
grows/shrinks based on conditions. Example: Find smallest subarray with sum ≥ K,
move all zeros to end while maintaining order.

 Linked Lists (Slow–Fast pointers) : Detecting cycles, finding the middle node, or
checking palindrome property. Example: Floyd’s Cycle Detection Algorithm (Tortoise
and Hare).

Visualization
Example: Pair with given sum

#include <iostream>

#include <vector>

using namespace std;

bool twoSum(vector<int> &arr, int target){

int start = 0, end = [Link]() - 1;

while (start < end){

int sum = arr[start] + arr[end];

if (sum == target)

return true;

// Move toward a higher sum

else if (sum < target)

start++;
 // Move toward a lower sum

else

end--;

// If no pair found

return false;

int main(){

vector<int> arr = {2,3,3,4,6,8,8,10};

int target = 11;

if (twoSum(arr, target))

cout << "true";

else

cout << "false";

return 0;

5. Sliding Window Technique

Sliding Window Technique is a method used to solve problems that involve subarray or
substring or window.

 Instead of repeatedly iterating over the same elements, the sliding window maintains
a range (or “window”) that moves step-by-step through the data, updating results
incrementally.

 The main idea is to use the results of previous window to do computations for the
next window.
  Commonly used for problems like finding subarrays with a specific sum, finding the
longest substring with unique characters, or solving problems that require a fixed-
size window to process elements efficiently.

Visualization

Example: Maximum sum subarray of size k

#include <iostream>

using namespace std;

int main() {

int arr[] = {2,1,5,1,3,2};

int k = 3, n = 6;

int windowSum = 0, maxSum = 0;

for(int i=0;i<k;i++) windowSum += arr[i];

maxSum = windowSum;

for(int i=k;i<n;i++) {
 windowSum += arr[i] - arr[i-k];

maxSum = max(maxSum, windowSum);

cout << maxSum;

return 0;

6. Hashing Techniques

Hashing maps data to an index using a hash function for fast access.

Types of Hashing

 Chaining

 Open Addressing (Linear Probing)

Visualization (Chaining)

Index 0 → 10 → 20

Index 1 → 15

Example: Frequency Count using Hash Map

#include <iostream>

#include <unordered_map>

using namespace std;

int main() {

int arr[] = {1,2,2,3,1};

unordered_map<int,int> freq;

for(int x : arr) freq[x]++;

for(auto p : freq)

cout << [Link] << " -> " << [Link] << endl;

return 0;
}

7. Dynamic Programming (DP)

Dynamic Programming solves problems by breaking them into overlapping subproblems

Two Approaches

Method Description

Memoization Top-down (Recursion + Storage)

Tabulation Bottom-up (Iterative)

8. Fibonacci using DP

Visualization

F(5)

→ F(4) + F(3)

→ Stored results reused

Tabulation Code

#include <iostream>

using namespace std;

int main() {

int n = 5;

int dp[n+1];

dp[0] = 0;

dp[1] = 1;

for(int i=2;i<=n;i++)

dp[i] = dp[i-1] + dp[i-2];

cout << dp[n];

return 0;
}

9. Knapsack Problem (0/1 Knapsack)

Problem Statement

Given weights and values, select items to maximize value without exceeding capacity.

Visualization

Items: (w,v)

(1,1) (3,4) (4,5)

Capacity = 4

Code

#include <iostream>

using namespace std;

int main() {

int wt[] = {1,3,4};

int val[] = {1,4,5};

int W = 4, n = 3;

int dp[n+1][W+1];

for(int i=0;i<=n;i++) {

for(int w=0;w<=W;w++) {

if(i==0 || w==0) dp[i][w] = 0;

else if(wt[i-1] <= w)

dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);

else dp[i][w] = dp[i-1][w];

cout << dp[n][W];

10. Longest Common Subsequence (LCS)

Visualization

X = ABCD

Y = AEB D

LCS = ABD

Code

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char X[] = "ABCD";

char Y[] = "AEB D";

int m = strlen(X);

int n = strlen(Y);

int dp[m+1][n+1];

for(int i=0;i<=m;i++) {

for(int j=0;j<=n;j++) {

if(i==0 || j==0) dp[i][j] = 0;

else if(X[i-1] == Y[j-1]) dp[i][j] = dp[i-1][j-1] + 1;

else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

cout << dp[m][n];

11. Longest Increasing Subsequence (LIS)

Visualization

Array: [10,9,2,5,3,7]

LIS = [2,5,7]

Code

#include <iostream>

using namespace std;

int main() {

int arr[] = {10,9,2,5,3,7};

int n = 6;

int dp[n];

for(int i=0;i<n;i++) dp[i] = 1;

for(int i=1;i<n;i++)

for(int j=0;j<i;j++)

if(arr[i] > arr[j])

dp[i] = max(dp[i], dp[j] + 1);

int ans = 0;

for(int i=0;i<n;i++) ans = max(ans, dp[i]);

cout << ans;

return 0;