Coding Start Up!

I recently uploaded a dynamic programming video for those wanting to learn dynamic programming and are bored of the easy example videos. This has real content!  

Hi everyone, I have opened a new youtube channel where I will post solutions to different Olympiad in Informatics problems from sources like POI/BOI/CEOI/IOI/JOI and more. Check out my first video here . I am looking forward to posting 3-4 videos per week. Don't forget to like and subscribe!

Hi guys, I have discussed here the problems of Codechef April Ltime 2020. First 4 probs. Next 2 probs. Hope you like them :) 

Hi guys, Recently, I worked with Codechef, where I was the editorialist of the April Cook-Off Contest, 2020. Here is a link to the contest . I wrote the editorials for all the seven problems, simulating the way in which I myself think about them. After contest, me and Teja Vardhan Reddy  discussed the problems. Click to see!

Its someday of the week. I am in Germany. I wake up in the morning. Open messenger. Adhyyan has asked us to try Potemkin Cycle from CEOI 2015 day1. I ignore it for the day, but again the next day there is some discussion about it in the group. I download and open it too. A biggg mistake. Problem: find any cycle with >3 nodes so that there are no edges between 2 nodes in this cycle unless they are consecutive nodes. (Chordless cycle ?!).   N=1000. M=100,000 Simple enough statement. How hard can it be. Its the next day morning, and I start thinking on it. Have a few ideas but quickly discard them. Finding a cycle and checking is ofcourse exponential. Can the solution be randomized? Maybe. Who knows. Meanwhile it see that adhyyan has already seen the editorial, and coded. WA. Anay meanwhile reads it, and after a few minutes (as always) says he has got it. PMing Adhyyan.I have another wrong idea : fix 1st and 3rd node of cycle and see if a possibke 2nd and 4th no...

I got started into programming through game development. Started off in Qbasic, which was then being taught in our school. This was towards the end of my 7th grade. Till then, I knew as much about programming as any of my classmates. Me and two of my friends wanted to make a pingpong for our annual exhibition that was up in about two months. However, after two days, the other two gave up. I didn't. It seemed interesting, and a challenge, so I looked up a lot of stuff on the internet, and the most important was how to account for the time delay for the game loop. If I recall correctly, I made use of a sound command, which played a frequency for a certain amount of time, so all the time the game played, there was a low humming noise. Wierd but okay. Also, I remember that I wrote the full code for the pingpong in pen and paper. Ofcourse, there was one user and one computer, and the computer had some wierd heuristical movement, and then the ball also had some randomised speed changes ...

Rough Sketch of How Things Work I wont be going into the exact details of how things work, mostly because it has been about 2 years since I stopped working on this particular game, and have mostly forgotten how things were supposed to work.  As I have mentioned already in some previous blog, there are several GameEngines, with a specific task. The most important one by far is the GameEngine. The engines work alongwith the GameLoop.  What happens is that after the gameloop is started, it pings all the engines to update themselves and render their new forms to the GameWindow. I will only go into how the gameEngine is updated.  Firstly, there are two modes in which the GameEngine(henceforth referred to as GE) can be in :  Map mode or inventory mode. Basically, in the map mode, the map is shown and the player can move about, attack enemies, collect and place items in the backpack. The inventory mode is basically the backpack. Here you can do stuff to th...

What is MongoDb? MongoDb is a opensource database, that stores data in a document-oriented data model. It is what an example of what is commonly known as a NoSQL database. But let's get a bit thorough on this.  Normally, we are usually introduced to Relational Databases, like MS Access. Those are primarily SQL based languages. They have tables in which data is stored. Each table has multiple rows, and each row has multiple columns or fields. The data stored follows a well defined schema. Moreover, relations can be set-up between various tables, so that redundant data is not stored. One of the main advantages is that we can thus change the data in only one location and the effects are observed everywhere. Also, due to the presence of a schema, we know beforehand what all fields exist in the tables. But enough about Relational/SQL databases.  MongoDB, however is very different from the setup. Instead of tables, it has what are called as "Collections", though o...

What This Post Is About: Disclaimer : I will assume the reader is familiar with basic path-copying persistance. Here I will mostly elaborate some usecases of persistance, as these are ussually not given in a blog that teaches persistance. Note that these are mostly Competitive-Programming specific usecases. Getting Started : Persistance is mostly used when there are multiple query parameters. For example, if in a segment tree (as the most common usecase of persistance is in segment trees) if we have a query like (L,R,X) where X is some parameter, we would usually store a lot of information in each node and then binary search some information using the value X, in all the nodes that we would reach that would satisfy the (L,R) bound while traversing the segment tree, like we do in a merge sort tree. Persistance serves as an easy replacement for these types of problems, where it can reduce a O(logn) factor from our time complexity, at the cost of adding a O(logn) facto...

