### aajjbb's blog

By aajjbb, 6 years ago,

Hi, I'm trying to solve this problem: Link

I know how to solve it in O(N * M) per query (using bfs or dfs) to find the components in the matrix obeying the constraints, but this problem asks for a faster approach (matrix can be 1000 * 1000, and 10^5 queries), how to do it ?

• 0

 » 6 years ago, # |   0 Flood all the island fully and then start decreasing the water level. The connectivity components can be easily maintained using disjoint sets.
•  » » 6 years ago, # ^ |   0 I'm still thinking how to code this idea, what's the expected complexity to search the new components to be inserted, isn't it still O(N * M) ? Using a map to store all cells with an height 'P' would decrease the time, but the map access overhead would make it infeasible as well.
•  » » » 6 years ago, # ^ |   0 Why map? Just sort them, sorting an array of 10^6 element is pretty feasible.You won't search components, you'll merge them. Do you know about disjoint sets?
•  » » » » 6 years ago, # ^ |   0 This cleared something to me. Now I have in mind to sort them in non-increasing by their height, them keep track of the number of components and keep join cells as long as my flood decreases, but I'm lost in how to merge this components.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 You didn't answer to this question: "Do you know about disjoint sets?". I mean this.
•  » » » » » » 6 years ago, # ^ |   0 Sorry, I know disjoint sets (Union Find), I started the last answers writing this but somewhat I erased it.
•  » » » » 7 weeks ago, # ^ |   0 I don't understand