Light

dragonslayerx / competitive-programming-repository Goto Github PK

View Code? Open in Web Editor NEW

431.0 25.0 155.0 150 KB

Competitive Programming templates that I used during the past few years.

License: MIT License

C++ 99.98% Batchfile 0.02%

competitive-programming data-structures algorithms algorithms-implemented dijkstra segment-tree floyd-warshall bellman-ford-algorithm biginteger graphs

competitive-programming-repository's Introduction

Competitive-Programming-Repository

Collection of algorithms and data structures in C++ used widely in Competitive programming contests.

The following topics are covered:

Range Updates and Queries

Range Aggregate Queries :
- Binary Indexed Trees (BIT) :
- Segment Trees (SegTree) :
- Merge Sort Trees :
  - Merge sort trees
  - Merge sort trees - Order Statistics
- Sparse Table :
  - Range Minimum Query
- Mo Algorithm :
  - Mo Algorithm - Arrays
Dynamic Programming :
- Dynamic Programming Templates :
  - Digit DP / Bitwise DP
- Standard DP Problems :
Graphs :
- Single Source Shortest Path Algorithms :
- All Pair shortest path :
  - Using Binary exponentiation
  - Floyd Warshall
- Cycle Detection :
  - Cycle detection in Undirected/Directed Graphs
- Minimum Spanning tree :
  - Kruskal Algorithm
- Topological Sort / Strongly Connected Component :
  - Topological Sort
  - Strongly Connected Component
- Maxflow/Matching :
  - Hopkroft Karp Max Matching
  - Dinic Max Flow
- Misc :
Trees :
- Ancestor queries :
  - Lowest Common Ancestor
  - Kth Ancestor
- Path queries :
- Misc :
  - Diameter of Tree
  - Preorder/Postorder stamps, Is it in Subtree?
Binary Exponentiation :
- Calculate n^m using Binary exponentiation
- Solving Linear Recurrences
Strings :
- String Algorithms :
- String Data Structures :
  - Suffix Array *
Sorting :
- Merge Sort
- Quick Select
Fast Input/Output, String/Integer Conversion :
- Fast Input/Output
- String/Integer Conversion
Misc. Data Structures :
Persistent Data Structures :
- Persistent Segment Trees (SegTree) :
  - Persistent Segment Tree
  - Persistent Segment Tree - Order Statistics
Number Theory Algorithms :
- Primality Check :
  - Fermat's Primality Check
- Sieve :
- Polynomial Multiplication :
  - Fast Fourier Tranform
  - Karatsuba
- Misc :
Computational Geometry :
- Convex Hull
Misc :

competitive-programming-repository's People

Contributors

Stargazers

Watchers

Forkers

agarwalnaimish shashipk sangramsam sayanmandal hussainmoiz39 jameskumar arnabbir utk3995 prakharsvnit sundarrinsa harmanjeet-singh sunnygkp10 vishvanath45 ydeepak1889 abhishekagrawal1995 thunder-blade kartikey54 sandeepgupta007 ankur-a jainaman1398 nimitbhardwaj ckblau hmntptwl ankitkesarwani achintmi sun1lksh avvinci desidia akhandmishratruth interviewpre sainiarpit12 atulsinha007 rohitthapliyal2000 hujiaogen sachin-bisht ugurkap monir06 tripmani bdehri ailyanlu1 abhiy13 mfrigillana shaily20 malvikabhalla99 nadim-mahmud niazbinsiraj divayjindal95 persiststudy adityaxxx chucky122 bingyingl yj1399 manan008 subhahu123 neo4reo adarshrana205 wuyuanmm shipleyxie dragon-slayer-in-training jonesnapoleon leonardosu sajidnwar psakila souraavv ankitsri98 sagsango fresher001 carlosal1015 anukkrit149 bebatman cutup195 jewel-cse amberprice-stack hanrick2000 rajpolu gauravk268 nihal-mishra apoquinto ashutosh210798 mradulrathore pranjalwalia makjn10 tianyouzzz adi120 woorimlee sksinghl498 ankitanvesh kshitij3199 saarthakag janubalraj suryaans mds10 ksi7 xowl yashsaxena9 purvansh11 omega07 devjyoti29 cp-solutions praj41

competitive-programming-repository's Issues

Requirement for new codes.

This library is not exhaustive as it still needs several key algorithms and data structures which are widely used in Competitive Programming. The lack is partially due to my lack of knowledge about them or
my laziness to implement and test them.

I'm listing some of the key algorithms here which this library needs.

A simple concise implementation of Centroid Decomposition, Bridge trees.
Knuth Morris Pratt (KMP), Manacher, Aho corasick : One can find an obselete code of kmp in obselete folder, I have used it several time but code is not concise.
A library for Computational Geometry including some key algorithms like finding convex hull of a set of points.

Any new cool completive programming template is also welcome ! Please report bugs in case u get one during using any of the template.

I would like to invite competitive programming enthusiasts to contribute to this library and let the knowledge grow. :)

src/bigint_library.cpp mis behavior with value 0

If I create Bigint with value 0. stream operation and logical operations seems not work properly. like the example below:

int main() {
    Bigint A("0"); // Construct Bigint using string representation
    Bigint B(0); // Construct Bigint using integer representation
    Bigint C("456789");
    cout << A * B << endl; // Overridden ostream
    cout << A * B + C << endl; // Chaining operations
    cout << (A > B) << endl;
    // logical operations
    if (A > B) cout << "A is greater than B" << endl;
    else cout << "B is greater than A" << endl;
}

Output:


456789
1
A is greater than B

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.