README.md

Week 2 | Competitive Coding

Introduction

Programming is a challenging role and once you enter this field you will encounter new challenges and you may have to solve some problems which no one has solved before or their solution doesn’t exist anywhere. At that time you are expected to come up with a solution in the least possible time using your problem-solving and logical ability.

Competitive Programming is a sport! Take any sport, let’s consider cricket for that matter, you walk in to bat for the first time. Swing and a miss, do it couple of times and you’ll eventually hit one over the ropes. Now, consider a programming contest as a game of cricket, metaphorically. Compile a code and submit, you may get a WA (Wrong Answer). Make changes to code and eventually you will get your first AC (Accepted/Correct Answer).

Many programmers argue that the problems in competitive programming do not relate to the real life programming work. For the most part, it is true. Then why do we do it? Because it makes you a better programmer. How?

• Time limit always makes you write time efficient solutions.
• Critical test data helps you write correct solutions, in one go!
• Further it makes you great at debugging code.
• Hard problems makes you break down the problem into chunks, solve them individually and bring it all together to solve the main problem.
• A lot of big companies like Google, Facebook. Microsoft, Amazon hires through competitive programming

Yes, competitive programming is not the only way to master these qualities but it is one of the best ways to do so. Give it a shot, if you enjoy it, it’s worth it. You will be rewarded with objective benefits.

OK...So how do I start?

Head over to this WnCC Wiki Article to get started with your journey on Competitive Coding.

For those who are new to this domain & wish to learn more about different Data Structures & Algorithms, check out the Excellent Resources > Algorithms section of the above article.

Ready to Practice? Check out these Tutorials & Problems

Competitive Coding is all about learning & practicing. To help you get hooked to CC, here are some resources along with a curated list of problems for you to practice:

• Refer to this site for standard code templates
• If you feel you don’t understand a topic and need more practice for that topic , here is a topic wise list of problems

Recommended Problems:

Note: Most of the problems have editorials or tutorials , also you could refer to submissions for a problem to understand code implementation , but first try to do these problems on your own after reading the relevant topics.

Easy problems

• Some Ad-hoc Problems

  • Problem: Watson asks Does Permutation Exist
  • Problem: Prefix Numbers
  • Problem: Red Blue Green Balls (keteki)
  • Problem: Game of Bullets (Read about Nim game)
  • Problem: Black And White Cells

• Binary Search

  • Problem: Aggressive Cows
  • Problem: Multiplication Table

• Strings

  • Tutorial: Read about Prefix Sum Array and their uses
  • Problem: Make Palindrome

• Stacks

  • Problem: Largest Rectangle in Histogram (Try a O(n) solution)

• Greedy Algorithms

  • Problem: Array Splitting
  • Problem: IPC Trainers

• Dynamic programming(DP)

  • Problem: Longest Regular Bracket Sequence (Stacks + DP)
  • Problem: Contest Setting [Problem C > download pdf of problem statements and look for this problem > to submit just click on submit code and submit under C]

Intermediate Problems

• Tree

  • Tutorial: Lowest Common Ancestor - Binary Lifting
  • Problem: Marathon on a Tree

• Djikstra's Algorithm

  • Problem: AND on Graph

• Convex Hull Trick:

  • Tutorial: A Primer on the Convex Hull Trick
  • Problem: Hit the Coconuts

• Convex Hull

  • Tutorial: Graham's Scan for Convex Hull Construction
  • Problem: Save The Trees (Easier)
  • Problem: Mancunian Candidate Master Forever

• Disjoint Set Union (DSU)

  • Tutorial: Read about Kruskal’s Algo implementation using DSU
  • Problem: Gears

• Binary Indexed Tree (BIT)

  • Tutorial: Find Number of Inversions in an Array using BIT and merge sort
  • Problem: Bye, inversions!

• Square Root Decomposition

  • Tutorial: Applications of Square Root Trick
  • Problem: Just Update and Print the array

• Mo’s Algorithm

  • Tutorial: Mo’s Algorithm
  • Problem: Traffic Count (Mo’s algorithm + BIT)

• KMP/Z-Algorithm

  • Tutorial: Z-Algorithm
  • Tutorial: KMP Algorithm
  • Problem: Pattern matching

• Tries

  • Tutorial: Tries & Example Problems
  • Problem: Alice and Bob play Contact

• Dynamic Programming

  • Bitmasks, Subsets and Digit DP
    • Tutorial: Dynamic Programming and Bit Masking
    • Tutorial: Digit DP
    • Tutorial: DP over Subsets
    • Problem: Pen Pineapple Apple Pen
    • Problem: Cardinality
  • DP on Trees
    • Tutorial: DP on Trees - 1
    • Tutorial: DP on Trees - 2
    • Problem: Tree Height

Advanced Problems

• Segment Tree + 2-Pointers

  • Tutorial: Using the 2 Pointer Technique
  • Problem: Mei Mei and dress

• Dynamic Programming

  • Tutorial: DP over Subsets
  • Problem: Disconnecting Cities
  • Hint: DP over Subsets [think about solution close to O(3^(n-k))) (3^n operations are needed if you want to iterate through all subsets of set S for every S , where S is a subset of X , size of X is n. Proof : It is summation N_c_i * 2^i = 3^N)]

• Graphs (Strongly Connected Components, Topological Sort, Binary Search)

  • Problem: Visiting Friends
  • Problem: Chef and Roads
  • Problem: Crypto Trading

• Number Theoretic Transform (NTT)

  • Tutorial: Prufers Code
  • Tutorial: Polynomial Multiplication using NTT
  • Problem: High Interview
  • Problem: Trees and Degrees

• 2-Satisfiability Problem (2-SAT)

  • Tutorial: 2-SAT Algorithm
  • Problem: Constrained Selection
  • Problem: Vertex Cover

• Flows

  • Max flow (Simple)
    • Tutorial: Maximum Flow Introduction
    • Problem: New Friends
  • Minimum Cost Maximum Flow
    • Tutorial: Minimum Cost Maximum Flow
    • Problem: Bus Routes

• Heavy-Light Decomposition

  • Tutorial: Heavy-Light Decomposition
  • Problem: Adi and the Tree