Hi all,
I need your help to solve this problem (task mines day 2 Baltic OI 2010). I heard that it can be solved using Gaussian Elimination (but I haven't had detail ideas). According to what I know, Gaussian Elimination runs in O(N^3) and the space is O(N^2). I tried to transform this problem to gaussian elimination version. I ended up with this transformation:
1. Now define (x,y) into a number (we number every cells start from 1 to N*M)
2. Build N*M equations and save it in gaussian table. So table[i][j] has value 1 if node i and j are adjacent, otherwise 0
3. Input[i][j] (the given input) means how many bombs in cell(i,j) then table[transform(i,j)][N*M+1]=Input[i][j]
4. Solve it using gaussian elimination.
Unfortunately, for above-mentioned solution, I need O((N*M)^2) space and O((N*M)^3) time which is far enough to solve this problem. Any helps and ideas are appreciated. Thank you for your attention.
I am looking forward for a reply.
I need your help to solve this problem (task mines day 2 Baltic OI 2010). I heard that it can be solved using Gaussian Elimination (but I haven't had detail ideas). According to what I know, Gaussian Elimination runs in O(N^3) and the space is O(N^2). I tried to transform this problem to gaussian elimination version. I ended up with this transformation:
1. Now define (x,y) into a number (we number every cells start from 1 to N*M)
2. Build N*M equations and save it in gaussian table. So table[i][j] has value 1 if node i and j are adjacent, otherwise 0
3. Input[i][j] (the given input) means how many bombs in cell(i,j) then table[transform(i,j)][N*M+1]=Input[i][j]
4. Solve it using gaussian elimination.
Unfortunately, for above-mentioned solution, I need O((N*M)^2) space and O((N*M)^3) time which is far enough to solve this problem. Any helps and ideas are appreciated. Thank you for your attention.
I am looking forward for a reply.
My solution is iterative. Firstly we should know how to solve this problem when m=1. It's not difficult. Mines' location uniquely determined by the presence of mines in the first cell.
Second we should understand how to calc sum of third line prefixes. sum[i]=a[i][1]-a[i][0]. Indexes are 0-based. a is array with mines number and sum is number of mines neer ith position in third line. Now we can find mines position in third line. Using this idea we can find positions of mines in line with 0-based 3*k+2 lines for all k. If the last of these lines is last or there is only one line after it we can find location in other lines using this idea.
If there are too lines after last line we can use it for columns instead of rows. And there is no tests when algorithm don't work both on rows and columns.
Sorry for my bad english.
let's use example:
3 5
24531
46631
34310
can you please write the value of table sum[] and a[][] for sample input?
Thanks in advance.
Thank you for your explanation and help :)
at first So we solve row 3*k+2 for all k
then if there are 2 lines left, we can solve column 3*k+2 right?
I understand how to solve:
1. If there is no row left (n=3*k+2)
2. If there is one row left
3. How about 2 rows left?
I read your post and I agree that we can solve column.
So one question if it left 2 column, what should we do?
X means you got the answer (there is bomb or no bomb):
+/? you haven't known it
5 5
++X++
++X++
XXXX
++X??
++X??
now how to solve:
??
?? part?
Thanks in advance.
5 5
++X++
++X++
XXXXX
++X??
++X??
I don't know how this problem can be solved using Gaussian Elimination... But perhaps you can use flow network and The Ford–Fulkerson algorithm. Say, each cell (of both grids) be a node of our network. And, in addition, S and T nodes. Say, u is a node corresponding to a cell of Henio's grid and v is a node corresponding to a cell of the other one. Then c(S, u) = 1; c(v, T) is the number in the cell v of Indrek's grid. c(u, v) = 1 if the corresponding cells of Henio's grid are adjacent, and c(u, v) = 0 otherwise. All other capacities are equal to 0. (It would be better if you assume that an edge is not exists if the corresponding capacity is equal to 0). Then we compute the maximum flow (from S to T). A cell corresponding to node u contains a mine if and only if f(S, u) = 1. So you need at most O((W*H)^2) time. But it seems to me that this algo works faster (maybe i'm not right).
I think, kuniavski 's solution is better, though
Please correct me if I'm wrong
example:
2 2
11
11
Re-number u
12
34
Re-number v
56
78
Connect
0(source) to 1 with capacity 1; 0(source) to 2 with capacity 1; 0(source) to 3 with capacity 1; 0(source) to 4 with capacity 1
//node u to adjacent node in v
1 to 5,6,7,8 with capacity 1
2 to 5,6,7,8 with capacity 1
3 to 5,6,7,8 with capacity 1
4 to 5,6,7,8 with capacity 1
// to sink
5 to 9(sink) with capacity 1(s[1][1])
6 to 9(sink) with capacity 1(s[1][2])
7 to 9(sink) with capacity 1(s[2][1])
8 to 9(sink) with capacity 1(s[2][2])
Thanks
Yes, everything is correct.
In addition, you can use any heuristic modification. For example, before Ford-Fulkerson you can write fast greedy algorithm to find any flow. Perhaps in this problem such modification would be effective.
2 2
1 1
1 1
the answer should be:
2 2
X.
..
I have tried it, while I got 4(the value for max flow)
which means there are 4 bombs right?
but there should be 1 bomb in this case
ohh, you are right, there is a mistake. That's pity... But I think it can be fixed. Let's assume that c(S, u) = the number of the cells adjacent to cell u (on Henio's grid) plus one (cell u itself), and modify the algorithm so that f(S, u) always is either 0 or c(S, u) (i.e. it's value can't belong to [1; c(S, u) - 1]). It seems to be possible, but the solution becomes bulky.
In your example: c[0, 1] = c[0, 2] = c[0, 3] = c[0, 4] = 4. All other capacities are not changed. The value of the max flow is 4. f(0, 1) = 4; f(0, 2) = f(0, 3) = f(0, 4) = 0. Cell u contains a mine if and only if f(S, u) > 0 (or, equivalently, f(S, u) = c(S, u)). So, the answer is
2 2
X.
..
I hope, this solution is right because the Ford-Fulkerson theorem is still right with our modification. Although, it's not nessesary for you to write it because now you know kuniavski 's solution wich seems to be better and more simple :-)