Overlapping Ranges First, suppose we have the following problem: We are given some ranges of the form [L,R] For each query we will be given a range [QL,QR] and we will have to report the count of all the ranges that lie completely within this range. In an update, we can add/delete a new range Main Idea:  The main idea that is not easy to come up with, and could  seem as being an overkill for this but is useful for a variety of problems, of which this example is just a simple case. We are given ranges in a 1D numberline. The crux is that we want to convert these ranges from a 1D line segment to a 2D point. How? Well, for each range that we are given [L,R] just define a point as (x=L,y=R). Thus the updates are basically just adding or deleting points. And the queries? Well, define the query as a point P(Ql,Qr). Now we just have to count the number of points whose X-coordinate is more that that of P and whose Y-coordinate is less than that of P. Thus forming a ...

Merge-Sort Tree I'll start with this because this is quite useful, but does not have much material on it in the internet. The construct is simple enough. First, build a normal segment tree Wait! don't finish building it :P . Instead of store a single value in a node, we store a vector of values. When we merge two nodes, we do a 2-ptr on the vectors to build our resultant vector so that the sorted order is preserved. During queries, we just go down to our terminal nodes and usually do a binary search on the values. Proof of space and time complexity of building is very similar to merge sort. Query time is O(n log² n) (since we normally do an extra binsearch in each of the terminal nodes, which there are O(logn) overall) Just to give an example, suppose we are given an array of size N and there are Q queries each of which gives a L,R and K and asks how many values in range L to R are less than K. For this, first create a merge-sort tree where each node...

The Vanilla Method Let's take the given problem: We have some sets as U = {S1,S2,S3....Sn} where U is the "container" set. Initially each set contains a single element. After each operation each set will contain some numbers. We define the cost of a set as the number of unique elements in the set. For each query, we merge two unmerged set and then report the sum of cost of all the sets.  The most brute force approach is for each query, add all numbers in one of the sets and put them in the other set. This will take approximately O(nlogn) time per merge operation and since there can be about O(N) mergings (because after atmost N mergings there will be only 1 set left) this will take time proportional to O(n^2logn) time. For the report, part, we just return the sum of the sizes of the set. This part is O(1) as we only have to check the size of the new merged set as the sizes of the other sets haven't changed. This is obviously a poor algorithm for a seem...

What Are Recurrences? Let's start with a simple problem:  There are N students standing in a line. The first student gets 1 chocolate. The second student gets 2 chocolates. The third student however demands that he gets twice as many chocolates as the first student plus the number of chocolate that the second student got. Similarly, the fourth student said that he wanted twice the amount of chocolate that the second student got plus the amount the third student got. Thus, each student wants the amount that the previous student got plus twice the amount the student before that had got. We need to find the total number of chocolate that we are going to need to give to all the students.  The obvious solution is to first give student1 1 chocolate, student2 2 chocolates, student3  2*1+2=4 chocolates, student4 = 2*2+4=8 chocolates and so on and then take the sum of all the chocolates that the students had got. Well, the key idea here was that if we know how many cho...

Spanning Trees in a Graph We are given a graph with say N vertices and M edges. We call a subset of these edges a spanning tree  of the graph so that if we keep only these edges, the graph still remains connected and so that the residual graph is a tree. This can also be thought of as specifying discreetly that we have to select exactly N-1 edges out of the total M that we are given. Some points that should be specified here is that there can be a lot of different number of spanning trees of a graph. Also, ALL the nodes need to be connected by the set of edges that we had selected in our spanning tree. Moreover, it doesn't really depend on whether we have weighted edges or unweighted edges, though we will shortly be looking at different types of spanning trees, some of which do take advantage of edge weights.  Finding Spanning Trees To find any random spanning tree of a graph a simple DFS will obviously suffice. Assuming the graph is connected,...

DISCLAIMER: I will not  be going over centroid tree. Just the decomposition technique as its far more useful than the actual centroid tree. Usefulness Before I describe the technique, it's better if i go over the usefulness of this technique first. Suppose we have been given a problem where we have to find the sum of F that is commutative that we have to compute over all possible paths in out tree. Oh and yes.. THIS TECHNIQUE IS ONLY FOR TREES . For now, let F be sum of edgeweights. Note that this could be done using other techniques too, and even faster than centroid decomposition, but this will serve as a nice example for the basics. We will approach harder problems later. Main Idea So the idea here is, it would be very nice if we could root the tree at some point, and then calculate this function for all paths passing through the root. This would have been done easily with a DFS. The problem is, we will then need to root the tree at various points, and calculate ...

Euler Tour        We mostly divide our problems into mostly two types: Array problems and Tree/Graph problems.  But what if we can convert some specific type of tree problems into actually array problems?  Problem: We are given a Tree. We have to perform two types of operations:   Query: Find the sum of weights of all nodes in the subtree of the given query node. Update: Set the weight of a given node to X. Obvious Solution? For each update just make the corresponding weight of the given node to X. For Queries, traverse the whole subtree and find the sum. This has a worst case of O(N*Q). However we will come up with a O(nlogn) solution to this same problem by the end of this post. Start Time/End Time When we do a DFS, suppose we keep a global variable called time.Whenever we visit a new node, we are doing something new and thus we "increase" the time. This can be thought of as a time variable that we are manuall...