/Competitive-Programming

This repository is collection of lot of problems tag wise and their solution coded to help other users, also this contains lot of ready made modules for cp

Primary LanguageC++

Competitive Programming by om-ashish-soni

Disclaimer:

The codes provided in this repository are written based on my personal preferences. Although they are public, I continue to use this repository for participating in contests. Therefore, please ensure that you take appropriate measures to protect your code against plagiarism.

Starter Contests for Beginners

Contests for Newcomers
Contest 1

Websites for Interview Preparation

DSA and Interview Preparation
LeetCode
GeeksForGeeks
InterviewBit
CodingNinjas
Binary Search (currently down)

Golden Resources for Learning

Useful resources for learning
Good Tutorials for Competitive Programming
EKZLib

Awesome Contest Tools

Handy tools for contests
Graph Editor - CSAcademy
OEIS - The On-Line Encyclopedia of Integer Sequences

Codeforces Tools

Helpful tools for Codeforces
Codeforces Randomizer
Codeforces Predictor
Codeforces Practice Tracker
Codeforces Enhancer
Carrot Rating Predictor
Stopstalk
Codeforces Recommender by CodeDrills
Profile Comparator
Codeforces CLI
CP Editor

Note to Myself

  1. AtCoder Standings
  2. Codeforces Contest List
  3. Virtual Judge
  4. Codeforces Profile Comparator
  5. USACO Contests Guide
  6. Codeforces Recommender by CodeDrills

C++ Tricks

  1. Codeforces - C++ Tricks
  2. Codeforces - Useful C++ Tricks
  3. Codeforces - C++ Optimization Techniques
  4. Codeforces - Cool C++ Features
  5. C++ Reference - cppreference.com
  6. LearnCpp.com - C++ Tutorial

Advanced C++ Guides

  1. USACO Guide - Generic Code
  2. USACO Guide - Lambda Functions

Python Tricks

  1. GeeksforGeeks - Differences Between Python 2.x and 3.x

Java Tricks

  1. Java Programming Guide - PDF

How to Read a Problem?

  1. Pay Attention to Problem Statement: Take extra care to read the problem statement correctly. Mistakes in understanding the problem can lead to wrong solutions. For example, distinguishing between "undirectional" and "unidirectional" graphs (undirected vs directed) can significantly impact the approach.

  2. Analyze the Constraints: Understanding the problem constraints can provide valuable insights into choosing the appropriate algorithms and data structures to solve the problem effectively.


Courses

  1. T-414-AFLV Course
  2. Codeforces Educational Courses
  3. KTH Competitive Programming

Implementations

  1. Om Ashish Soni's Competitive Programming Repository
  2. KTH Competitive Programming Repository
  3. USACO Implementations by Benjamin Qi

Other Resources

  1. VisuAlgo - Visualizing Algorithms and Data Structures
  2. Topcoder Data Science Tutorials
  3. CS97SI - Introduction to Competitive Programming from Stanford University

Practice Websites

  1. Codeforces Problemset
  2. AtCoder Contest Archive
  3. Saraswati Online Judge
  4. CodeChef
  5. HackerRank Dashboard
  6. CSAcademy Contest Archive
  7. TLX - Toki Learning Center
  8. Kattis Open

Tag-wise Practice

  1. CSAcademy Tag-wise Practice
  2. Saraswati Online Judge Tag-wise Practice

Practice Guides

  1. USACO Guide - Practicing
  2. Codeforces - Guide to Problem Solving
  3. Informatics Notes - Preparing for Contests

Input Output Guides

  1. Codeforces - Input/Output Guide

Debug Guides

  1. KTH Competitive Programming Repository - Troubleshooting
  2. Codeforces - Debugging Guide

Other Tools

  1. Desmos Calculator
  2. DiffChecker - Compare Text Diff
  3. Geodeb - Geometry Debugger

Important Books

  1. Programming and Problem Solving (PAPS) by USACO Guide
  2. Competitive Programming Handbook (CPH) by USACO Guide
  3. Competitive Programming in C++ by Darren Yao

