Skip to content

Latest commit

 

History

History
377 lines (300 loc) · 14.3 KB

readme-old.md

File metadata and controls

377 lines (300 loc) · 14.3 KB
Raw

Competitive-Programming-by-om-ashish-soni

Disclaimer :

   The codes are written for my suitable choice.
   Eventhought public, this repository is still being used by me for participating in contests. So make sure you take care of your code for plagiarism.

Starter Contests for beginners

Contests for new commmers
Contest 1

Nice Website for interview preperation

DSA and Interview Preperation
LeetCode
GeeksForGeeks
InterviewBit
CodingNinjas
Binary Search (down for now)

GOLDEN MATERIAL :

Nice materials for learning
good tutorials for cp
ekzlib

Awesome Contest Tools :

Nice contest tools
graph editor csa academy
oeis

Codeforces tools :

cf tools
Codeforces Randomizer
Codeforces Predictor
Codeforces Practise Tracker
Codeforces Enhancer
Carrot Rating Predictor
stopstalk
Codeforces Recommander Codedrills
Profile Comparator
Codeforces CLI
CP Editor

note to me :

   1. https://kenkoooo.com/atcoder#/table//
   2. https://not-522.appspot.com/list
   3. https://vjudge.net/
   4. https://cfviz.netlify.app/compare.html
   5. https://usaco.guide/general/contests?lang=cpp
   6. https://recommender.codedrills.io/

C++ Tricks

   1. https://codeforces.com/blog/entry/16262 
   2. https://codeforces.com/blog/entry/57729
   3. https://codeforces.com/blog/entry/10124
   4. https://codeforces.com/blog/entry/15643
   5. https://en.cppreference.com/w/
   6. https://www.learncpp.com/

Advanced C++ guides :

   1. https://usaco.guide/general/generic-code?lang=cpp
   2. https://usaco.guide/general/lambda-funcs?lang=cpp

Python Tricks :

   1. https://www.geeksforgeeks.org/important-differences-between-python-2-x-and-python-3-x-with-examples/

JAVA Tricks :

   1. https://darrenyao.com/usacobook/java.pdf

How to read problem?

   1. Sometimes doing mistake in spelling of problem statement. i.e.
          undirectional graph vs unidirectional graph.
          (undirected vs directed)
      So  it is very essential as well as necessary to read problem statement correctly.
  2. Have a look at constraints , from that idea of which algorithm to apply , can be derived.

Courses :

   1. https://github.com/SuprDewd/T-414-AFLV
   2. https://codeforces.com/edu/courses
   3. https://github.com/kth-competitive-programming/kactl

Implementations :

   1. https://github.com/om-ashish-soni/Competitive-Programming
   2. https://github.com/kth-competitive-programming/kactl
   3. https://github.com/bqi343/USACO

Other Resources :

   1. https://visualgo.net/en
   2. http://www.topcoder.com/community/data-science/data-science-tutorials/
   3. http://stanford.edu/class/cs97si/

Practise Websites :

   1. http://codeforces.com/problemset
   2. https://atcoder.jp/contests/archive
   3. https://saraswati-online-judge.vercel.app/
   4. https://www.codechef.com/
   5. https://www.hackerrank.com/dashboard
   6. https://csacademy.com/contest/archive
   7. https://tlx.toki.id/
   8. https://open.kattis.com/

Tag wise practise :

   1. https://csacademy.com/contest/archive
   2. https://saraswati-online-judge.vercel.app/

Practise Guides :

   1. https://usaco.guide/general/practicing?lang=cpp
   2. https://codeforces.com/blog/entry/53341
   3. https://aryansh.gitbook.io/informatics-notes/usaco-specific/preparing-for-contests

Input Output Guides :

   1. https://codeforces.com/blog/entry/5217

Debug Guides :

   1. https://github.com/kth-competitive-programming/kactl/blob/main/content/contest/troubleshoot.txt
   2. https://codeforces.com/blog/entry/64993

Other Tools :

   1. https://www.desmos.com/calculator
   2. https://www.diffchecker.com/
   3. https://github.com/lukakalinovcic/geodeb

Important Books :

   1. https://usaco.guide/PAPS.pdf
   2. https://usaco.guide/CPH.pdf
   3. https://darrenyao.com/usacobook/cpp.pdf

