Coding Start Up!

Some More Notations I will start with some notation first. Though this will be very short. First, when talking about nodes, we just refer to them using numbers. Or using alphabets. When using examples, it's rare that we will ever consider more than 26 nodes ( normally less than 10). Second, when talking about edges, we refer to them as e = (u,v) which means that edge e connects node u to node v. Somehow we generally use characters like u,v,w to refer to nodes. Just a preference.  When referring to undirected graphs, we use lines to represent them. Directed versions generally have arrows to point form where the edge is starting and where it is ending. When referring to a graph, we use the notation G = (V,E) which means that Graph G has vertices belonging to the set V and edges belonging to the set E. Note that the edges in E has its endpoints as vertices in V. (think about it... if it were not so.. then that edge would not have much meaning). Another thing th...

Introduction Let's start with a description: "There are several cities in a country. Suppose N cities for now. Suppose there are M roads,each of which connects some 2 pair of cities. " A very common description found in a huge number of problems. But what is this actually? How to usefully use this information, which seems to be a very obvious thing in out real life? Well, lets model this in terms of what we call "Graph theory". Not that it has much connection to the canonical definition of a graph that we generally encounter in our schools. The two main, MAIN, concepts in graph theory is a "node" and an "edge". Nodes can be said to be a "place" and edge can be thought of as a way to get from one "place" to another "place". In the above problem, we basically have N nodes, and M edges. Each edge just connects two nodes. Here the nodes are depicted by circles, and the edges are denoted by the s...

The Universal Proof And It's Variations " When we make a update, only O(logn) can be added to Φ(x) This is because we can add tags only to the ordinary nodes, which are O(logn) in number, and each gets added by 1 ONLY, because of the **UNIQUE** clause that I had mentioned earlier. Think about it... if it werent unique, then potentially O(log^2n) tags could be added as each tag would have contributed to its logn parents and there can be logn terminal nodes in general. Now something interesting should be noted here: we are saying that we place tags in only O(logn) nodes, that is, only on the ordinary nodes: what about the extra ones we visit? Turns out, we dont place tags on them. Think about it... the extra nodes are those that are completely inside the range...and a depth lower than the optimal position. What I mean by this is, even when we move to its parents, its still in the range and so it does not have to combine with any value that was outside of the range. The maj...

The Complexity Proof Where we left off.. In the last post I described the basic idea of a segment tree beats In each node maintain a MAX value and a SECOND_MAX value Terminate your search only when update value is more than the SECOND_MAX value However, the main problem was that there, we were visiting potentially lots of extra nodes.  In this post I will attempt to explain the time complexity proof of why, even though it seems we are doing a lot of extra work, we actually are not. Some Basic Concepts First off, just forget about the lazy tags. Only remember that when we make a lazy update, we call a method pushdown(). It propagates the lazy tag. Thats it. Now forget about the lazy tags. Good. Let me redefine tag as the maximal value of the node that is not the same as that of it's parent. What I mean by this is that the MAX value of a node is now what we call a "tag". And we stick with this definition throughout the rest of this post. NOT LA...

Segment Tree Beats  Disclaimer : This post is based on a recent post made by jiry_2 on codeforces. Before I begin, a clear understanding of segment tree and lazy propagation is required.  If you don't know those, I would recommend you to go search it up online and read it thoroughly, before coming back. With that out of the way, here goes... Hey wait wait wait. Hold on. Just to clarify, now that you have read it, in case you are confused with what I call terminal nodes in a segment tree update/query, it's basically the node that is completely inside the update range, the one where we generally end our search in a segment tree. I say generally.. well.. you will see :). Anyway without further ado...  A simple problem So the first problem I want to address, and it is fairly easy, is supporting two operations on a range: Range minimize (for each i in range, make it min(i, update_value) )  point query Solution : This is just a variant of the n...

Will talk about the challenges faced for the NTSE.. (Ranked #51 in WestBengal)  Please bear with me.. little busy with the exams!

I will talk about all the objects in the Game.. please bear with me.. little busy with the exams!