Common Advice

  1. Practice on Codeforces: Solve a lot of problems on Codeforces that are just above your current rating range.
  2. Prioritize Codeforces: Codeforces is the best platform to improve your competitive programming skills, so spend a significant amount of time on it.
  3. AtCoder: Participate in AtCoder Beginner Contests, which are suitable for beginners and provide valuable practice. You can also try AtCoder Regular Contests.
  4. Codechef: Use Codechef for math and bit manipulation questions.
  5. Codechef Starters Contests: Participating in Codechef Starters Contests can be beneficial.
  6. LeetCode: Solve LeetCode Weekly and Biweekly Contests for practice and warm-up. These contests often have a mix of easy and medium difficulty questions, which can boost your motivation.
  7. Awesome Resources: Explore the following resources for inspiration and motivation:

Tips

  1. Stuck in a Contest: If you feel stuck during a contest, take a short break of 1 or 2 minutes. Wash your face to refresh yourself and then start again with a clear mind.

  2. Can't Improve: If you're struggling to improve, try upsolving. If you can't come up with any ideas, refer to the editorial. If there is an unfamiliar topic, learn it and repeat this process.

  3. How to Boost Performance: Participating in long challenges on Codechef can help boost your performance and allow you to learn various tips and techniques.

  4. Combining Different Approaches to Solve Problems: When faced with a problem, try multiple approaches. For example, if it's a graph problem, start with DFS. If that's not enough, try using disjoint sets. If there's a need for path compression, use it. If the constraints allow, consider using Fenwick trees. This approach helps you combine different techniques to solve problems effectively.

  5. Difficulty with Last 3 to 4 Problems of a Contest: If your basics are clear, practice a lot of problems related to trees, graphs, dynamic programming, and segment trees until you feel satisfied.

  6. Where and How to Practice:

    • Hackerrank is a good platform for beginners to learn a programming language.
    • Once you have a basic grip on a language, move to the problem set on Codeforces.
    • Solve problems on Codeforces with ratings below 1000.
    • Practice problems based on specific topics from the Codeforces problem set.
    • Participate in contests on Codeforces and Codechef.
    • Upsolve problems. If you can't solve a problem within 30 minutes, refer to the editorial. Learn any unfamiliar topics and repeat this process.
    • As your rating improves, continue step 4 and solve problems within the rating range of [your rating - 100, your rating + 100].
    • Keep learning new algorithms and practice implementing them.
  7. How Problem Setters Find New Problems: Not all problems in contests are built from scratch. Many problems are a mixture of multiple problems from resources like the CSES Problem Set.

  8. Getting TLE with String as a Key in Ordered Map: If you're experiencing performance issues with a string as a key in an ordered map, try using a hash map instead. This change may improve the performance.

  9. IDE Recommendation: In competitive programming, it's recommended not to use an IDE. Instead, develop a habit of using a text editor like Vim.

  10. Which Template Should I Use in CP?: There are various templates available for competitive programming. You can refer to the following resource for templates that are useful in competitive coding: Templates Useful for CP

  11. Tips to solve Constuctive :

    1. Writing a brute force script rather than manual solving
    2. Finding a pattern
    3. coding optimized solution corresponding to pattern
    4. Taking care of edge cases.

