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 ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
Flood all the island fully and then start decreasing the water level. The connectivity components can be easily maintained using disjoint sets.
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.
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?
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.
You didn't answer to this question: "Do you know about disjoint sets?". I mean this.
Sorry, I know disjoint sets (Union Find), I started the last answers writing this but somewhat I erased it.