KayacanV's blog

Usaco > Asteroids
By KayacanV, 11 years ago, In English

Usaco > 2006 > november > gold > Asteroids

question { Problem 1: Asteroids [Gary Sivek, 2004]

Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid.

Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot. This weapon is quite expensive, so she wishes to use it sparingly. Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.

PROBLEM NAME: asteroid

INPUT FORMAT:

  • Line 1: Two integers N and K, separated by a single space.

  • Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and column coordinates of an asteroid, respectively.

SAMPLE INPUT (file asteroid.in):

3 4 1 1 1 3 2 2 3 2

INPUT DETAILS:

The following diagram represents the data, where "X" is an asteroid and "." is empty space:

X.X

.X.

.X.

OUTPUT FORMAT:

  • Line 1: The integer representing the minimum number of times Bessie must shoot.

SAMPLE OUTPUT (file asteroid.out):

2

OUTPUT DETAILS:

Bessie may fire across row 1 to destroy the asteroids at (1,1) and (1,3), and then she may fire down column 2 to destroy the asteroids at (2,2) and (3,2). }

/////////////////////////////////////////////

I have one more question about this problem. Is there a good way to find which rows and columns

  • Vote: I like it
  • -1
  • Vote: I do not like it

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

Seems like you could simply interpret the input as an NxN 2-D array then use a greedy algorithm.

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

    What greedy algorithm exactly did you mean? Because none should work :D

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

      You are right, my idea is not correct. Sorry about that :)

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

It seems to be the same thing as Codechef problem KMHAMHA; editorial here

→ Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

You'd better search about "Network-Flow" or "Bipartite-Graph".

Let's assume graph have two set " row and column ", each element is node.

and, the point that locate asteroid is edge. row->column or column-row directional edge.

assume we have source and sink, answer is "the minimum number of edge that remove until no path source->sink" and, it's equivalent that "the maximum number of flow"

this theory is "Min-Cut-Max-Flow", and will use DFS or BFS

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

Assume you have a bipartite graph in which one part represents rows and other represents columns.
You have an edge between two vertices iff there's an asteroid on the intersection of the corresponding row and column.
So you just need to find the size of the minimum vertex cover in this graph.
According to the Konig's theorem, it's equal to the size of the maximal matching. And it can be easily found using Kuhn's algorithm or Hopcroft–Karp algorithm.
Good luck!

→ Reply