Common Advice :

   1. Practise a lot problems on code forces of just above your rating range.
   2. Codeforces is only the site that will improve competitive programming , so give priority and spend a lot of times on it
   3. Next is atcoder , give atcoder beginner contest are really nice for beginners and to practise.
   4. You can also give atcoder regular contest.
   5. Use Codechef for maths and bit manipulation question.
   6. You can give codechef starters contests are good.
   7. Leetcode weekly and biweekly can also be given in order to practise as well as warm up, since 3/4 questions are easy and medium , so it will improve your motivation.

Awesome Resources :

   1. https://codeforces.com/blog/entry/23054
   2. https://www.vplanetcoding.com/courses

tips:

1. stuck in contest :

   take 1 or 2 min break, wash face and start again with freshness

2. can't improve :

   try to upsolve, no idea comming see editorial and if un-none topic learn it, repeat this

3. how to boost performance:

   always and almost long challanges on codechef helps to boost performance and learn various tips and techniques

4. how to combine different approach and solve problem :

   let's say there is a problem and you performed below steps
   1. the problem is of graph , dfs -> not enought to solve a problem ?
   2. using disjoint set -> yes -> but tle
   3. using path compression -> yes -> but wrong answer on some edge case
   4. oh , look at the constraints , can we use fenwick tree? yes -> Solved -> AC
   these are the steps that how to combine different approaches

5. Can not solve last 3 to 4 problem of contest :

   If your basics are clear , then you need to practise a lot of problems of tree,graph,dp, segment trees,
   until you feel satisfied enough

6. Where and how to practise :

   1.always hackerrank is good to learn a language for beginners
   2. after having little grip on 1 language, go to codeforces problem set
   3. on codeforces problem set solve problem of rating < 1000
   4. solve topic wise problem on codeforces problem set
   5. give contest on codeforces and codechef
   6. upsolve problems , if can not solve in 30 mins , see editorial, if unnone topic , learn it, and repeat this
   7. after rating growth, repeat  step-4 and solve problems of rating range [your rating -100 , your rating + 100]
   8. keep learning new algo and practice them

7. How problem setters every time finds and puts new problem in contest :

   see , its not that every problem was built from scratch , 
   most of the problems in contests are mixture of more than one problem of below cses sheet.

8. Getting TLE while using string as a key in ordered map ?

   Try to use it with hash map, might performance be improved.

CSES SHEET : cses sheet

8. Which ide should i use ?

   Don't use ide in competitive programming , make a habit of using vim editor.

Improving sorting ( Ruffle Sort inspired from second thread's code) :

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

vim-configuration

   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>

Note :

do below commands :

  vi ~/.vimrc

  //then write above code of vim-configuration

  press ctrl-c and then ctrl-b to compile and run the code

vim is the one of the best suitable editor for competitive programming in the world.

9. Which template should i use in cp?

   Oops , there are two much templates, look below reference.

templates useful for cp

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

Error on codeforces for java : Source should satisfy regex [^{}]public\s+(final)?\sclass\s+(\w+).

https://codeforces.com/blog/entry/98846

python jump by 2

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

You might not know this

https://www.geeksforgeeks.org/heap-using-stl-c/

how to avoid recursion depth problem in python :

sys.setrecursionlimit(10 ** 6)

C++ tricks :

https://codeforces.com/blog/entry/15643

roadmap :

https://blog.shahjalalshohag.com/topic-list/

cf blogs :

https://codeforces.com/catalog

note to me:

  • number theory , bit manip and dp are most popular,
  • in 98% of the contest atleast one of them is always there,
  • please practise more and more

Some basic constraints and the safe time complexity :

N Big Oh
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) [ Sorting/Greedy Algo]
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 repos :

repo
code library
Tourist
William Fiset Algo
dhiraj-01 CP
CP-Library dhruv gheewala
Coding library huzaifa
Ashish Gupta
Shahjahals cp lib
Coding Notes
Leetcode questions
Algo-lib
Coding notes
Atcoder library
Alexandru Valeanu
CSES

important topic reference

topic ref link
Dynamic programming
Maths for dsa & cp

nice articles

article ref link
Roadmap for cp
modulo multiplicative inverse
random suffle

Important links :

https://leetcode-questions.herokuapp.com/

Problem sheet :

https://cses.fi/problemset/

contest :

https://clist.by/

good to know

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

Guides for writing clean code :

   1. https://google.github.io/styleguide/cppguide.html

Roadmap

number theory and combinatorics

topic ref link
prime number
topic ref link