Improving Sorting (Ruffle Sort Inspired from Second Thread's Code)

Here's an implementation of the Ruffle Sort algorithm inspired by code from the second thread:

static void ruffleSort(int[] a) {
    int n = a.length; // Shuffle, then sort
    for (int i = 0; i < n; i++) {
        int oi = random.nextInt(n);
        int temp = a[oi];
        a[oi] = a[i];
        a[i] = temp;
    }
    Arrays.sort(a);
}

codechef Roadmap

  1. start with array -> practice -> 2 🌟
  2. learn c++ stl or any language similar library, dp -> 3 🌟
  3. disjoint set union , graph, little dsa -> 4 🌟
  4. segment tree -> 5 🌟
  5. Codechef has very nice problems on Bit manipulation So , making good grip over bit manip can help in contest.

Codeforces Suggestion

  1. Codeforces requires speed of solving problems.
  2. Even if you solve only 2-3 problems , but very quickly then , you will get fruitful ratings.
  3. Upsolving is required since the problem pattern might be repeated in future problems.
  4. First two questions are mostly greedy in div -2,3,4 contests. No prior knowledge except programming language is required.
  5. Below is example how upsolving looks like cf upsolving

Troubleshooting Error on Codeforces for Java

If you encounter the error "Source should satisfy regex [^{}]public\s+(final)?\sclass\s+(\w+)" while using Java on Codeforces, follow this guide to resolve the issue: Troubleshooting Java Error on Codeforces

Python: Jumping by 2

You can easily jump by 2 in Python using the range() function with a step size of 2. Here's an example:

for i in range(0, 10, 2):
  print(i)

Lesser-known Resource

Discover a lesser-known resource that can enhance your competitive programming skills: Heap using STL in C++

Avoiding Recursion Depth Problem in Python

To avoid recursion depth problems in Python, you can increase the recursion limit using the following code:

import sys
sys.setrecursionlimit(10**6)

Useful C++ Tricks

Explore a collection of useful C++ tricks to enhance your programming efficiency: C++ Tricks on Codeforces

Feel free to explore these resources to overcome common challenges and improve your competitive programming skills.

README

Welcome to the repository! This README file provides important information and resources related to the project.

Roadmap

You can find the roadmap . It outlines the planned features, milestones, and overall direction of the project.

Codeforces Blogs

For additional information and insights, you can refer to the Codeforces blogs . These blogs cover various topics related to competitive programming and can be a valuable resource for learning and improving your skills.

Note to Self

Please keep in mind the following points:

  • Number theory, bit manipulation, and dynamic programming (DP) are among the most popular topics in competitive programming.
  • In 98% of the contests, at least one of these topics is always included.
  • It is essential to practice these topics extensively to improve your proficiency.

Basic Constraints and Safe Time Complexity

N Big O
For N <= 10 O(2^N) and O(N!)
For N <= 100 O(N^3)
For N <= 10^3 O(N^2)
For N <= 10^5 O(NLogN)
For N <= 10^6 O(N)
For N <= 10^9 O(logN)


nice youtube channels :

channel
Tushar Roy
Striver
CodeNCode
Tech-Dose
Luv
Apna college Placement course
Errichto
William Lin
William Fiset
Algorithms live
benritmicocode
jonathan paulson
Second Thread

Other Nice Repositories

Repository
Code Library by Shahjalal Shohag
Tourist
William Fiset Algorithms
CP by Dhiraj-01
CP-Library by Dhruv Gheewala
Coding Library by Huzaifa
Competitive Coding by Ashish Gupta
Shahjalal's CP Library
Coding Notes by Ankit Priya Rup
Leetcode Questions by fterh
Algo-lib by Saketh Are
Coding Notes by Ankit Priya Rup
Atcoder Library
Competitive Programming by Alexandru Valeanu
CSES by superj6

Important Topic References

Topic Reference Link
Dynamic Programming Video
Mathematics for DSA & CP Video

Helpful Articles

Article Reference Link
Roadmap for Competitive Programming
Modulo Multiplicative Inverse
Random Shuffle

Important Links


Good to Know

  • At maximum, a number can have O(2*sqrt(n)-1) factors, which is the upper bound for the number of factors.
  • A leaf node is a node with a degree less than or equal to 1.

Guides for Writing Clean Code

  1. Google C++ Style Guide

Please refer to the respective links for more information and resources related to coding, competitive programming, and problem-solving.

Vim Configuration

To configure Vim for competitive programming, follow the steps below:

  1. Open the terminal and enter the command: vi ~/.vimrc
  2. Paste the following configuration code into the file:
set number
set tabstop=4
set shiftwidth=4
set autoindent
set mouse=a
colorscheme default
autocmd vimEnter *.cpp map ^B :w <CR> :!clear ; g++ --std=c++17 %;if[[-f Output : ++++++++++++++++++++++++++++++++] a.out ];time ./a.out; rm a.out; if[[-f End : --------------------------------]a.out]<CR>
  1. Press Ctrl+C and then Ctrl+B to compile and run the code.