Misc-Programming

This repository contains various types of programs. Almost all program can compile with C++14. The following files require C++17: "Graph1.cpp", "Range Iteration.cpp"

Contents

• Misc-Programming
  • Contents
  • How to start
  • Tips
  • Useful Data Structures and Programs
  • C++ tips
  • Good code references

How to start

• Learn Competitive Programming In Just One Month For Free | How To Start Competitive Programming
  • https://cses.fi/
  • https://cses.fi/problemset/
  • Guide to Competitive Programming - Learning and Improving Algorithms Through Contests
  • Competitive Programmer’s Handbook - Antti Laaksonen Draft August 19, 2019
• How to start Competitive Programming?
• How To Become Red Coder? (codeforces.com)
  • Summary of the video tips
    1. Practice - solve problems
    2. If you don't know algorithms, you can start to solve problems which have editorials - problems that have an analysis by the organizers. Maybe for the first time you will encounter DFS, then google DFS, solve a few more problems on DFS and you can go back to randomly solving problems.
    3. Choose levels slightly above your comfort zone (i.e. slightly above your level). Not too much above your level, otherwise you won't understand how to solve and will get demotivated. Neither below your level, otherwise there is no learning.
    4. Solve a lot of problems
    5. For beginners and medium level participants - after being stuck for about 20-30 minutes, look at the answer. Read the answer till the end, if you needed.
    6. Once the problem is solved, look at the top/best solutions for the same question to understand how top programmers think and solve the problem.
• Don't Make These Mistakes (1st and 2nd Year)
• How do competitive programmers become so good at problem solving skills ? What is their approach in solving a high level programming question ?
• How smart are red coders ?
• How should one win the ACM ICPC? What efforts should I put forth starting from my 1st year of engineering (IT) ?
• LeetCode
  • A must-read guide for new LeetCode users
    • #comment - Depending on the reason for which you joined LeetCode, this blogs talks about how to make most effective use of LeetCode
  • How to use LeetCode to help yourself efficiently and effectively (for beginners)
    • #comment - Talks about how to use LeetCode features. The below summary covers almost everything.
    • Consistency is very important
    • Focus of continuously improving yourself and your programming
    • Same strategy does not work for all. Feel free to have your own preparation strategy
    • Start with problems that have an editorial already written. These are the ones with a little "document page" icon in the "Solution" column of the problem set.
    • Start with problems that have good reviews. Check the upvotes vs downvotes ratio and then decide whether to solve the question or not.
    • Editorial and Discuss tab will be very useful to know about optimal solutions
    • The blog author strongly recommend "Cracking the Coding Interview" book.
  • How to effectively use LeetCode to prepare for interviews
    • #comment - This was the best blog
    • Use Breadth First (i.e. solve questions of all algorithms and data structures) approach to solve questions instead of Depth First (i.e. solve all easy questions of a topic - say Array/Tree/etc). Pick 5-6 questions from each topic and try to master the basics of the topic.
    • The blog author recommends moving from the "easy" questions as soon as possible, for it's the "medium" level questions that will be asked mostly in interviews
    • Make notes of what you have learnt from a question
    • Read other peoples interview experience to get used to the interview feeling
    • It also has list of Easy and Medium questions created by the blog author
  • Must Read Blogs If Using LeetCode - Important and Useful links from all over the LeetCode
  • Solutions - https://github.com/kamyu104/LeetCode-Solutions/
• Learn Data Structures with Images - https://leetcode.com/explore/learn/
• Compiled Coding Notes - https://github.com/ankitpriyarup/Coding_Notes

Tips

• It is highly suggested to do Competitive Programming in group so that everyone is motivated to continue even after small failures.
• If one participates in a programming contest (e.g. on CodeForces), then it is necessary to solve the questions which one could not solve during the contest (i.e. upsolve questions which one could not solve during the contest).
• One should try to solve problems which are slightly above their capacity but not too hard so that he/she does not get demotivated. Secondly, beginers should try to think of solution for 15-30 minutes, and:
  • If one is able to solve the question, then too they should see the tutorial for the question to see other peoples approach and also view the solution of those people whose code got accepted and took the least amount of time and memory.
  • If one is not able to solve the question, then see the tutorial/solution as beginners have a lot to learn and the brain won't get an idea to implement a new data structure required to solve the problem. And, one should understand the concepts required for the question throughly so that he/she is able to solve similar questions in future.
• Lastly, continue practicing question because if one stops problem solving for just a month, even then the confidence goes down. So, regularly solve question and praticipate in competitions to be confident of your skills.

Useful Data Structures and Programs

