DAGs and SCC

-

Comments

Post a Comment

Popular posts from this blog

Small-to-Large

-
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...
Read more

Segment Tree Beats - An introduction

-
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...
Read more

Preparing for IOI Training Camp

-
International Informatics Olympiad Training Camp Preparing for the IOI Training Camp was not any different for me as the usual practice. Though saying that would be a bit inadequate as I practiced very little competitive programming in the months from November to March, mainly due to school exams. Still, I would like to give a few pointers that might help. Firstly, try solving all the problems from the IARCS problem archive. Although this should be a pre-requisite for preparing for INOI, it is not necessary. However, solving all the problems of the problem archive should help you. For my own part, I rarely submitted actual solutions to get AC, mainly due to lack of time, (and a little bit of laziness :), ehh not really ) but I tried finding the solutions for all the problems in pen and paper. Next, the main thing to know is that solving problems o CF and Codechef won't help much in the Team Selection Test. They usually are trivial, or have very little in common with t...
Read more