CommonLounge is a community of learners who learn together. Get started with the featured resources above, ask questions and discuss related stuff with everyone.
Introduction to Graphs (and how to represent them)
I recommend watching the following videos for learning about graphs. These are really well made videos and he covers a lot in these short videos, so if you feel overwhelmed, use the rewind and pause buttons.
Introduction to Graphs
What are graphs? What are different types of graphs (directed and undirected, trees and DAGs, etc)? And examples of using them to model web links, flights between cities, and other things.
In the most of the text/video tutorials,vertices are always( as far as I've noticed) represented by integers ( from 0 to any positive integer). Is this always the case?? I ponder if we're dealing with real life,then vertices would be an object,right??
This discussion is for expanding your array of maneuvers needed to code quickly and efficiently.
The first and most important thing that I'd like to discuss about is the C++ STL. Learning it would enable you to code up an assortment of algorithms and complicated data structures in a matter of seconds.
You can learn to use the C++ STL from the following amazing sites:
Studytonight : Contains syntax and examples for most of the STL containers and algorithms.
Sanfoundry : Shows how to implement what you've learnt in complete programs
Topcoder(Highly recommended) : This place teaches yo...
Number Theory is a topic which you will come across frequently in programming contests. I feel this is a topic which has a lot of resources but these resources are scattered. Therefore, I write this tutorial trying to bring in all the best resources together. There are many people who feel I am not good at Math, can I be a good competitive programmer?. This tutorial is for you guys. Don't hesitate to read it as the material here is presented in extremely lucid form and anyone can understand it. Feel free to ask in case you have any doubts.
In many problems especially in problems where the answer can become very very large, you must have found that they ask you to report the answer modulo 10^9+7. Let us learn more about this modulo operator and it's properties.
Motivation: Given an array of N integers. You have to answer some queries in form (l, r, k). To answer this query you have to print the number of integers less than k in the sub-array array[l .... r].
You should be able to solve the problem in O(log^2 n) per query at least. How? You can use Merge Sort Trees.
Now what is a Merge Sort Tree? Merge Sort Tree is actually a Segment Tree but each node contains a vector. If the range of the node is [l,r] then the vector will contain the elements of array[l...r] but in sorted order.
To solve the above problem we can make a Merge Sort Tree first and go into relevant segments and binary search on the vector that was stored in those nodes to count how many numbers are less than k. This will give O(log^2 n).
I think O(nlog^2 n ) is not an acceptable time limit for this problem. It is only meant to be solved in O(nlog n). I tried writing it using merge sort tree but was getting TLE even with fast io. You can solve it using BIT or persistent segment tree in nlogn time.
Motivation problem: We have a tree consisting of n(<=10^5) nodes. We will consider the tree nodes indexed from 1 to n. We will also consider the first node to be initially painted red, and the other nodes — to be painted blue. The distance between two tree nodes v and u is the number of edges in the shortest path between v and u. We need to learn how to quickly execute queries of two types:
paint a specified blue node in red;
calculate which red node is the closest to the given one and print the shortest distance to the closest red node.
Your task is to write a program which will execute the described queries.
Comments: It does seem like RMQ(Range Minimum/Maximum but on trees. Of course these can be solved using segment trees(Heavy Light Decomposition). But there is a technique which can be used to solved these kind of problems with the same time complexity but shorte...