1. Competitive Programming Template (Big).cpp
2. Competitive Prog-ramming Template (Small).cpp
3. Graph1.cpp
   • Directed/Un-directed Unweighted Graph
     • Depth First Search (DFS)
     • Breadth First Search (BFS)
     • bipartite_graph_split
     • detect_cycle
     • find_cycle
   • Directed/Un-directed Weighted Graph
     • minimum_spanning_tree_kruskals
     • dijkstras (i.e. Dijkstra's shortest path)
     • bellman_ford
     • floyds_warshalls
     • bfs_0_1
   • GraphAdjMatrix - to store matrix of points
4. Tree1.cpp
   • Depth First Search (DFS)
   • Read Types of trees in data structures
5. Segment Trees.cpp
   • SegmentTree - optimized to space complexity of O(2*N)
     • Methods: size, resize, reset, operator[], build, setval, update, query, query_idx (for prefix sum)
   • SegmentTreeSimple - use complete binary tree and iterative algorithms
     • Methods: size, resize, reset, operator[], build, setval, update, query
   • SegmentTreeSimpleLazy - use complete binary tree and recursive algorithms
     • Methods: size, resize, reset, build, setval, query
6. Binary Index Tree (Fenwick Tree).cpp
   • update
   • query
   • size
   • resize
   • reset
   • operator[]
   • find (returns the index with given cumulative frequency in O(log(n)) time, return -1 if not found)
7. uBigInt.cpp - infinite size unsigned integers
   • Additions operators +, +=
   • Subtraction operators -, -=
   • Multiplication operators *, *=
   • Modulous operators %, %=
   • Binary shift operators <<=, >>=
   • Comparision operators ==, !=, <, <=, >, >=
   • to_dec()
   • to_hex()
   • to_uint64_t
   • factorial
8. Matrix2d.cpp - 2 dimetional array
9. Disjoint Set Union (Union Find).cpp
   • find_set
   • union_sets
   • in_same_set
10. String Data Structures.cpp
    • Trie (Ternary Search Tree - space optimized Trie)
    • Palindrome check
    • Longest Palindrome using Manacher's Algorithm
    • longest_match - finds the maximum number of characters that match between two strings
    • min_edit_distance - the edit distance between two strings is the minimum number of operations required to transform one string into the other.
    • Suffix Tree
    • Suffix Array
11. Prime Numbers.cpp
    • SieveOfEratosthenes
    • SmallestPrimeFactor
    • is_prime - using Fermat's Theorem
    • is_prime_dp - using Dynamic Programming
    • is_prime_simple - using school method
    • Read Primes
12. Policy Data Structures and Hashing.cpp
    • Read C++ STL: Order of magnitude faster hash tables with Policy Based Data Structures
    • Read C++ STL: Policy based data structures
      • Tag — class denoting a tree structure, which we will use. There are three base-classes provided in STL for this, it is rb_tree_tag (red-black tree), splay_tree_tag (splay tree) and ov_tree_tag (ordered-vector tree). Sadly, at competitions we can use only red-black trees for this because splay tree and OV-tree using linear-timed split operation that prevents us to use them.
    • Read Blowing up unordered_map
13. Notes
    • Generally recursive implementations are better than iterative implementation - testing and comparison
      • However, sometime iterative can also be good. It depends on the use case and the constraints under which the problem has to be solved. Example: if we have to traverse a binary tree in O(n) time and O(1) space complexity, then iterative implementation (i.e. Morris Traversal) is better than other recursion (because recursion has O(log(n)) space complexity) and stack based iterative implementations.
    • Lambda Function (C++11 and higher): https://stackoverflow.com/questions/7627098/what-is-a-lambda-expression-in-c11

C++ tips

• IMPORTANT: read the Question carefully
• IMPORTANT: see INPUT limits carefully
• IMPORTANT: if unable to get a solution, then take a small break and think in different direction.
• Should be cautious about
  • int overflow
  • array bounds
  • special test-cases

• int dp[10000]; /* will give better speed as compared to */
  std::vector<int> dp(100000); /* however prefer using std::vector */

• Use iterators to traverse a data structure
• Using #define MOD 1000000007 will give better performance as compared to const int MOD = 1000000007;
• if(a != 0) result++; can be written as result += !!a;
• Use #include<bits/stdc++.h> for competitions but it will drastically increase the compilation time
• The following snippet affects the input/output speed

  std::ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  cout.precision(20); cout << fixed;

• While testing the program for large input on local machine, always use

  g++ -O2 fileName.cpp    # the -O2 will optimize the output file

Good code references

• Note that I have not seen all their codes. I think that they are good in general after taking an abstract level look at them
• https://github.com/trekhleb/javascript-algorithms - this repository give implementation, simple explanation and sources to refer for a particular topic
• https://github.com/indy256/codelibrary/
• http://e-maxx.ru/algo/