Data Structures and Algorithms Practice

Introduction

This repository contains my solutions to algorithmic problems. Main language is C++

Topics included(Some problems may not be listed here):

1. Basic Algorithms: LC/383

   • Sorting: kattis/sortofsorting(E), CF/1808B(M), USACO/786(M, time interval), LC/881, USACO/713, USACO/1251, USACO/787, CSES/1164, CSES/1074, LC/973, LC/75, USACO/738, CF/104417G, Kattis/downtime, USACO/1064, LC/179
   • Binary Search: VNOJ/nksgame(M), CF/1201C(M), USACO/666(E), CSES/1085(M) (similar to LC/1011), USACO/690(M), USACO/858(M), CF/424B, CSES/1620, HackerRank/minimum-loss, CF/1117C, VNOJ/ndccard, CF/283911A, CF/283911B, CF/283911C, CF/283911D, CF/283932A.cpp, CF/283932B, USACO/380, LC/875, LC/278, SPOJ/JNEXT, LC/436, CF/1624D, USACO/1303, CF/283932C, CF/283932E, CF/1077D CF/702C, USACO/594, USACO/992, LC/74, LC/33, LC/981
     • Minimax: CF/285083A, CF/285083B, CF/285083C, CF/782B
     • Maximal Average: CF/285069A
     • Find the K-th Element: CF/285084A
   • Greedy: CSES/1090, CSES/1629(E), CF/1418C(M), CF/1338A(M), CSES/1630(M), kattis/doubleup, LC/948, LC/45, LC/134, USACO/1301, USACO/689, CSES/1073, CSES/1632, USACO/1084, USACO/573, USACO/1062, UVA/410, UVA/1062, CF/762B, USACO/835
   • Complete Search: CF/863B, USACO/963(M), CF/574B, USACO/736, USACO/615, USACO/712, LC/638, CF/831C, CF/1914C, USACO/639
   • Backtracking: CSES/1623(E), CF/1097B(E), CSES/1622(M), LC/77, LC/51 (NQueens), USACO/1276, SPOJ/ALLIZWEL, LC/78, CSES/1624, CF/839C
     • Permutaion: LC/46
   • Simulation: USACO/891, USACO/855, USACO/568

2. Data Structures:

   • Stack: kattis/evenup(E), SPOJ/ONP(E)(transform algebraic expression into RPN), LC/20, LC/150, UVA/1062
     • Monotonic Stack: LC/496, SPOJ/SSAM219G, LC/85, LC/739, CSES/1645
   • Queue: UVA/10901, CF/644B
   • Sets and Maps: CSES/1091(E, use multiset), USACO/964(E), USACO/687(M), USACO/831, CSES/1640, USACO/667, CSES/1163, CF/518B, LC/347, USACO/1107, CSES/1188, CSES/1632, CF/616D, LC/811, SPOJ/PRO, CF/831C, CF/104417G, kattis/conformity, kattis/candydivision, LC/49, Kattis/cd, LC/325
     • DAT: UVA/10260
   • Heap(PQ): USACO/690(M), LC/1046, LC/853, CodeChef/RRATING, USACO/859, kattis/numbertree, UVA/1203, AC/abc214_e, UVA/11997
   • DSU: CSES/1676, LC/128, VNOJ/colquery, USACO/646, CF/104C, LC/305, CF/289390A
   • Segment trees: CSES/1649, CSES/1648, CF/273169C, CF/380C, VNOJ/gss, VNOJ/qmax2
   • Fenwick trees: csa/swap_pairing
   • Indexed set: SPOJ/INVCNT
   • Sparse Table: CSES/1647
   • Sliding Window: LC/239, CSES/1141, CSES/2428
   • Minimum Stack / Minimum queue: VNOJ/mink, Kattis/bungeebuilder

3. Two pointers: VNOJ/nksgame(M), CSES/1090(E, Greedy, Sorting), LC/11, VNOJ/ndccard, VNOJ/sopenp, LC/56, CF/307092A, CF/307092B, CF/307092C, CF/307093A, CF/307093B, CF/307093C, CF/307093E, CF/307093F, CF/701C, CF/616D, USACO/738, CF/307093D, CF/307094C, marisaoj/92, CF/307094A, CF/307094B, CF/307094E, CF/762B, CSES/1641, LC/88, LC/340, LC/1438

