×

Medium

Pre-requisites:

Disjoint Set Union

Problem:

Maintain the size of the most populated region after each query.

Explanation:

Solution for the subtask 1 (21 points):

The solution of this subtask is to use breadth first search after applying each query to find all the regions' city sets. If we have all the regions' cities sets, we can easily find the maximal populated region.

Let's describe this approach in more details.

Let's denote:

1) Integer array $P$, where $P[i]$ is the population of city numbered the $i$th.

2) Boolean array $D$, where $D[j]$ is true, if the road numbered the $j$th has been destroyed, and false otherwise.

3) Adjacency list $Adj$. We can store this list efficiently, for example, using STL vector in C++. For every adjacent node, let's store a structure, containing the following fields:

• The number of the adjacent node, denoted by $node$.
• The ID of the corresponding edge, denoted by $edge$.

Having all this, we can process the queries in the following way:

• P $x$ $y$ - change the population of the city numbered the $x$th to $y$. In this case, we just make a single assignment: $P[x]$ = $y$. This operation is performed in $O(1)$.

• D $x$ - destroy the road numbered the $x$th. Again, this is just a single assignment ($D[x]$ = true), so it is also performed in $O(1)$.

Now, how to find the size of the maximal populated region.

We will make use of queue data structure.

Let's iterate through all the nodes. Whenever we find a node which was not included in any connected component, we start the breadth first search. Let's describe it in brief:

• Add the first node of the region to the queue.
• While the queue is not empty, pick the node from the head of the queue and add all its' not yet added neighbors.

Let's denote Boolean array $Used$, where $Used[i]$ is true, if $i$th city was added to queue, and false otherwise.

The pseudocode of the algorithm for finding the size of the most populated region is given below.

ans = 0; For i := 1 to N used[i] = false For i := 1 to N if not used[i] queue.add(i); population = 0; while queue is not empty do curNode = queue.pop(); population += P[curNode]; For j := 0 to Adj[curNode].Length if ((not D[Adj[curNode][j].edge]) and (not Used[Adj[curNode][j].node])) Used[Adj[curNode][j].node] = true; queue.add[Adj[curNode][j].node]; ans = Max(ans, population); return ans 

The complexity is $O(Q*(N+M))$.

We will use the data structure called Disjoint Set Union.

Let's have $N$ elements numbered $1$ to $N$ and $N$ sets. Initially, the $i$th set contains the $i$th element.

Disjoint Set Union maintains two basic operations:

1) Uniting two sets.

2) Finding the set containing the given element.

The amortized time per operation is $O(\alpha(N))$, where $\alpha(N)$ is less than $5$ for all remotely practical values of $N$.

Note that you don't have to output the size of the most populated region before reading the next query. So, you can read all the queries in advance and solve the task in reverse order.

Assume that all $Q$ queries were performed. Let's add all connected components (regions) to the DSU. Obviously, we can determine the most populated region.

Let's create the DSU with $N$ elements denoting the cities and $N$ sets denoting the regions. Along with each set (say, the $X$th), let's maintain the value of $P[X]$, denoting the total population of the cities in the $X$th set. Now, the DSU corresponds to the road system with $N$ cities, given populations and without roads. Note that we should take the populations that are obtained after the performing of all the queries.

Now, assume that all the queries has already been performed. Then, there is a set of roads, which has not been deleted. Let's add all of them. The addition of the road is simply merging two corresponding sets in the DSU structure. Since we have one non-standard operation here, namely, handling the sizes of the regions, letТs give a pseudocode for it.

Given that we need to add a road connecting the city numbered the $X$th and the city numbered the $Y$th.

 Merge (X, Y) setX = FindSet(X) setY = FindSet(Y) if (setX == setY) return; SetParent(setY, setX) P[setX] = P[setX] + P[setY] 

Now, let's "rollback" the queries starting with the last one. The "rollback" of the change population query is changing the value of the corresponding $P[X]$, and the "rollback" of the road deletion query is adding the road like we've described above.

Meanwhile, we can also maintain a priority queue of an STL set for determining the size of the largest region quickly. This way, we can answer on the maximal region population in $O(\log N)$.

The complexity is O($N + M \alpha(N) + Q \log N$).

Setter's Solution:

Can be found here

Tester's Solution:

Can be found here

This question is marked "community wiki".

719436377
accept rate: 0%

19.7k350498541

 1 @ayushtomar: Process the queries offline from last to first, so instead of deleting edges you're actually adding them. answered 27 Dec '15, 16:16 157●1●8 accept rate: 10% Sir sir _/_ (27 Dec '15, 19:52) arpn4★ @AnonymousBunny While we process the queries in reverse order, if the query encountered is of "p" type then how we would be knowing, what was the population before that query. (30 Dec '15, 20:13) arpit7281★
 0 Add the problems to practice section! And nice editorial! answered 27 Dec '15, 15:01 492●1●10 accept rate: 14%
 0 setter and tester's code not opening.. answered 27 Dec '15, 15:29 0★a____ 79●11 accept rate: 20%
 0 How to use DELETE in DSU ? DSU uses path compression answered 27 Dec '15, 15:42 141●1●5 accept rate: 4% You basically don't delete. When you process the queries in the opposite order, you just add new edges instead of deleting. (27 Dec '15, 16:27)
 0 I found out the connected components for after each query and found out the max in those components. Was it an overkill for this problem? https://www.codechef.com/viewsolution/9027824 answered 27 Dec '15, 18:06 21●2 accept rate: 0%
 0 @aminoacid, it was not an overkill for this problem. As told by the editorialist as well, use bfs can do the trick for 30 points. I think what went wrong in your case was the recusrive call stack because of the tarjan algorithm you applied, giving you segmentation fault (stack size reached the upper limit due to large number of recursive calls). You may refer to my solution for 30 points, similar to the way editorialist has written. https://www.codechef.com/viewsolution/9024537 answered 27 Dec '15, 18:55 6★likecs 3.7k●22●79 accept rate: 9% @likecs please tell me what is that priority queue thing. My code is taking time because I am finding max region in O(n). (07 Jan '16, 18:26) arpit7281★
 0 Why is my code giving wrong answer for small subtasks? https://www.codechef.com/viewsolution/9029061 https://www.codechef.com/viewsolution/9029150  answered 27 Dec '15, 19:25 1 accept rate: 0%
 0 @admin Why the hell are the codechef's editorialist's and tester's code NEVER visible ? answered 31 Dec '15, 12:39 101●1●6 accept rate: 0% @theweblover007 Tester's code is visible. (31 Dec '15, 22:21) arpit7281★
 0 Hello, I've been solving this problem for about a month (with breaks OFC), but I still can't get something; My DSU solution passes through all subtask's tests, but it doesn't work on main tests; Yes, I used "long long" and gave range of (1e5 * 5 + 1), everywhere, please can you say my mistake or make tests visible, it's really getting erratating, thanks! answered 09 Jan '18, 15:25 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,556
×487
×114
×47
×28
×13

question asked: 22 Dec '15, 06:12

question was seen: 4,208 times

last updated: 10 Jan '18, 12:43