Questions Tagged With disjoint-sethttps://discuss.codechef.com/tags/disjoint-set/?type=rssquestions tagged <span class="tag">disjoint-set</span>enTue, 23 Oct 2018 23:30:42 +0530Koicost Spojhttps://discuss.codechef.com/questions/43956/koicost-spoj<p><a href="http://www.spoj.com/problems/KOICOST/">http://www.spoj.com/problems/KOICOST/</a>
I'am not able to understand the problem correctly.
It says "While there is a path between vertex u and v, delete the edge with the smallest weight. Cost(u,v) is the sum of the weights of the edges that were deleted in this process." So do we have to consider all outlier paths too?
Like in going from 1->2 according to the test case, are 1->2->3->6->2...1->2->3->4->5->3->2 valid routes?
Also,once we delete an edge with smallest weight in a path between nodes,say node 1 and node 2,do we consider it deleted already,while computing cost(u,v) of some other pair of nodes?</p>rtx12Thu, 05 Jun 2014 11:38:10 +0530https://discuss.codechef.com/questions/43956/koicost-spojdisjoint-setDISHOWN July challenge (Disjoint-set) doubthttps://discuss.codechef.com/questions/47689/dishown-july-challenge-disjoint-set-doubt<p>Hii
I wrote two solutions one in c++ and one in JAVA Of DISHOWN
All variable names are same ,function names are same ,everything is same</p>
<p>Got AC in C++ :) but in JAVA getting NZEC error :( :(. PLz can anyone tell me Why is it so even though both programs are exactly same </p>
<p>C++ solution : <a href="http://www.codechef.com/viewsolution/4335936">http://www.codechef.com/viewsolution/4335936</a></p>
<p>JAVA solution : <a href="http://www.codechef.com/viewsolution/4335995">http://www.codechef.com/viewsolution/4335995</a></p>n1n1_4Wed, 16 Jul 2014 17:08:11 +0530https://discuss.codechef.com/questions/47689/dishown-july-challenge-disjoint-set-doubtdisjoint-setjavac++dishownCode Monk: DSUhttps://discuss.codechef.com/questions/72999/code-monk-dsu<p>Hi,</p>
<p>If you're a beginner and would like to learn the concept of DSU, do take part in CodeMonk DSU! :D
Date: 15 July Time: 2100 HRS (IST)
Yes, there are HackerEarth merchandise to be won. So, come on and code on! </p>
<p>Here's the link: <a href="https://www.hackerearth.com/code-monk-disjoint-set-union/">https://www.hackerearth.com/code-monk-disjoint-set-union/</a> </p>
<p>Good luck!</p>oldschoolburkeTue, 14 Jul 2015 23:42:01 +0530https://discuss.codechef.com/questions/72999/code-monk-dsuhackerearthcodemonkdisjoint-setGettin WA in DISHOWNhttps://discuss.codechef.com/questions/77552/gettin-wa-in-dishown<p>Pls help in letting me know what are the test cases on which my code fails in the practice(easy)DISHOWN. I have tried all possible test cases.. Pls help :(
Here is my code <a href="https://www.codechef.com/viewsolution/8892158">https://www.codechef.com/viewsolution/8892158</a></p>mayank1995Mon, 07 Dec 2015 15:25:13 +0530https://discuss.codechef.com/questions/77552/gettin-wa-in-dishownunion-finddisjoint-setdishownDeveloping the test caseshttps://discuss.codechef.com/questions/78199/developing-the-test-cases<p>How to derive test cases for problems like <a href="https://www.codechef.com/LTIME31/problems/ABROADS">this</a></p>
<p>Can anyone derive possible test cases for this problem, I am getting wrong answer for its solution, my code is working fine with all the test cases, which I have developed.</p>arpit728Thu, 31 Dec 2015 22:17:34 +0530https://discuss.codechef.com/questions/78199/developing-the-test-casesdisjoint-setabroadsgraphdsusetstest-casesActivity selection problem on topcoderhttps://discuss.codechef.com/questions/78986/activity-selection-problem-on-topcoder<p>Can anyone write editorial for <a href="https://community.topcoder.com/stat?c=problem_statement&pm=2977&rd=5880">this</a> Topcoder problem. What is approach to solve this kind of problem.</p>arpit728Fri, 29 Jan 2016 07:18:29 +0530https://discuss.codechef.com/questions/78986/activity-selection-problem-on-topcoderdisjoint-setjobsalgorithmgreedydata-structureeditorialtopcoderTULIPS - Editorialhttps://discuss.codechef.com/questions/79924/tulips-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/MARCH16/problems/TULIPS">Contest</a><br>
<a href="http://www.codechef.com/problems/TULIPS">Practice</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/meteora">Malvika Raj Joshi</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/furko">Roman Furko</a><br>
<strong>Translators:</strong> <a href="http://www.codechef.com/users/antoniuk1">Vasya Antoniuk</a> (Russian), <a href="http://www.codechef.com/users/vnoi">Team VNOI</a> (Vietnamese) and <a href="http://www.codechef.com/users/huzecong">Hu Zecong</a> (Mandarin)<br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/kevinsogo">Kevin Atienza</a> </p>
<h1>DIFFICULTY:</h1>
<p>Hard</p>
<h1>PREREQUISITES:</h1>
<p>Centroid decomposition, segment tree, disjoint set union, power-of-two pointers</p>
<h1>PROBLEM:</h1>
<p>There are $N$ nodes forming a tree. Each node contains a tulip, and each edge has a given length. If a tulip is picked, a new one will grow in the same spot if it is left <strong>undisturbed</strong> for $X$ contiguous days. </p>
<p>On day $d_j$, Cherry visits all node reachable from $u_j$ with edges of length $\le k_j$. She will pick all the tulips she can find. On day $d_1$, all nodes have tulips. </p>
<p>For each of the $Q$ days Cherry does this, print the number of tulips she gets. </p>
<h1>QUICK EXPLANATION:</h1>
<ul>
<li>Construct the "reachability tree" of the given tree. We define the reachability tree as a rooted binary tree with $2N-1$ nodes such that each leaf represents a node in the original tree, and each internal node represents a set of nodes in the original tree that are reachable from each other using edges up to a certain length. In other words, each internal node is associated with some value, say $k$, such that the leaves under it represent a maximal set of nodes in the original tree that are reachable from each other using edges of length $\le k$. This tree can be constructed in $O(N \log N)$ time. </li>
<li>Compute the preorder traversal of the leaves of this tree. Now, the nodes in the original tree in this traversal has the property that any visitation by Cherry always affects consecutive nodes in the traversal, making it amenable to range query optimizations. </li>
<li>
<p>Construct a segment tree on top of this traversal that can support the following operations: </p>
<ul>
<li><strong>initialize</strong>: Initialize all values to $0$. </li>
<li><strong>update</strong>: Given a subrange, increase/decrease it by a given amount. </li>
<li><strong>query</strong>: Given a subrange, how many values in it are equal to $0$?</li>
</ul>
<p>The structure may assume that all values will stay nonnegative. </p>
</li>
<li>
<p>For every visitation $(d_j,u_j,k_j)$, first find in the preorder traversal the range $[l,r]$ of nodes reachable from $u_j$ using edges of length $\le k_j$. (This can be done in $O(\log N)$ time using power-of-two pointers.) Next, print the number of values in the segment tree in the subrange $[l,r]$ equal to $0$. Next, increase all elements in the subrange $[l,r]$ by $1$. Finally, add a <em>future decrement operation</em> that will decrease all elements in the subrange $[l,r]$ by $1$ on day $d_j+X$. (You will need to perform these decrement operations before processing visitations on or after that day. You can keep track of these <em>future decrements</em> using a queue, because $d_j+X$ is increasing.) </p>
</li>
</ul>
<p>(Note: there are many other approaches as well)</p>
<h1>EXPLANATION:</h1>
<h1>Traversing edges up to a given length</h1>
<p>Each visitation has a starting node $u$ and a number $k$, and performs some operations across all nodes that are reachable from $u$ using edges with weights $\le k$. We will use the notation $R(u,k)$ to denote <strong>the set of nodes reachable from $u$ using edge with weights $\le k$</strong>. Clearly, we can't iterate through all nodes of $R(u,k)$ for every visitation because that would be slow. So to progress, we must study the $R(u,k)$ sets more closely. </p>
<p>Let's consider a <em>fixed</em> $u$, and a <em>varying</em> $k$. $k$ starts at $0$ and continuously increases up to $\infty$. Let's see what happens to $R(u,k)$ while this happens. In the beginning ($k = 0$), no edges are usable, so $R(u,k)$ is simply $\{u\}$. As we increase $k$ however, more and more edges become usable, giving us access to more nodes, so $R(u,k)$ possibly increases in size. Eventually, $k$ will surpass the largest edge weight in the tree, and $R(u,k)$ becomes the set of all $N$ nodes. </p>
<p>There are two things that we learn from this process: </p>
<ul>
<li>As we increase $k$, $\left|R(u,k)\right|$ never decreases in size.</li>
<li>Not only that, but we can also say that for $k < k'$, $R(u,k) \subset R(u,k')$! In other words, once a node becomes reachable from $u$, it becomes reachable forever. </li>
</ul>
<p>These are certainly nice facts. Unfortunately these don't give us the full picture. So let's look at the full picture. Instead of focusing on a fixed node $u$, we will focus on <em>all</em> $N$ nodes. Specifically, we will focus on $R(u,k)$ for all nodes $u$ (not just a fixed $u$), as we increase $k$. </p>
<p>As before, in the beginning, no edge is usable, so $R(u,k) = \{ u \}$ for all nodes $u$. Now, as we increase $k$, one by one each edge becomes usable, effectively <strong>uniting</strong> the set of reachable nodes it connects. Specifically, once the edge $(u,v)$ becomes usable, $R(u,k)$ and $R(v,k)$ unite and become equal. This happens one by one for each edge, until finally $k$ passes the largest edge weight, and all sets $R(u,k)$ unite into a single set containing all $N$ nodes. </p>
<p>So, what did we learn from this experiment? We learned that the sets $R(u,k)$ behave as if we're doing <strong>union-find</strong>. Moreover, upon closer look, we can also see some sort of <strong>tree structure</strong> behind all this! </p>
<p>Let's call this tree the <strong>reachability tree</strong>. We will define the reachability tree as a rooted binary tree with $2N-1$ nodes such that:</p>
<ul>
<li>Each leaf represents a node in the original tree, and </li>
<li>Each internal node represents a <strong>union</strong> operation during our experiment above. </li>
</ul>
<p>We call this the "reachability tree" because each internal node represents some $R(u,k)$ at some point during our experiment above. More specifically, each internal node is associated with some value, say $k$, such that its leaves constitute some $R(u,k)$. </p>
<p>Let's give an example. Consider the following tree:</p>
<p><img src="https://discuss.codechef.com/upfiles/1_11.png" width="100%"></p>
<p>The reachability tree of this tree is the following:</p>
<p><img src="https://discuss.codechef.com/upfiles/2_8.png" width="100%"></p>
<p>Note that the original nodes are leaves in this reachability tree. Also, every internal node represents some $R(u,k)$. For example, node $f$ represents the set $R(A,16) = R(C,16) = R(D,16) = \{A, C, D\}$. </p>
<p>The reachability tree has the following nice property:</p>
<p><strong>Given any $u$, $k$, $R(u,k)$ is always the set of leaves of some subtree in the reachability tree.</strong> (This includes <em>any</em> $k$, not just values associated with internal nodes.) </p>
<p>For example, suppose that in the tree above, we start at node $F$ and traverse all edges with weight $\le 14$. Then $R(F,14) = \{F, E, H\}$, as shown in the following: </p>
<p><img src="https://discuss.codechef.com/upfiles/3_2.png" width="100%"></p>
<p>True enough, these nodes can be found as leaves of some subtree in the reachability tree: </p>
<p><img src="https://discuss.codechef.com/upfiles/4_2.png" width="100%"></p>
<p>This property of the reachability tree is very useful for us, as we intend to operate on $R(u,k)$ sets many times. To see why it's useful, note that when we perform a <strong>preorder traversal</strong> of the tree and collect the leaves during this traversal, the set of leaves of any subtree can be found in <em>consecutive</em> positions in the traversal. This allows us to turn any operation on the set $R(u,k)$ into a <strong>range query</strong>! Thus, this tree can help us immensely if we can construct it. </p>
<h1>Constructing the reachability tree</h1>
<p>We can construct the reachability tree by remembering how we discovered it: by uniting sets together, starting from $N$ sets to just one. This is very much like union-find, except that during every <strong>union</strong>, we also create a <strong>new node</strong> recording that union in the reachability tree. </p>
<p>That is the main idea of the construction. We're building the tree from the ground up, starting from the leaves up until the root. We will maintain disjoint sets representing $R(u,k)$s. In addition, each disjoint set's representative points to its current root node in the reachability tree. </p>
<ul>
<li>Initially, all $N$ nodes are on separate sets, each pointing to a new node. These new nodes are the leaves of the reachability tree. </li>
<li>Next, we iterate through all edges in increasing order of weight. For each edge $(u,v)$ with weight $k$, we unite the sets containing $u$ and $v$, and create a new node in the reachability tree whose children are the nodes being pointed at by $u$'s and $v$'s representatives. </li>
<li>After iterating through all $N-1$ edges, we now have the reachability tree! </li>
</ul>
<p>This runs in $O(N \log N)$ time because we sorted the edges. Everything else runs asymptotically faster. </p>
<h1>Performing queries</h1>
<p>Next, we need to convert a query $(d_j,u_j,k_j)$ into a range query, with the help of the reachability tree. We will assume that we've already performed the preorder traversal on the reachability tree, and collected all leaves in this traversal. </p>
<p>Our goal now is to find the relevant <em>range</em> of nodes $[L_j,R_j]$ corresponding to the set $R(u_j,k_j)$. There are two steps we need to take: </p>
<ol>
<li>Given $u_j$ and $k_j$, find the subtree that contains all nodes of $R(u_j,k_j)$ (and only those nodes). Let $p$ be the root of this subtree. </li>
<li>Given this subtree rooted at $p$, find the indices of the leftmost and rightmost leaves. (These indices are the $L_j$ and $R_j$ we are looking for.)</li>
</ol>
<p>Let's look at the first step. We need to find $p$. Surely, $p$ is an ancestor of $u_j$ in the reachability tree. More specifically, $p$ is the highest ancestor of $u_j$ whose associated value $k$ is $\le k_j$. This gives us a way of computing $p$, but it's slow (because the reachability tree can be highly imbalanced). </p>
<p>So how do we compute $p$ quickly? It would be nice if we can binary search along all ancestors of $u_j$. But we can actually do that with the help of <strong>power-of-two pointers</strong> (also called jump pointers). The idea is, for each node in the reachability tree, to store all its ancestors at power-of-two heights, i.e. for every $i \ge 0$, we store its $2^i$th ancestor. This structure is usually used to compute <a href="https://en.wikipedia.org/wiki/Level_ancestor_problem">certain ancestors</a> of nodes quickly (and is also used in computing lowest common ancestors), but we can also use this structure to compute $p$ quickly. The following pseudocode illustrates the idea:</p>
<pre><code>// in this code, u.jump(i) is the 2^i'th ancestor of u
def find_p(u_j, k_j):
if nodes[ROOT].k <= k_j:
return ROOT
i = 0
while u.jump(i).k <= k_j:
u = u.jump(i++)
while i != 0:
i--
if u.jump(i).k <= k_j:
u = u.jump(i)
return u
</code></pre>
<p>The first part simply checks if the root is already a valid $p$. Otherwise, the first while loop simply finds <em>some</em> ancestor that is not a valid $p$. The second while loop then finds the <em>smallest</em> ancestor that is not a valid $p$. So after that loop, the ancestor before that must be the $p$ we are looking for!</p>
<p>Now, for the second part. Given a subtree rooted at $p$, what is the leftmost and rightmost leaf? This is actually easier: Simply precompute all leftmost and rightmost leaves using a single traversal and dynamic programming! The following recurrences can be used:<br>
$$\text{leftmost}(u) = \begin{cases}
u & \text{if $u$ is a leaf} \\\
\text{leftmost}(\text{left}(u)) & \text{otherwise}
\end{cases}$$
$$\text{rightmost}(u) = \begin{cases}
u & \text{if $u$ is a leaf} \\\
\text{rightmost}(\text{right}(u)) & \text{otherwise}
\end{cases}$$</p>
<p>Now, we can convert $(d_j,u_j,k_j)$ into a range query on the range $[L_j,R_j]$! </p>
<h1>Range queries</h1>
<p>Now that all queries are now range queries, let's write the current version of the problem: </p>
<p><em>There are $N$ nodes in a line. Each node contains a tulip. If a tulip is picked, a new one will grow in the same spot if it is left <strong>undisturbed</strong> for $X$ contiguous days.</em> </p>
<p><em>On day $d_j$, Cherry visits all nodes from $L_j$ to $R_j$ and picks all the tulips she can find. On day $d_1$, all nodes have tulips.</em></p>
<p><em>For each of the $Q$ days Cherry does this, print the number of tulips she gets.</em> </p>
<p>This sounds much doable because we've essentially gotten rid of the tree and replaced it with range queries. We've now essentially <em>flattened</em> the problem. All that remains is to find a way to perform the range queries efficiently! </p>
<p>The idea for our fast solution would be to create an array of $N$ elements, $[D_1, \ldots, D_N]$, where $D_i$ represents the "disturbance" of the $i$th node. Here, we define the <strong>disturbance</strong> of a node as the number of times the node has been disturbed in the past $X$ days. This way, a node has an available tulip if and only if its disturbance is $0$. Initially of course, $D_i = 0$ for all $i$. </p>
<p>Now, when nodes $L_j$ to $R_j$ are visited on day $d_j$, these things happen:</p>
<ul>
<li>Count the number of available tulips in the range. Specifically, count the number of nodes in the range $[L_j,R_j]$ with disturbance equal to $0$. </li>
<li><em>Disturb</em> these nodes, i.e. increase the disturbance of all nodes from $L_j$ to $R_j$ by $1$. However, we must remember to decrease them again after $X$ days, i.e. on day $d_j+X$. </li>
</ul>
<p>So all in all, three events happen for each <em>visit</em> $(d_j,L_j,R_j)$: </p>
<ul>
<li>On day $d_j$, we count the number of $i$s in the range $[L_j,R_j]$ where $D_i = 0$. </li>
<li>On day $d_j$, we increase all disturbances in the range $[L_j,R_j]$ by $1$. </li>
<li>On day $d_j+X$, we decrease all disturbances in the range $[L_j,R_j]$ by $-1$. </li>
</ul>
<p>Thus, to process all visitations, we just need to sort all the <em>events</em> across all visitations altogether. If multiple events happen on the same day, perform decrease operations before queries, and perform queries before increase operations. </p>
<p>But how do we handle range increases/decreases and range queries? At first glance, it seems hard to find any efficient segment tree solution, but things become much easier when you notice that <strong>disturbances never drop below $0$</strong>. So if the disturbance $0$ is present in the range at all, then it is surely the <em>minimum</em> disturbance in that range. Thus, to answer the range query "how many disturbances are equal to $0$", we can use the following more general range query: </p>
<ul>
<li>Given a subrange $[L_j,R_j]$, what is the minimum disturbance in this range, and how many times does it appear?</li>
</ul>
<p>To answer our original range query, we simply perform this new range query on the range and then check if the minimum disturbance is $0$. If it is, then return the count, otherwise, simply return $0$. :) </p>
<p>Thus, all we need to implement is a typical <em>range minimum query</em> structure with range updates, with a slight twist: we also need to count how many times the minimum appears. But our trusty <strong>segment tree with lazy propagation</strong> can do this job very efficiently! We just need to modify it slightly so that the count can also be returned. To do it, simply add this count in every node of the segment tree, and remember to update it during downward propagations, updates and queries! </p>
<p>For implementation details, see the tester's or editorialist's code. </p>
<p>Now, what is the time complexity? Clearly, $O(\log N)$ time is needed for each query/update, so all events run in $O(Q \log N)$ time. Initializing the segment tree requires $O(N)$ time, and computing the sorted order of the events requires $O(Q \log Q)$ time. By including the fact that the reachability tree is constructed in $O(N \log N)$ time, the overall complexity becomes $O((N+Q)\log N + Q\log Q)$. </p>
<p>We can actually remove the $O(Q \log Q)$ bit by noticing that the visits are given in increasing order of $d_j$ already. This means that the only out-of-order events are the <em>decrease</em> events, and even they are already given in increasing order (since $d_j+X$ is increasing). Thus, all we need to do is to <em>merge</em> two sorted list of events together. The <em>merge</em> routine of merge sort does this job in $O(Q)$ time. With this, the overall running time becomes just $O((N+Q) \log N)$. </p>
<h1>Time Complexity:</h1>
<p>$O((N+Q) \log N)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="https://www.codechef.com/download/Solutions/MARCH16/Setter/TULIPS.cpp">setter</a><br>
<a href="https://www.codechef.com/download/Solutions/MARCH16/Tester/TULIPS.cpp">tester</a><br>
<a href="https://www.codechef.com/download/Solutions/MARCH16/Editorialist/TULIPS.cpp">editorialist</a> </p>kevinsogoSun, 13 Mar 2016 18:29:31 +0530https://discuss.codechef.com/questions/79924/tulips-editorialdisjoint-setmarch16hardsegment-treeeditorialcentroid-decompFillMTR Solution not passing with DSUhttps://discuss.codechef.com/questions/112212/fillmtr-solution-not-passing-with-dsu<p>My following code is giving wrong answer constantly. Please help me. I have used approach of DSU and assigning color to root and comparing color of root while union. If anyone got Ac, with this approach,Please give link of code.</p>
<p>import <a href="http://java.io">java.io</a>.<em>;
import java.math.</em>;
import java.util.*;</p>
<p>import static java.util.Arrays.fill;
import static java.lang.Math.*;
import static java.util.Arrays.sort;
import static java.util.Collections.sort;</p>
<p>class FillTheMatrix
{</p>
<pre><code>public static int mod = 1000000007;
static FasterScanner in = new FasterScanner();
static PrintWriter out = new PrintWriter(System.out);
static int maxn=(int) (1e5+2);
static int[] parent=new int[maxn];
static int[] size=new int[maxn];
static int[] color=new int[maxn];
public static int findheadof(int x)
{
while(x!=parent[x])
{
parent[x]=parent[parent[x]];
x=parent[x];
}
return x;
}
public static void union(int u,int v)
{
int x=findheadof(u);
int y=findheadof(v);
if(x==y)
return;
if(size[x]<size[y])
{
int temp=x;
x=y;
y=temp;
}
size[x]+=size[y];
parent[y]=x;
}
public static void main(String[] args)
{
int testcases=in.nextInt();
while(testcases-->0)
{
int n=in.nextInt();
int q=in.nextInt();
for(int i=1;i<=n;i++)
{
parent[i]=i;
size[i]=1;
color[i]=2;
//color ==2 means no color
}
boolean ispossible=true;
while(q-->0)
{
int u=in.nextInt();
int v=in.nextInt();
int w=in.nextInt();
if(u==v)
{
if(w!=0)
ispossible=false;
continue;
}
if(w==0)
{
if(color[findheadof(u)]!=2 && color[findheadof(v)]!=2)
{
if(color[findheadof(u)]!=color[findheadof(v)])
ispossible=false;
}
if(color[findheadof(u)]==2 && color[findheadof(v)]==2)
{
union(u, v);
color[u]=0;
color[v]=0;
continue;
}
if(findheadof(u)==u && size[findheadof(u)]==1)
{
union(u, v);
color[u]=color[findheadof(v)];
continue;
}
if(findheadof(v)==v && size[findheadof(v)]==1)
{
union(u, v);
color[v]=color[findheadof(u)];
}
}
else
{
if(color[findheadof(u)]!=2 && color[findheadof(v)]!=2)
{
if(color[findheadof(u)]==color[findheadof(v)])
ispossible=false;
}
if(color[findheadof(u)]==2 && color[findheadof(v)]==2)
{
color[findheadof(v)]=1;
}
if(findheadof(u)==u && size[findheadof(u)]==1 && color[findheadof(u)]==2)
{
color[u]=1-color[findheadof(v)];
continue;
}
if(findheadof(v)==v && size[findheadof(v)]==1)
{
color[v]=1-color[findheadof(u)];
}
}
}
if(ispossible)
out.println("yes");
else
out.println("no");
}
out.close();
}
public static long pow(long x, long n, long mod)
{
long res = 1;
for (long p = x; n > 0; n >>= 1, p = (p * p) % mod)
{
if ((n & 1) != 0)
{
res = (res * p % mod);
}
}
return res;
}
public static long gcd(long n1, long n2)
{
long r;
while (n2 != 0)
{
r = n1 % n2;
n1 = n2;
n2 = r;
}
return n1;
}
static class FasterScanner
{
private byte[] buf = new byte[1024];
private int curChar;
private int snumChars;
public int read()
{
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try
{
snumChars = System.in.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public String nextLine()
{
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do
{
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public String nextString()
{
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do
{
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public long nextLong()
{
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do
{
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int nextInt()
{
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do
{
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n)
{
int[] arr = new int[n];
for (int i = 0; i < n; i++)
{
arr[i] = nextInt();
}
return arr;
}
public long[] nextLongArray(int n)
{
long[] arr = new long[n];
for (int i = 0; i < n; i++)
{
arr[i] = nextLong();
}
return arr;
}
private boolean isSpaceChar(int c)
{
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c)
{
return c == '\n' || c == '\r' || c == -1;
}
}
</code></pre>
<p>}</p>parth_patel15Tue, 19 Sep 2017 13:25:44 +0530https://discuss.codechef.com/questions/112212/fillmtr-solution-not-passing-with-dsudisjoint-setunionfillmtrsept17datafindstructureNPLFSGL-Editorialhttps://discuss.codechef.com/questions/116755/nplfsgl-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/NPLFSGL">Practice</a>
<a href="https://www.codechef.com/NPLF2017/problems/NPLFSGL">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/vinod10">Vinod</a>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/vinod10">Vinod</a>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/manjunath1996">Manjunath</a></p>
<h1>DIFFICULTY:</h1>
<p>MEDIUM</p>
<h1>PREREQUISITES:</h1>
<p>graph,xor propery,union disjoint</p>
<h1>PROBLEM:</h1>
<p>batch power of graph is defined as sum of xor of all connected vertices.Each day one edge is being blocked (consider as removed).We have to find batch power on each day after removal.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Instead of blocking, consider each day we are unblocking the edges. Then it is easy to solve this <a href="http://problem.so">problem.so</a> suppose previously 2 connected components x,y were there which were just connected by unblocking current edges.Then answer changes as ans=prev_ans-(xor(x)+xor(y))+xor(x,y),where (x,y) denoted connected graph of x,y vertices.We can convert the actual problem to this variation by considering unblocking of edges from last day to the first day.</p>
<h1>EXPLANATION:</h1>
<p>Instead of blocking, consider each day we are unblocking the edges. Then it is easy to solve this <a href="http://problem.so">problem.so</a> suppose previously 2 connected components x,y were there which were just connected by unblocking current edges.Then answer changes as ans=prev_ans-(xor(x)+xor(y))+xor(x,y),where (x,y) denoted connected graph of x,y vertices.We can convert the actual problem to this variation by considering unblocking of edges from last day to the first day.</p>
<pre>
make each vertex as a disjoint set.
value of disjoint set is xor of all vertices in that set.
answer[m]=sum
for(int i=m;i>=1;i--){
//u-v is being unblocked
if(set(u)==set(v)){
ans[i-1]=ans[i];
}
else{
ans[i-1]=ans[i]-value(set(u))-value((set(v));
union(u,v);
value(set(u))=value(set(u))^value((set(v));
ans[i-1]+=value(set(u));
}
}
</pre>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="https://www.codechef.com/viewsolution/16236770">here</a>.
Tester's solution can be found <a href="https://www.codechef.com/viewsolution/16236770">here</a>. </p>manjunath1996Sun, 12 Nov 2017 12:29:21 +0530https://discuss.codechef.com/questions/116755/nplfsgl-editorialdisjoint-setnplf2017DISHOWN - Editorialhttps://discuss.codechef.com/questions/47241/dishown-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/DISHOWN">Practice</a><br>
<a href="http://www.codechef.com/JULY14/problems/DISHOWN">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/viv001">Vivek Hamirwasia</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/jingbo_adm">Shang Jingbo</a> and <a href="http://www.codechef.com/users/gerald">Gerald Agapov</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/devuy11">Devendra Agarwal</a> </p>
<h1>DIFFICULTY:</h1>
<p>Easy </p>
<h1>PREREQUISITES:</h1>
<p>Set Union Data Structure </p>
<h1>PROBLEM:</h1>
<p>N chef's are there. Each chef has a dish which is given a value (denoted by S[i]). You need to answer 2 queries : <br>
1. 0 x y : Chef containing dish x competes with chef containing dish y. If both dishes belong to same chef print "Invalid Query!" , otherwise the winner of the round will obtain all the dishes of the loser which will then be eliminated.<br>
2. 1 x : Output the chef which contains the dish x. </p>
<h1>Explanation</h1>
<p>This problem can be solved using <a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure">Disjoint set data structures</a>. </p>
<p>Union Find or Disjoint Set Data structures allow you to merge two sets of items together dynamically and maintain for each item - to which set set does it belong. </p>
<p>This is exactly what we need in the problem , i.e. dynamically merging two sets and querying which set does an element belong. </p>
<p>We will be using Disjoint Set Data Structure that supports the following : </p>
<ol>
<li>find(A) : Get the id of the disjoint set to which A belongs(i.e. the chef id which contains that dish). </li>
<li>union(A,B) : Merge the two disjoint sets in which A and B belong respectively. </li>
</ol>
<p>Initially, we will create N disjoint set , each set contains 1 dish and it's owner.<br>
Let dish x be in setA and dish y be in setB.<br>
If the dish contained by the owner of setA has score higher than the dish contained by the owner of setB , then we will merge setA and setB and set the owner of setA as the overall owner of the merged set.<br>
If the dish contained by the owner of setB has score higher than the dish contained by the owner of setA , then we will merge setA and setB and set the owner of setB as the overall owner of the merged set. </p>
<p><strong>Note</strong> : You can easily prove from this that the owner of the set has dish whose score is higher than all other dish of the set.<br>
We will be using only Path Compression heuristics to solve the problem. </p>
<p><strong>Pseudo Code</strong></p>
<pre><code>Initialize parent[i] = i
Let S[i] denote the initial array.
int find(int i)
int j
if(parent[i]==i)
return i
else
j=find(parent[i])
//Path Compression Heuristics
parent[i]=j
return j
set_union(int i,int j)
int x1,y1
x1=find(i)
y1=find(j)
//parent of both of them will be the one with the highest score
if(S[x1]>S[y1])
parent[y1]=x1
else if ( S[x1] < S[y1])
parent[x1]=y1
solve()
if(query == 0)
Input x and y
px = find(x)
py = find(y)
if(px == py)
print "Invalid query!"
else
set_union(px,py)
else
Input x.
print find(x)
</code></pre>
<h1>AUTHOR'S and TESTER'S Solution:</h1>
<p><a href="http://www.codechef.com/download/Solutions/2014/July/Setter/DISHOWN.cpp">Author's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/2014/July/Tester/DISHOWN.cpp">Tester's solution</a> </p>devuy11Mon, 14 Jul 2014 15:01:37 +0530https://discuss.codechef.com/questions/47241/dishown-editorialdisjoint-seteasyunion-findjuly14editorialdishownGALACTIK - Editorialhttps://discuss.codechef.com/questions/18004/galactik-editorial<h1>PROBLEM LINK</h1>
<p><a href="http://www.codechef.com/problems/GALACTIK">Practice</a><br>
<a href="http://www.codechef.com/JULY13/problems/GALACTIK">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>EASY</p>
<h1>PREREQUISITES</h1>
<p><a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure">Disjoint Set Data Structure</a>, Simple Math</p>
<h1>PROBLEM</h1>
<p>There are <b>N</b> nodes in a graph labeled from <b>1</b> to <b>N</b>. Each node has an associated cost with it, given by cost array. You wish to connect this graph by constructing edges between the nodes.</p>
<ul>
<li>You can construct an edge between two nodes <b>a</b> and <b>b</b> iff <b>cost[a] ≥ 0 AND cost[b] ≥ 0</b> </li>
<li>The cost of the construction of the edge is equal to <b>cost[a] + cost[b]</b></li>
</ul>
<p>Some edges already exist. Hence, some nodes are already connected. You wish to find the minimum cost of connecting the entire graph.</p>
<h1>QUICK EXPLANATION</h1>
<p>We will be using a <b>Disjoin Set Data Structure</b> that supports the following operations</p>
<ul>
<li><b>init(N)</b>, initialize <b>N</b> disjoint sets. </li>
<li><b>find(A)</b>, get the id of the disjoint set to which <b>A</b> belongs. </li>
<li><b>join(A,B)</b>, merge the two disjoint sets in which <b>A</b> and <b>B</b> belong respectively.</li>
</ul>
<p><b>Union-Find</b> along with <b>Union by Rank</b> and <b>Path Compression</b> is the asymptotically optical way of maintaining <b>Disjoint Sets</b>.</p>
<p>After considering the existing set of edges, we will have some disjoint sets, where there are one or more nodes in each set. Let us assume there are <b>K</b> disjoint sets.</p>
<p><b>We only need to put K-1 edges</b></p>
<p>This is easily proven by considering that adding each edge reduces the number of disjoint sets by <b>1</b>. If it doesn't, then the edge is connecting two nodes that are already connecetd.</p>
<p>Thus, we only consider <b>K-1</b> edges at most.</p>
<h1>EXPLANATION</h1>
<p>As we dwell deeper into discussing the solution to the problem we will encounter a lot of difficulty discussing the ideas if we keep reminding ourselves of <b>ignoring the vertices with negative costs</b>. To be able to handle them in the discussion below (and maybe in your implementation as well), we assume that each negative cost is replaced by a <b>very large positive cost</b>. We will see soon that doing this does not affect the <b>optimal answer</b>.</p>
<p>We can consider each disjoint set as an independent vertex and try to build a <a href="http://en.wikipedia.org/wiki/Minimum_spanning_tree">minimum spanning tree</a> on the graph. The problem is, that for <b>K</b> disjoint sets, there may be as many as <b><sup>K</sup>C<sub>2</sub></b> edges. We know that we can solve the problem of finding the <b>minimum spanning tree</b> by greedily considering the edges in <b>increasing order of weights</b>.</p>
<p>Here comes to our rescue the definition of the weight of edges in the problem statement.</p>
<p><b>Edge Weight for edge from a to b = cost[a] + cost[b]</b></p>
<p>Let <b>x</b> be the vertex for which <b>cost[x]</b> is <b>smallest</b>. An edge between <b>x</b> and any other vertex will have a lower cost than <b>any other edges</b> in the graph.</p>
<p>Also, considering all the edges with one end point on <b>x</b> means we are considering sufficient edges for a connected graph!</p>
<p>Note how assuming that all negative cost vertices were actually <b>very large positive cost</b> edges allows us to get around several edge cases</p>
<ul>
<li>The lowest cost vertex, <b>x</b>, is automatically the lowest non-negative cost vertex </li>
<li>We will consider all the edges from <b>x</b> to other vertices in the order of increasing weights, thus we avoid considering edges to vertices with negative weights </li>
<li>If we are forced to consider an edge to a vertex with large weight (negative cost vertex originally), then we know that we <b>could not have</b> connected to the connected component of that vertex through any vertex whose weight was positive (otherwise we already would be connected to that component).</li>
</ul>
<p>Hence, if the answer could be reached <b>before</b> connecting to any vertex with very large weight, we can print the answer, otherwise, we will print <b>-1</b>.</p>
<p>Note that we can avoid the sorting step altogether and consider the <b>minimum cost vertices</b> in each <b>connected component</b>. This way, if we know the <b>sum of costs</b> of the <b>minimum cost vertices</b> in each component, the answer is simply</p>
<pre>cost[x] * (K-1) + sum - cost[x]
</pre>
<p>Where <b>x</b> is the vertex with the smallest cost.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/July/Setter/GALACTIK.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/July/Tester/GALACTIK.cpp">here</a>.</p>gamabuntaFri, 19 Jul 2013 19:44:38 +0530https://discuss.codechef.com/questions/18004/galactik-editorialdisjoint-seteditorialunion-findmstjuly13easyMy Solution to S-T Mincut from May18https://discuss.codechef.com/questions/126885/my-solution-to-s-t-mincut-from-may18<p>Since people are looking for editorials for the May Long Competition and I really enjoyed this problem I decided to describe my solution.</p>
<p>The most obvious part of the problem is that the final matrix $A$ needs to be symmetric. That is clear from the first two test cases. After that it helped me to consider the first subtask.</p>
<p><strong>First Subtask:</strong></p>
<p>For the first subtask we have $A_{ij}\in\{0,1\}$. In this case we only need to consider connectivity. Here we will say that two nodes are connected if there exists a path between them. We then have a very important transitive property: If node $i$ is connected to node $j$ and node $j$ is connected to node $k$ then node $i$ is connected to node $k$. In terms of minimum cuts that statement can be reformulated as:</p>
<p>If the $i-j$ mincut cost is $1$ and the $j-k$ mincut cost is $1$ then the $i-k$ mincut cost is at least $1$.</p>
<p>As a result the final $A_{ij}$ will be at least equal to $1$ if there is a path $P=\{p_1=i,p_2,\dots,p_q=j\}$ such that $A_{p_\ell p_{\ell+1}}=1$ or $A_{p_{\ell+1}p_\ell}=1$ in the original matrix $A$ for all $1\leq\ell< q$. If we update only those components $A_{ij}$ and set them to $1$ then we get a matrix $A$ that is associated with a forest (an acyclic graph that may or may not be connected). Given any such forest, the matrix $A$ is given by</p>
<p>$$A_{ij}=\begin{cases}1,\qquad \text{if }i\neq j\text{ and nodes $i$ and $j$ are part of the same tree,}\\0,\qquad \text{otherwise.}\end{cases}$$</p>
<p>We note that the matrix $A$ depends only on how the nodes are grouped into connected components (trees) and not on the structure of those components. Since this matrix satisfies our requirements and we only made changes that are necessary, it must be optimal.</p>
<p>The problem can now be solved using a <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure">disjoint-set data structure</a>. We start with a set of nodes that are all in different sets. We then iterate over the elements of $A$. If the element $A_{ij}=1$ and the associated nodes $i$ and $j$ are in disjoint sets, we join those two sets. In the end we have a collection of disjoint sets, each of which represents a tree in the forest. Based on the sizes of the disjoint sets it is then easy to compute the total number of $1$s in the final matrix $A$.</p>
<p>Implementing this method is extremely easy if you have a disjoint-set data structure available. Here is a solution in Python:
<a href="https://www.codechef.com/viewsolution/18589852">https://www.codechef.com/viewsolution/18589852</a></p>
<p><strong>Original Constraints:</strong></p>
<p>To solve the problem with the original constraints we can use many of the same ideas but we iterate over the different values of the mincut. As an example let us assume that $A$ contains values from $\{0,1,2\}$. In the optimal $A$ no element will need to be larger than $2$. To determine where $2$s will be located in the optimal $A$ we can build a forest as before but only connecting nodes if the associated $A_{ij}=2$. After taking care of all of the stronger connections, we can then continue working with the weaker connections ($A_{ij}=1$).</p>
<p>To generalise this idea we can use a max-heap priority queue. We will loop over all elements of $A$ and add them to the priority queue if they have a value that is greater than $0$. We also need to keep track of the nodes associated with each value in the priority queue. To solve the problem then remove elements from the queue and process them in the order that they come out. Each new element is always one of the largest remaining values. If the associated nodes are not currently in the same set, we need to join those sets and account for the associated values in the final matrix $A$.</p>
<p>Here is my Python code to solve the full problem:
<a href="https://www.codechef.com/viewsolution/18590032">https://www.codechef.com/viewsolution/18590032</a></p>
<p><strong>Third Test Case:</strong></p>
<p>I will now give a quick description of how my method solves the third test case.</p>
<p>We start by considering the largest element of the matrix $A$. That is $A_{42}=4$. We thus connect nodes $2$ and $4$ with an edge of weight $4$. We then move onto either $A_{23}=3$ or $A_{34}=3$. In both cases we will connect node three to either node $2$ or $4$ with an edge of weight $3$. We then have a graph with nodes $2$, $3$, and $4$ in a single connected component. We can thus skip any components of $A$ that do not involve node $1$. When we get to $A_{13}$, $A_{14}$, or $A_{41}$, we will then add an edge with weight $2$ between node $1$ and any other node. At that point our graph is fully connected and we can stop.</p>
<p>The final matrix is given by</p>
<p>$$A=\begin{bmatrix}0 & 2 & 2 & 2\\2 & 0 & 3 &4\\2 & 3 & 0 & 3\\2 & 4 & 3 & 0\end{bmatrix}$$</p>
<p>and one possible graph is given by</p>
<p><img alt="alt text" src="https://discuss.codechef.com/upfiles/st_im-1.jpg"></p>oconnor_robertThu, 17 May 2018 18:13:46 +0530https://discuss.codechef.com/questions/126885/my-solution-to-s-t-mincut-from-may18disjoint-setstmincutunion-findlong_challengemay18editorialHelp needed in Binary Matrix CF 884Fhttps://discuss.codechef.com/questions/131424/help-needed-in-binary-matrix-cf-884f<p>Hello, I am facing WA in test 7 in problem <a href="http://codeforces.com/contest/884/problem/E">Binary Matrix</a>. Here's my <a href="http://codeforces.com/contest/884/submission/40407003">submission</a>. Can anyone tell me what is wrong in my solution, or provide helpful test cases?</p>taran_1407Mon, 16 Jul 2018 16:27:30 +0530https://discuss.codechef.com/questions/131424/help-needed-in-binary-matrix-cf-884fdisjoint-sethelpcodeforcesADAFARM - EDITORIALhttps://discuss.codechef.com/questions/138334/adafarm-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/ADAFARM/">Practice</a> <br>
<a href="https://www.codechef.com/COOK99A/problems/ADAFARM">Contest: Division 1</a> <br>
<a href="https://www.codechef.com/COOK99B/problems/ADAFARM">Contest: Division 2</a> </p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/alei">Alei Reyes</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/allllekssssa">Aleksa Plavsic</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/taran_1407">Taranpreet Singh</a> </p>
<h1>DIFFICULTY:</h1>
<p>Hard</p>
<h1>PREREQUISITES:</h1>
<p>Centroid Decomposition, Disjoint-Sets, Geometry and a knack of implementation.</p>
<h1>PROBLEM:</h1>
<p>Given an $N$ sided polygon on a 2-Dimensional plane with points numbered from 1 to $N$ given in clockwise order, we are to process $Q$ queries.</p>
<ul>
<li>Join points numbered $u$ and $v$.</li>
<li>Print area of the region where point $(x, y)$ is lying. In case point lies on some border or outside the polygon, print 0.</li>
</ul>
<h1>QUICK EXPLANATION</h1>
<ul>
<li>Divide polygon on triangles by all diagonals we have, and maintain a disjoint set for each triangles storing area of regions in the current union of the set of triangles.</li>
<li>Apply centroid decomposition on tree formed by adding edge between two vertices corresponding to triangles, which share a diagonal. </li>
<li>Answer queries in reverse order, initially all regions split into triangles, getting merged into larger components and answering queries.</li>
<li>Handle points carefully which lie on borders whether yet removed or not.</li>
</ul>
<h1>EXPLANATION</h1>
<p>This problem is a complicated implementation (been saying that a lot lately, but what can I do? :P)</p>
<p>First of all, <strong>Geometry Time</strong></p>
<p>Check if a point P lies on line segment joining A and B.</p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>Length of segment AP + length of segment PB = length of segment AB is the sole condition which guarantees that Point P lies on line segment AB.</p>
<p>More details <a href="https://www.geeksforgeeks.org/direction-point-line-segment/">here</a>.</p>
</div></div>
<p>Check if a point P lies inside triangle ABC if vertices are given in clockwise order.</p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>Two methods, One is to check for every edge of the triangle in clockwise order, if the point P lies on or to the left of any edge, Point is not strictly inside the triangle.</p>
<p>Second method is based on relation that $a(PAB)+a(PAC)+a(PBC) = a(ABC)$ where $a(XYZ)$ denote area of triangle $XYZ$.</p>
<p>More details can be found <a href="https://www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/">here</a>.</p>
</div></div>
<p>Area of triangle ABC, given coordinates of A(Ax, Ay), B(Bx, By) and C(Cx, Cy).</p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>One common formula is $abs(Ax*(By-Cy)+Bx*(Cy-ay)+Cx*(Ay-By))/2$.</p>
<p>Another formula (as used by setter) is $abs((Bx-Ax)*(Cy-Ay)-(Cx-Ax)*(By-Ay))/2$</p>
<p>Side information, calculation of the area of a $N$ sided polygon can be done using Shoelace Formula, which can be found <a href="https://www.geeksforgeeks.org/area-of-a-polygon-with-given-n-ordered-vertices/">here</a></p>
<p>The first formula is just the shoelace formula for $N = 3$.</p>
</div></div>
<p><strong>About Triangles</strong>.</p>
<p>For any polygon, we can represent it as the union of a number of non-overlapping triangles by joining non-adjacent vertices of the polygon.</p>
<p>See image for example</p>
<p><img alt="alt text" src="https://discuss.codechef.com/upfiles/polyToTriangles_zbikbxg.png"></p>
<p>The polygon with $N$ vertices is decomposed into $N-2$ triangles. Also, all triangles do not overlap, thus the area of the polygon is just sum of areas of all these triangles.</p>
<p>So, Beginning with our approach, let us reverse all queries. The problem looks like following.</p>
<p>We now have a polygon having $N$ vertices with some fences added and we have to process two type of queries.</p>
<ul>
<li>Remove fence joining vertices $u$ and $v$.</li>
<li>Print the area of the region containing point $(x,y)$.</li>
</ul>
<p>Though the problem looks still similar, we will see how it is beneficial to merge triangles rather than to split, by using <a href="https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/">Disjoint set Union</a>, Each set initially consisting of one triangle initially, and another array storing areas of the triangles. When we remove a diagonal, Exactly two sets will merge, the regions, which were earlier divided by that diagonal. Areas also get merged. </p>
<p><strong>The real benefit of reversing queries is because it is far easier to get the area of the region, given area of sub-parts. Rather than finding the area of subregions formed due to new diagonal.</strong></p>
<p>Now, we have all small tools ready for solving this problem. By using all these tools, it is possible to solve this problem in $O(N*Q)$ by answering area queries in $O(N)$ by checking all triangles. If point lie inside any triangle, we can print area of the region which contains this triangle. Otherwise, if the query point lies on any fence, we need to check if this fence was removed. If yes, print area of the region. Otherwise, print 0.</p>
<p>Now, $O(N*Q)$ is too slow to solve our problem, so we need an insight about <a href="https://en.wikipedia.org/wiki/Polygon_triangulation">Polygon Triangulation</a></p>
<p><strong>If we have a graph of $N-2$ vertices each representing a triangle, and edge $(A, B)$ for all $A \neq B$ exist if triangle $A$ and triangle $B$ share an edge (not just corner), we get a tree.</strong></p>
<p>Also, consider the following image (Image credits to problem setter).</p>
<p><img alt="alt text" src="https://discuss.codechef.com/upfiles/Triangulation.png"></p>
<p>The yellow region is connected to all regions while no other regions are connected with each other. Also, If we know, that query point say $J$ in the image, is lying to the left of segment DE, We can just ignore Blue and Green Regions, and move toward Red region.</p>
<p>Now, we have a tree of regions.</p>
<p>This gives us a different implementation to answer queries in $O(N)$ worst case. (will be helpful to reach our final solution.)</p>
<p>For every query, just choose any triangle, check if query point lies inside that triangle. If yes, print area of the region containing that triangle. Otherwise, there will be one edge of this triangle, from which query point lies to the left side of the edge. Call this <strong>Special Diagonal</strong> Move toward triangle which shares special diagonal with current triangle. Continue this process until you reach the triangle which contains this triangle, or it is determined that point is outside the polygon.</p>
<p>It is guaranteed that you'll visit all the triangles in the worst case. Also, make sure to check if a point lies on the border of any triangle. If that border is removed, print area of the region containing that border. Otherwise, print 0.</p>
<p>This way too, we get $O(Q*N)$ time complexity, but this forms the base for optimizing this solution faster than a blink of an eye, just by <strong>Divide and Conquer</strong> Technique.</p>
<p>Now, in this solution, once we move from one triangle to other, we never move back, thus reducing the size of search space by at least half the size of current search space, if we apply Divide and Conquer on trees, commonly known as Centroid Decomposition on tree, can read <a href="https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree">here</a>.</p>
<p>We still do the same thing, Choose a starting triangle, check if the point lies inside or on the border of this triangle. If no, we move toward component toward which has the next triangle.</p>
<p>The thing about divide and conquer is, that we have almost the same idea, but just by choosing vertices carefully, we divide the search space into half at every step, resulting in $O(logN)$ steps.</p>
<p>This complexity, combined with $O(logN)$ for usage of maps and other data structures, gives overall $O(Q*log^2 N)$ time complexity which is sufficient to fit the time limit.</p>
<p>As for implementation, I have added line-by-line comments in setter's solution which you may refer for implementation.</p>
<h1>Time Complexity</h1>
<p>Time complexity is $O(Q*log^2 N)$.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/COOK99/setter/ADAFARM.cpp">Setter's solution</a> </p>
<p><a href="http://www.codechef.com/download/Solutions/COOK99/editorialist/ADAFARM.cpp">Editorialist's solution</a></p>
<p>Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)</p>taran_1407Tue, 23 Oct 2018 23:30:42 +0530https://discuss.codechef.com/questions/138334/adafarm-editorialtaran_1407disjoint-setgeometryhardimplementationadafarmcook99centroid-decompPython 3 - TLE in MAGICSTRhttps://discuss.codechef.com/questions/113570/python-3-tle-in-magicstr<p>So, I was trying to solve <a href="https://www.codechef.com/problems/MAGICSTR">the MAGICSTR problem here.</a></p>
<p>After reading <a href="https://discuss.codechef.com/questions/77347/magical-strings-editorial">the editorial</a> and going through some blogs, I made an implementation of the Union-Find Data Structure in Python and tried to solve the problem using it. But I am getting a TLE. <a href="https://www.codechef.com/viewsolution/15599832">Here is the link to my last solution.</a> In the data structure, I used both path compression and union by rank. Please help.</p>
<p>Thanks.</p>dhruvsomaniWed, 04 Oct 2017 19:43:28 +0530https://discuss.codechef.com/questions/113570/python-3-tle-in-magicstrunion-finddisjoint-settlepython3magicstrJABO - Editorialhttps://discuss.codechef.com/questions/3710/jabo-editorial<h1>PROBLEM LINK</h1>
<p><a href="http://www.codechef.com/problems/JABO">Practice</a><br>
<a href="http://www.codechef.com/NOV12/problems/JABO">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>MEDIUM</p>
<h1>PREREQUISITES</h1>
<p><a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure">Disjoint Sets</a>, Simple Math</p>
<h1>PROBLEM</h1>
<p>You are given a Jam Board with R rows and C columns. A row of the jambaord contains a group of 5 points arranged vertically, which are connected with the same metal plate. So you have a grid of 5*R rows and C columns.</p>
<p>You are to simulate the following 4 operations</p>
<ul>
<li>Add a wire connecting two grid points.</li>
<li>Give potential to a grid point.</li>
<li>Remove potential from a grid point.</li>
<li>Check if there is potential difference between two grid points. (Since potential difference leads to LED being on) </li>
</ul>
<h1>QUICK EXPLANATION</h1>
<p>This would be an entirely different problem if we were to allow for removal of a wire that connects two grid points. Since that is not allowed, the problem reduces to maintaining <b>disjoint</b> <b>sets</b> of groups. Also known as <b>Union</b> <b>Find</b>. We have to make a tiny modification though - to maintain the number of sources providing potential to each group.</p>
<p>The number of sources are easy to maintain.</p>
<ul>
<li>Augment the Join method in your Disjoing Sets data structure to add and store the potential on the root for the whole group.</li>
<li>Addition and Removal of a source of potential for a group are simply performed at the root of the group.</li>
</ul>
<h1>EXPLANATION</h1>
<p>Let us assume <b>U</b> is a disjoint set data structure.</p>
<ul>
<li><b>U.init(N)</b> creates a node <b>N</b> and assigns it an independent group.</li>
<li><b>U.Root(N)</b> returns a unique identifier for the group to which <b>N</b> belongs.</li>
<li><b>U.join(A,B)</b> joins the groups which contain <b>A,</b> an which contain <b>B</b> respectively.<ul>
<li>After calling <b>U.join(A,B),</b> <b>U.Root(A)</b> will be equal to <b>U.Root(B)</b></li>
</ul>
</li>
</ul>
<p>We know that the amortized complexity of performing <b>T</b> operations of U is <b>O(U * iA(N))</b>, where <b>iA</b> is the inverse of the <b>Ackermann</b> function (and practivally very very small for very large values of <b>N</b> as well).</p>
<p>We use <b>U</b> and build <b>aU</b>, which helps us maintain the number of sources without any additional complexity.
</p><pre>procedure: aU.init(N) // O(1)
U.init(N) // O(1)
sources[N] = 0 // O(1)
</pre><p></p>
<p><b>aU.Root(N)</b> simply returns <b>U.Root(N)</b>. Of course, we do not have to do any additional calculations for maintaining the number of sources while finding the Root.</p>
<p>We add the number of sources of potential in the <b>Join</b> method.
</p><pre>procedure: aU.join(A,B)
U.join(A,B)
if U.Root(A) has become parent of U.Root(B)
sources[ U.Root(A) ] += sources[ U.Root(B) ]
else
sources[ U.Root(B) ] += sources[ U.Root(A) ]
</pre><p></p>
<p>Now, <b>addition</b> / <b>deletion</b> and <b>lookup</b> of the number of sources of potential on a grid node <b>N</b> can be done by <b>incrementing</b> / <b>decrementing</b> and <b>lookup</b> of <b>sources[ aU.Root(N) ]</b></p>
<p>It remains to mention that considering all grid nodes as separate groups - and joining groups of 5 initially - may create massive blobs of in-memory arrays that might cause thrashing (and slow code). Thus, you can optimize your code by calculating the row-number that a given grid point belongs to and working on the that number. Now, there can be at most <b>500*2500</b> sets.</p>
<h1>SETTERS SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2012/November/Setter/JABO.cpp">here</a>.</p>
<h1>TESTERS SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2012/November/Tester/JABO.c">here</a>.</p>gamabuntaMon, 12 Nov 2012 18:46:00 +0530https://discuss.codechef.com/questions/3710/jabo-editorialnov12mediumeditorialdisjoint-setunion-findANUSAR - Editorialhttps://discuss.codechef.com/questions/43060/anusar-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/ANUSAR">Practice</a> <br>
<a href="http://www.codechef.com/COOK46/problems/ANUSAR">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/anudeep2011">Anudeep Nekkanti</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/gerald">Gerald Agapov</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/dpraveen">Praveen Dhinwa</a> </p>
<h1>DIFFICULTY:</h1>
<p>MEDIUM HARD </p>
<h1>PREREQUISITES:</h1>
<p>Suffix Array, Suffix Tree, dfs, Segment tree, Fenwick Tree or BIT. </p>
<h1>PROBLEM:</h1>
<p>Given a string S and Q queries. In each query you are given an integer F. You need to find out number of substrings of S
which occur at least F times in S. </p>
<h1>QUICK EXPLANATION</h1>
<p><strong>Suffix Array solution:</strong> <br>
Construct suffix array SA of the string S. Create an array LCP such that LCP[i] = lcp(SA[i], SA[i + 1]). Full form of lcp is longest common prefix. </p>
<p>Now the LCP array can be seen as a histogram with each bar having height LCP[i]. Then for some range [i,j] if minimum of [LCP[i], LCP[i+1].. LCP[j]] is m, then it means that there is a substring of length m, which is present at j-i+2 indices in string S. </p>
<p>Using this property we can find the solution in following way. Let D[i] represent the number of substrings which repeat exactly i times. If we can compute the array D, we can easily answer all the queries. For a given frequency F, required answer will be D[F] + D[F+1] + ... D[length of S]. </p>
<p>For a bar of height H (LCP[i] = H), let us assume that we know the largest interval (L[i], R[i]) such that minimum of LCP array over the interval is equal to H, then it means that we have got a substring of length H, which repeats exactly R[i]-L[i]+2 times. (See examples given in the explanation). <br>
We will update the D array accordingly. </p>
<p><strong>Suffix Tree Solution</strong><br>
Construct suffix tree of the string S, then you just need to do a dfs over it and keep updating the count of appearance of substrings.</p>
<h1>EXPLANATION</h1>
<p>First we will explain more about significance of array D and how it helps to solve the problem. Then the next section will elaborate on
different ways of computing L[i] and R[i] for a given histogram H.</p>
<p>Let us take an example string and create its suffix array. Consider the string S = "ABABBAABB".</p>
<table>
<tbody><tr>
<td>
Suffix position in S
</td>
<td>
Suffixes of S
</td>
<td>
LCP array of S
</td>
</tr>
<tr>
<td>
6
</td>
<td>
AABB
</td>
<td>
1
</td>
</tr>
<tr>
<td>
1
</td>
<td>
ABABBAABB
</td>
<td>
2
</td>
</tr>
<tr>
<td>
7
</td>
<td>
ABB
</td>
<td>
3
</td>
</tr>
<tr>
<td>
3
</td>
<td>
ABBAABB
</td>
<td>
0
</td>
</tr>
<tr>
<td>
9
</td>
<td>
B
</td>
<td>
1
</td>
</tr>
<tr>
<td>
5
</td>
<td>
BAABB
</td>
<td>
2
</td>
</tr>
<tr>
<td>
2
</td>
<td>
BABBAABB
</td>
<td>
1
</td>
</tr>
<tr>
<td>
4
</td>
<td>
BBAABB
</td>
<td>
2
</td>
</tr>
<tr>
<td>
8
</td>
<td>
BB
</td>
<td>
Not Defined
</td>
</tr>
</tbody></table>
<hr>
<p>Now A appears 4 times in S. A is the prefix of first 4 suffixes in the suffix array. Minimum of LCP[0], LCP[1], LCP[2] (0 based indexing) is 1 which represents that A has appeared 4 times. </p>
<p>As pointed out in the quick explanation section, we can express LCP array as histogram with following values [1, 2, 3, 0, 1, 2, 1, 2]. You can also very easily
verify the fact that if for some range[i, j], minimum of LCP array is m, then their exists a substring of length m occurring at j - i + 2 positions in the string S.</p>
<p>L[i] for given LCP will be [0, 1, 2, 0, 4, 5, 4, 7]. <br>
R[i] for given LCP will be [2, 2, 2, 7, 7, 5, 7, 7]. </p>
<p>Now let us find out how to update D using LCP. <br>
We will iterate over each possible value in the LCP array (in whichever order you wish), Let the value on which we are currently iterating be V. </p>
<p>As we know that for the range [L[i], R[i]], minimum value of LCP array is equal to V. <br>
Note that there are exactly V substrings (consider any prefix of the suffix corresponding to LCP[i], ie longest common prefix of i and i + 1 in the suffix array, it has size V and hence there will be V prefixes of it). Hence there will V * (D[R[i] - L[i] + 2) substrings repeating (R[i] - L[i] + 2) times. So we will update D[R[i] - L[i] + 2] by adding val * D[R[i] - L[i] + 2] to it.</p>
<p>eg. Let us suppose we have following suffixes in the sorted order.<br>
AA <br>
AAB <br>
AAC <br>
LCP = {2, 2}. <br>
L = {0, 0}. <br>
R = {1, 1}. </p>
<p>When we are iterating over V = 2, Assume we are at position i = 0.
V = 2 and R[i] - L[i] + 2 = 3.
We will add 2 * 3 = 6 into D[3]. In other words it refers to adding substrings A and AA 3 times. </p>
<p>The above mentioned approach has some small <em>pitfalls</em> which need to be taken care of. We are doing some over-counting in the approach. We need to fix that up. There are two kind of issues with the above approach which are explained in detail here.</p>
<hr>
<p><strong>Issue 1</strong> <br>
Let us consider that a string S = ABABAA has following suffixes <br>
A <br>
AA <br>
ABAA <br>
ABABAA <br>
BAA <br>
BABAA </p>
<p>LCP = [1, 1, 3, 0, 2]
L = [0, 0, 2, 0, 4]
R = [2, 2, 2, 4, 4]</p>
<p>When we are iterating over LCP array, Let us assume that current V = 1, If we are at i = 0 (ie at suffix A) we will count that A has occurred exactly 4 times (because R[0] - L[0] + 2 = 4, LCP[0] = 1).
But when are considering V = 2, If we are at position i = 2 (ie we are at suffix ABAA), we have R[2] = 2, L[2] = 2. We will increment the count of D[(R[2] - L[2] + 2)] ie D[2] by 2,
(we are updating count of occurrences of substrings A and AB by 2 more).
But this is not correct, because in this approach we have counted A 6 times, which is wrong (You can easily see that A appears exactly 4 times).</p>
<p>So There is over counting in our current method. We need to somehow get rid of this. Note that at suffix ABAA, the suffix just preceding it is AA.</p>
<p>For V = 2 and suffix ABAA, when we count for A we have already counted the fact that substring A has appeared four times when the V = 1. </p>
<p>So we can not say that all prefixes of length LCP[2] are counted exactly once. Notice that LCP[L[i] - 1] is 1 and hence we are going to recount just the first prefix of suffix ABAA (ie A). So instead of directly saying that there are exactly LCP[i] substrings which appear exactly R[i] - L[i] + 2 times, we will say that there are exactly min(LCP[i], LCP[i] - LCP[L[i] - 1], LCP[i] - LCP[R[i] + 1]) unique substrings appearing exactly R[i] - L[i] + 2 times. If you have not understood this fact, <strong>please</strong> take more examples and convince yourself.</p>
<hr>
<p><strong>Issue 2</strong> <br>
Now let us consider that our suffix array have following suffixes.<br>
A <br>
AB <br>
ACD </p>
<p>Our LCP array will be [1, 1].</p>
<p>As said earlier, we will iterating over LCP and our current V = 1.Assume that we are currently at the suffix A (ie i = 0), we have R[i] = 1.
We will update D[3] by 1 * 3. <br>
When we go to the i = 1, we will also do the same. This amounts to over counting.<br>
For a particular V in the LCP array, When at some point I have considered the range between L[i] and R[i] corresponding to some i (st LCP[i] = V), then I should not re-count the values corresponding to index j (LCP[j] = V) such that j lies in the range L[i] to R[i] because this range has already been considered and it will only amount to over counting. </p>
<p>We can implement this by a two pointer method, We can maintain a pointer 'right' which denote the rightmost index which has been considered. Note that right is always non-decreasing, Hence it will guarantee that our algorithm takes O(N) time.</p>
<hr>
<p><strong>Pseudo Code:</strong> <br>
Let P be a list of lists, P[i] denotes the positions of occurrence of i in LCP array.
eg. If LCP = [1, 2, 0, 1, 2, 1] <br>
Then P will contain three list. P[0] = {2}, P[1] = {0, 3, 5}, P[2] = {1, 4}. </p>
<pre><code>for V = 0 to N:
sz = P[val].size()
// right is maintained for implementing two pointer method.
right = 0;
for j = 0 to sz:
index = P[val][j]
// to take care of the issue 2, dont overcount, always check whether your current element under
// consideration is not inside the range which has already been considered.
if (index >= right):
lo = L[index], hi = R[index]
// len denotes the current number of prefixes of the suffix corresponding to size V.
len = V;
// to take care of the issue 1.
if (hi is defined, ie 0 <= hi < LCP.size()):
len = min(len, val - LCP[hi])
if (lo is defined, ie 0 <= lo < LCP.size()):
len = min(len, val - LCP[hi]);
// add the current prefixes
D[hi-lo+2] += len * (hi - lo + 2);
// update the right pointer
right = index + 1;
</code></pre>
<p>Now only difficulty in the entire algorithm described is to how to compute L[i] and R[i] for a given array LCP.</p>
<h1>Ways of Computing L[i], R[i] for all elements of Array A</h1>
<p>Now you have to solve the following problem. You are given an array A. For each element A[i] you have to find L[i] and R[i] where L[i] is the largest j <= i such that L[k] >= L[i] for all k lying between i and j. Similarly define R[i].
(In other words, For each index i, [L[i], R[i]] denotes the largest range such that all elements have minimum value equal to A[i].)</p>
<p>Now if we can solve the problem of finding L[i], we can easily solve the problem of finding R[i] for each i (We can just reverse the array A and then finding R[i] is exactly the same as finding L[i]). Hence
from now on, we will only look forward to solve problem of finding L[i].</p>
<p>If you have not solved the problem <a href="http://www.spoj.com/problems/HISTOGRA/">HISTOGRA</a> on spoj, then try solving that. There are a lot of ways of solving this problem, you can read <a href="http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html">University of Ulm Local Contest judges solutions for problem H</a> and
<a href="http://www.geeksforgeeks.org/largest-rectangle-under-histogram/">solution mentioned on geeksforgeeks site</a>. I will very briefly go through all of the methods mentioned there. Note that all these methods are explained in the details in the
above given links. You are highly recommended to read those.</p>
<p><strong>Segment Tree Based Solution</strong> <br>
As we know the largest value in the array A can go up to 10<sup> 5 </sup>, Hence our segment tree is made on new array B of size [10^5 + 1]
where B[j] shows that largest index i where j has occurred in the array A. <br>
We scan the array A from left to right. For finding out L[i], we can query the segment tree built on array B to find out the
maximum value in the range [0, B[A[i]]]. <br>
For updating the array B, we can simply add B[A[i]] = i and update the segment tree accordingly. Essentially we have to maintain
the information in the segment tree about the indices of the elements and maximum of each node and<br>
we will go from left to right and will do update and query operations the segment tree accordingly. </p>
<p>For reference solution, you can see <a href="http://www.codechef.com/viewplaintext/3923853">editorialists solution</a> to get an idea of its implementation. There are two segment trees, minSegmentTree
and maxSegmentTree representing finding L[i] and R[i] respectively. Rest details are just similar to things explained before. </p>
<p><strong>Stack Based Solution</strong> <br>
Assume that we maintain a stack. Initially the stack is empty. We go from left to right in the array A, we will pop out the elements in stack which are >= A[i], then the element at the top is the element which
we were searching for, we can easily find its index (For that we can store pair of [value, index] in the stack). L[i] will be the value of the of index of the topmost element in the stack. We also have to add the current element into the stack.</p>
<p>Observe the following important properties: <br>
1. Elements in the stack are always in the increasing order. This fact is very important for correctness of the algorithm.<br>
2. Each element is inserted at most once. Only the inserted elements in the stack are popped out, Hence this ensures that complexity of
the entire algorithm is O(N). </p>
<p>For sample implementation of this idea, you can refer <a href="http://www.codechef.com/download/Solutions/COOK46/Setter/SAR-STACK.cpp">setter solution</a>.</p>
<p><strong>Disjoint Set Union Based solution</strong> <br>
This is also an interesting solution, You should look into this <a href="http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html">link</a> for getting more ideas about the solution. It is left as a home work for the
readers. You can look at <a href="http://www.codechef.com/download/Solutions/COOK46/Setter/SAR-DSU.cpp">setter solution</a> to get an example of working solution.</p>
<h2>Suffix Tree Approach</h2>
<p>You can solve the task easily by using suffix tree structure, You should do dfs over the suffix tree nodes. To get exact implementation details, you can view <a href="http://www.codechef.com/download/Solutions/COOK46/Tester/ANUSAR.cpp">tester's solution</a>.</p>
<h1>AUTHOR'S, TESTER'S AND EDITORIALIST's SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/COOK46/Setter/SAR-STACK.cpp">Author's solution based on stack + suffix array</a> <br>
<a href="http://www.codechef.com/download/Solutions/COOK46/Setter/SAR-DSU.cpp">Author's solution based on DSU + suffix array</a> <br>
<a href="http://www.codechef.com/download/Solutions/COOK46/Tester/ANUSAR.cpp">Tester's solution based on suffix tree</a> <br>
<a href="http://www.codechef.com/viewplaintext/3923853">Editorialists's solution based on segment tree + suffix array</a> </p>dpraveenMon, 19 May 2014 00:24:35 +0530https://discuss.codechef.com/questions/43060/anusar-editorialcook46disjoint-setmedium-hardsuffix-arraysegment-treesuffix-treeseditorialstack