ABROADS - Editorial

Problem Link:

Practice

Contest

Difficulty:

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 ith.

  2. Boolean array D, where D[j] is true, if the road numbered the jth 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 xth 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 xth. 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 ith 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)).

Solution for all subtasks:

We will use the data structure called Disjoint Set Union.

Let’s have N elements numbered 1 to N and N sets. Initially, the ith set contains the ith 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 Xth), let’s maintain the value of P[X], denoting the total population of the cities in the Xth 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 Xth and the city numbered the Yth.


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

6 Likes

Add the problems to practice section! And nice editorial!

setter and tester’s code not opening…

How to use DELETE in DSU ? DSU uses path compression

@ayushtomar: Process the queries offline from last to first, so instead of deleting edges you’re actually adding them.

2 Likes

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

@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

Why is my code giving wrong answer for small subtasks?

https://www.codechef.com/viewsolution/9029061

https://www.codechef.com/viewsolution/9029150

@likecs Naive DFS solution works faster (0.01s). Any idea why BFS is slower ?

2 Likes

@admin Why the hell are the codechef’s editorialist’s and tester’s code NEVER visible ?

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!

You basically don’t delete.
When you process the queries in the opposite order, you just add new edges instead of deleting.

Sir sir _/_

@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.

@theweblover007
Tester’s code is visible.

1 Like

@likecs
please tell me what is that priority queue thing. My code is taking time because I am finding max region in O(n).