shahjalalshohag/code-library

Templates, algorithms and data structures implemented and collected for programming contests.

This is my personal code library where I compiled almost all the important templates that you will need in Competitive Programming (saying almost just for courtesy). Most of the codes are originally written by me and some of them are collected from others but modified in a cleaner way.

It took me around 4 years to complete the list. Maybe each line is just a line to you but to me it tells a story of the excitements I had while learning those stuffs, the sleepless but fun nights I had to seek knowledge.

Why am I sharing this library?

• Just so that your learning path becomes a bit smoother.
• Knowledge hidden inside my head or codes in a private code-library will be useless when I am dead, so it's better to share those among people before I die.

Also, you can make me happy(as in to pay me) just by giving a star to the repository.

I believe that my coding style is pretty clean and readable, and furthermore, a few problem links are attached to most of the codes so that you can practice those problems. Best wishes, my friend .

Topic List (For this Library, Must Check)

The topic lists for which I have created this library can be found here. It also contains the relevant problems and tutorials of each topic. Upvote the attached blog if you think I have helped you somehow.

code-library's Issues

Looking for Well Structured and Well Documented Code

Most files do not contain generalized and well-documented codes. For example for the following segment tree code:

struct ST {
  int t[4 * N];
  static const int inf = 1e9;
  ST() {
    memset(t, 0, sizeof t);
  }
  void build(int n, int b, int e) {
    if (b == e) {
      t[n] = a[b];
      return;
    }
    int mid = (b + e) >> 1, l = n << 1, r = l | 1;
    build(l, b, mid);
    build(r, mid + 1, e);
    t[n] = max(t[l], t[r]);
  }
  void upd(int n, int b, int e, int i, int x) {
    if (b > i || e < i) return;
    if (b == e && b == i) {
      t[n] = x;
      return;
    }
    int mid = (b + e) >> 1, l = n << 1, r = l | 1;
    upd(l, b, mid, i, x);
    upd(r, mid + 1, e, i, x);
    t[n] = max(t[l], t[r]);
  }
  int query(int n, int b, int e, int i, int j) {
    if (b > j || e < i) return -inf;
    if (b >= i && e <= j) return t[n];
    int mid = (b + e) >> 1, l = n << 1, r = l | 1;
    int L = query(l, b, mid, i, j);
    int R = query(r, mid + 1, e, i, j);
    return max(L, R);
  }
}t;

A better approach would be:

• Add template <typename T> before the struct to make it more generalized for any type.
• Add documentation before every function to explain what the function does.
• Link to some problems where you have tested this structure.

Example PR: #25

Check the whole codebase, you will be able to find lots of files where you can work on similar stuff.

Contribution Steps:

1. Identify Areas for Improvement: Scan through the codebase and identify files or components where similar issues can be fixed or optimized.

2. Fix Issues: Make the necessary changes in a new branch. Ensure that you adhere to the project's coding guidelines and that your changes are well-documented.

3. Open a Pull Request: After completing your changes, please open a pull request for review.

Once your PR is submitted, it will be reviewed and, if approved, merged into the main branch.

Thank you for your contribution!

I want to add the program for Majority element

##Description

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Prime Factorization Bug.

In Number theory dir prime factorization code snippet has a bug i guess its giving this = error: '__uint128_t' does not name a type. dir link(https://github.com/ShahjalalShohag/code-library/blob/master/Number%20Theory/Prime%20Factorization%20Fastest.cpp)

Dijkstra algorithm

Hey 👋 , I want to add dijkstra algorithm to this repo which useful for finding shortest path from source to destination. Please assign it to me under Hacktoberfest tag
Thank you:)

I want to create a program that guesses the unit digit of a number raised to power using power cycle.

Sir please if not already, then assign it to me.

BELLMAN-FORD ALGORITHM

hey i want to add bellman-ford algorithm to the repo. please assign me this issue

I want to make a collection of some most useful algorithms codes at one Place

1)K-way merge Algorithm

2)Stack Reduced Quick Sort

3)Merge sort combined with Insertion Sort

4)Prims, Topological, Kruskal's algorithm

5)DijKstra , Floyd Warshall ,bellman ford algorithm

6)Backtracking
a) Rat Maze
b) N-Queen
c) Sudoku
d) Sum of Subset

7)Activity selection , Huffman Encoding

8. Longest common subsequence , Quick Sort etc

please assign this to me , I am very much Interested to contribute myself in Hacktoberfest_2023 : )

Closest Pair of Points - wrong init of 'pair<int, int> ret' on line 18

Must be pair<int, int> ret = {p[0].y, p[1].y};

issue: Uninitialized variable: `ty` in `Graph Theory/Maximum Independant Set.cpp` file - line 74

Link issue

for (int i = 1; i <= n + 1; i++) {
    int ty; // Uninitialized variable: ty - when i is equal to n+1
    if (i <= n) cin >> ty;
    if (ty == 1 || i > n) {
      for (auto x : se) for (auto y : se) g[x - 1][y - 1] = 1, g[y - 1][x - 1] = 1;
      se.clear();
    } else {
      string s;
      cin >> s;
      if (mp.find(s) == mp.end()) {
        mp[s];
        mp[s] = mp.size();
      }
      int p = mp[s];
      se.insert(p);
    }
  }

Monotonic MinMaxQueue

My Implementation of monotonic Minimum and Maximum Queue:

template<typename T>
class MinMaxQueue {    
public:
    deque<T> q, minq, maxq;
    
    void push_back(T val) {
        q.push_back(val);
        while(!minq.empty() and minq.back() > val)
            minq.pop_back();
        while(!maxq.empty() and maxq.back() < val) 
            maxq.pop_back();
        minq.push_back(val);
        maxq.push_back(val);
    }
    
    void pop_front() {
        T val = q.front(); q.pop_front();
        if(val == minq.front())
            minq.pop_front();
        if(val == maxq.front())
            maxq.pop_front();
    }
    
    T min() {
        return minq.front();
    }
    
    T max() {
        return maxq.front();
    }
    
    T front() {
        return q.front();
    }  

    int size() {
        return q.size();
    }

    bool empty() {
        return q.empty();
    }
};

Tested it on:
Problem: https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
My Solution: https://leetcode.com/submissions/detail/792036375/

References:

• https://cp-algorithms.com/data_structures/stack_queue_modification.html#queue-modification-method-1
• https://www.youtube.com/watch?v=9hd8UFAYa1c&t=1054s

Bug in Bigint template

The Bigint template fails for multiplication of negative numbers. (Checked on Library checker).

However manually changing to positive and assigning the sign later gives AC.

Adding Backtracking folder

I want to create a new folder which includes all Backtracking problems with codes.

Please assign this to me , I am interested to contribute my self in hacktoberfest_23 : )

bug in tangents_lines_from_circle

Great library!
discovered minor bug in tangents_lines_from_circle.

instead of d2 = d.norm() should be d2 = d.norm2()

I want to add algorithm for LIS using binary search

can you please assign it to me?

How was this line declared

I can't understand how did you declare this line?

code-library/Data Structures/Treap.cpp

Line 6 in cf30396

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

Bug

there is a bug on https://github.com/ShahjalalShohag/code-library/blob/main/Number%20Theory/Intersection%20of%20Arithmetic%20Progressions.cpp
intersect(70, 13, 9, 7).first is 44 (its not right taking in consideration that the first element of the first AP is 70)

I want to add Longest palindromic Subsequence

I want to add Longest palindromic subsequence

Can u assign it to me _Hackoberfest_23 : )