QUEHEA - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Alei Reyes
Tester: Hasan Jaddouh
Editorialist: Praveen Dhinwa

DIFFICULTY:

medium hard

PREREQUISITES:

data structures, fenwick tree, segment tree, number of connected component, number of intervals inside an interval

PROBLEM:

There are total n people. Each person has his best friend a_i. A person admires himself and all the people whom his best friend admires. A guild is defined as largest group of persons such that for any two people in the group, there is a person whom both admire.

You are given few queries, in each query, you are given a range [L, R], you have to answer total number of guilds when all the persons who are not in the range [L, R] stop admiring their best friend’s admirers (i.e. they now admire themselves only). Each query is independent of other query.

EXPLANATION:

Understand the structure of underlying friendship graph
The underlying directed graph representing the friendship relation, will have a special structure. Firstly a person will have exactly one best friend, means that out degree of each vertex will be 1. However, it might be the case, there could be a lot of people who have a person as a best friend, meaning that in degree of a vertex could be larger than one, or could even be zero. These conditions ensure that graph will of formed of some lines and cycles which might contain some incoming lines. Please see the below image for some examples.

A guild in this graph will be composed of a connected component. You can notice that in a connected component, for every set of two vertices, there will be a vertex who is admired by both. You can see this easily in the line case. In case of cycle with incoming lines, you can verify it by taking these three cases.

  • Both the vertices belong to cycle.
  • One belongs to cycle and other to the line
  • Both of them belong to the line.

So, the problems asks us to find number of connected components in the underlying graph. From the structure of the graph, you can notice that the number of connected components will be equal to number of vertices - number of edges + number of cycles. So, you have to maintain all these three parameters for answering each query.

  1. Number of vertices
  2. Number of edges
  3. Number of cycles

Number of vertices

It’s the easiest one. It will be equal to R - L + 1.

Number of edges

Let us represent each edge by its endpoints by two variables, from and to, denoting that the edge goes from vertex from to vertex to. Let us first pre-calculate the intervals for the edges [from, to], where for each index i, such that from = i, and to = f_i, where f_i denotes the best friend of i-th person.

Finding number of edges in range [L, R] is same as finding number of above defined intervals contained inside the range [L, R]. Note that if f_i belongs outside the range, then it won’t be counted.

Number of cycles

You can handle the cycles (with some incoming lines into it) in the similar way. Represent a cycle by two values, the smallest and the largest index of some vertex present in it.

Finding number of intervals lying inside a given range.

So, we want to number of integer i, f_i, such that L \leq i, f_i \leq R. Let us create an array of arrays, vec[i], where vec[i] stores the right end point of the intervals whose left end point is i. Now, you can build a segment tree over it, whose each node will contain sorted order of right endpoints e in the segment tree node. While answering a query, if the query contains the segment node completely, you can just find the number of elements < R, by a simple binary search.

This method will give you a complexity of \mathcal{O}({(log \, n)}^2) complexity per query.

Tester’s Solutions:

Setter’s solution
Tester’s solution

2 Likes
2

Counting points within any rectangle can be done offline - split the rectangle into four that contain the origin of the coordinate system (like with 2D prefix sums), sort them, add points sorted by one coordinate and use a Fenwick tree to count the number of added points within any range [0,R]. This has O(Q\log) time complexity; in this case, just due to Fenwick trees, since the coordinates are already small.

1 Like
3

I solved it via a different approach, a few seconds after contest ended, using Mo’s algorithm:

We need to add/remove nodes during Mo’s algorithm and update the number of connected components accordingly. Consider the best friend relationship as an edge from node i to best[i]. For each node, keep track of the number of edges to and from undeleted nodes. Say it is Count[i].

When deleting a node, we have 3 cases:

  1. The node is not a part of a cycle: the increase in number of connected components is Count[i]-1.

  2. The node is a part of cycle, and no other node of the cycle is deleted currently. The increase in this case is Count[i]-2.

  3. The node is a part of cycle, but some other nodes of the cycle have been deleted. The increase will again be Count[i]-1.

Node insertion can be done similarly.

So we can insert and delete nodes in O(1) time. Total time complexity: N\sqrt{N}

Link to Code

5 Likes
4

gvaibhav21, could you explain how you arrived at the total time complexity? I considered your approach but concluded it could TLE. How did you upper-bound the total number of insertions/deletions you need to do?

Also, how do you make sure you keep your the current number of connected components updated after each insertion/deletion in O(1)? Don’t you need to assign labels to each node in affected connected components, thus making the worst case O(n)?

5

I limited the number of insertions and deletions using Mo’s algorithm: https://blog.anudeep2011.com/mos-algorithm/

We can insert/delete nodes in O(1) time, using the formula’s involving Count[i] in the 3 different cases I have described in the answer. You don’t need to explicitly maintain the connected components, just their number.

1 Like
6

image provided is not visible . could u fix that?

1 Like