You are not logged in. Please login at www.codechef.com to post your questions!

×

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 $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))$.

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 $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".

asked 22 Dec '15, 06:12

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719436377
accept rate: 0%

edited 27 Dec '15, 14:24

admin's gravatar image

0★admin ♦♦
19.7k350498541


Answer is hidden as author is suspended. Click here to view.

answered 30 Dec '15, 16:48

sarvagya3943's gravatar image

4★sarvagya3943
(suspended)
accept rate: 36%

edited 30 Dec '15, 16:48

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

link

answered 27 Dec '15, 16:16

AnonymousBunny's gravatar image

5★AnonymousBunny
15718
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★

Add the problems to practice section! And nice editorial!

link

answered 27 Dec '15, 15:01

rishivikram's gravatar image

5★rishivikram
492110
accept rate: 14%

edited 27 Dec '15, 15:01

setter and tester's code not opening..

link

answered 27 Dec '15, 15:29

a____'s gravatar image

0★a____
7911
accept rate: 20%

How to use DELETE in DSU ? DSU uses path compression

link

answered 27 Dec '15, 15:42

ayushtomar's gravatar image

5★ayushtomar
14115
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) additya19983★

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

link

answered 27 Dec '15, 18:06

aminoacid's gravatar image

4★aminoacid
212
accept rate: 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

link

answered 27 Dec '15, 18:55

likecs's gravatar image

6★likecs
3.7k2279
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★
link

answered 27 Dec '15, 19:25

himanshuarora2's gravatar image

3★himanshuarora2
1
accept rate: 0%

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

link

answered 31 Dec '15, 12:39

theweblover007's gravatar image

2★theweblover007
10116
accept rate: 0%

@theweblover007 Tester's code is visible.

(31 Dec '15, 22:21) arpit7281★

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!

link

answered 09 Jan '18, 15:25

hatelogic's gravatar image

0★hatelogic
11
accept rate: 0%

edited 09 Jan '18, 15:28

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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