4. Graphs:

   • Graph Traversal: LQDOJ/4601(E), SPOJ/BCDAISY(E), VNOJ/nkguard(H), USACO/965(M), CSES/1666(E), CSES/1668(Bipartiteness check), USACO/668(E), USACO/574(M), USACO/944(E), kattis/birthday, LC/1319, vjudge/Gym-102433C, LC/994, SPOJ/CAM5, USACO/940, USACO/1159 LC/542, USACO/644, CSES/1682, USACO/992, SPOJ/ALLIZWEL, UVA/11749, USACO/669
   • FloodFill: SPOJ/UCV2013H, SPOJ/BCLKCOUN, USACO/895, USACO/380, CF/1365D, USACO/570
   • Shortest Path: CSES/1667, kattis/shortestpath3, CSES/1672, CF/295B, CSES/1671, USACO/969(min cost max flow), LC/743, SPOJ/MICEMAZE, SPOJ/TRAFFICN, CSES/1195, CSES/1193, CC/AUG18-REVERSE(0-1BFS), SPOJ/ELEVTRBL, UVA/10557, LightOJ/1174, VNOJ/qbschool
   • MST: CSES/1675, kattis/cats, UVA/10397 (mst variants)
   • Graph Two Coloring: UVA/10004, USACO/920, CF/862B, CF/1176E
   • Topo Sort: CSES/1679, LC/2115
   • Cycle Check: CSES/1678, DMOJ/acsl1p4, LC/207, beecrowd/1610
   • Successor Graphs:
     • Floyd: CF/1137D, CF/1020B, CSES/1751

5. Dynamic Programming: CSES/1746(M), AC/dp_b(E), CF/1418C(M), CSES/1745(E), USACO/574(M), USACO/993(M), CSES/1093(E), USACO/694(M), VNOJ/nkrez(LIS variation)(E), VNOJ/nkcable(E), CSES/1639(E), LC/221, UVA/11450, UVA/507, LC/740(house robber variation), LC/983, UVA/108 (Kadane on 2D), kattis/commercials (Kadane on 1D), AC/dp_i, CSES/1145, UVA/10130, LC/714, AtCoder/dp_k, SPOJ/COINS, LC/313, CF/909C, LC/45, LC/62, LC/322, Timus/1009, UVA/11137, SPOJ/BYTESM2, SPOJ/ACODE

   • Bitmask DP: CSES/1690, VNOI/lem3, AC/dp_o
   • DP on DAG: CSES/1680, CSES/1681
   • 0-1 Knapsack: LC/474
   • DP on string: LC/72, LC/139

6. String: LC/125, LC/271, LC/811

   • KMP:
   • Trie: SPOJ/ADAINDEX

7. Prefix Sums: USACO/595(M), CSES/1662(similar to USACO/595), CSES/1619(M), CSES/1661(E), USACO/572, kattis/apivotalquestion, CF/909B, LC/253, LC/53, LC/238, USACO/715, SPOJ/HAYBALE, CF/1826D, marisaoj/63, marisaoj/60, marisaoj/66, USACO/691, USACO/787, USACO/645, CF/1398C, CSES/1650, LC 325

   • 2D pref: CSES/1652, USACO/1063
   • Divisibility of subarray: LC/974
   • Difference Array (Inc/Dec Points): CF/816B, CF/295A, CF/102951D, CF/1000C, marisaoj/70

8. Bit Manipulations: CF/1097B(E), CF/550B(E, subsets), CF/1556D(H), HE/mattey-multiplication-6(E), AC/abc295_d(M), LC/136, UVA/11933, UVA/12571, LC/201, LC/371, AC/abc365_e, CF/1872E

9. Tree Algorithms: CSES/1674, USACO/968, USACO/788, USACO/1062

   • Tree diameter: CSES/1131, CSES/1132, CF/755C, LC/310, SPOJ/BENEFACT
   • Euler Tour: CSES/1137
   • LCA: CSES/1688, CSES/1135

10. Geometry: CF/100168L, CF/100168D, CF/100168F, CF/100168G, CF/100168I, CF/100168H, CSES/2191, CF/1846D

11. Math:

    • Divisibility: CSES/1713, LC/1492
    • Modular Arithmetic: CSES/1095, CSES/1712, UVA/10489
    • Combinatorics: CSES/1079
    • Primes: LC/204
    • Other: CF/515B, CF/909D, LC/202

12. Others:

    • Small to Large merging: CSES/1139

13. Ad Hoc: USACO/832, USACO/915, USACO/894

14. Rectangle Geometry: USACO/567, USACO/759, USACO/783

15. Trees: LC/226, LC/104, LC/543, LC/110, LC/100, LC/235

16. Intervals: LC/57, USACO/896

17. LinkedList: LC/206, LC/143, LC/146, LC/116, UVA/11988

## STAT

* beecrowd : 1 
* CodeChef : 2 
* CSES : 64 
* Codeforces : 82 
* Leetcode : 83 
* HackerEarth : 1 
* LightOJ : 1 
* OJ.uz : 0 
* HackerRank : 1 
* SPOJ : 20 
* LQDOJ : 1 
* vjudge : 1 
* UVA : 19 
* USACO : 67 
* Timus : 1 
* AtCoder : 9 
* marisaoj : 5 
* csacademy : 1 
* Kattis : 19 
* Contest : 28 
* DMOJ : 1 
* VNOJ : 13 
* Total number of problems: 420