aajjbb's blog

Live Archive — 4627 Islands
By aajjbb, 11 years ago, In English

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 ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Flood all the island fully and then start decreasing the water level. The connectivity components can be easily maintained using disjoint sets.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          You didn't answer to this question: "Do you know about disjoint sets?". I mean this.

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Sorry, I know disjoint sets (Union Find), I started the last answers writing this but somewhat I erased it.

            → Reply