Harta's blog

Need help for this problem
By Harta, 14 years ago, In English
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.
  • Vote: I like it
  • +12
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
I had 100 on this problem.
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.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Oh, there is an error. We should not count prexix sums. We shoud count sums of connected bloks of 3 cells.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thank you for replying. Well, I'm still not clear about your solution.
    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.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      a[][] is what you had write.

      sum fror third line are {2(4-2),2(6-4),1(6-5),0(3-3),0(1-1)}. Using that we can understand that anser for third line is {1,1,0,0,0}. As for me 1-0 is mor comfortable than X-. so I will use them. Values in brekets are explanations how numbers had been recived.
      Then Sum for second line is {1(3-2),2(4-2),2(3-1),1(1-0),0(0-0)} and answer is {0,1,1,0,0}

      Sum for First line is {1(2-1),2(4-2),3(5-2),2(3-1),1(1-0)} ans answer is {0,1,1,1,0}

      So answer for all test is

      01110
      01100
      11000.

      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Maybe you didn't understand what is sum?

      sum for i line is:
      sum[0]=ans[i][0]+ans[i][1]
      sum[1]=ans[i][0]+ans[i][1]+ans[i][2]
      sum[2]=ans[i][2]+ans[i][2]+ans[i][3]
      ...
      sum[m-2]=ans[i][m-3]+ans[i][m-2]+ans[i][m-1]
      sum[m-1]=ans[i][m-2]+ans[i][m-1]

      where ans[i][j] is 1 if there is mine in (i,j) ans 0 if there is no mine ans m is sizeof of line.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I fully understand now.
        Thank you for your explanation and help :)
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Please correct me if I'm wrong.
    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.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      sorry it's
      5 5
      ++X++
      ++X++
      XXXXX
      ++X??
      ++X??
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Well, I don't know how to solve the problem. The only idea that i have (ans it's enough) to transponate matrix a (solve for matrix simetric to it). There is no test where both sizes are 3*k+2
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        ow.. I see.. Thx for your very nice solution.
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thx for replying. I don't really understand kuniavski's solution. I understand yours and I will try it. Can you help me with kuniavski's solution. Thanks for your attention
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    btw should we differentiate the new number for u and v?
    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
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        if input is
        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
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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 :-)

          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            yeah I have tried kuniavski's solution, but I failed to get the solution (I have no idea too) when it left 2x2 fields. do you have any idea?
            → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Do you mean my or kuniavski's solution? (Sorry, English is not my native, so sometimes I have some difficulties with understanding)
              → Reply
              • 14 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                np. My english is not that good too. I'm talking about kuniavski's solution
                → Reply
                • 14 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  Honestly, I have no ideas too... I didn't try to understand his solution fully before. But now a have understood it and I see the bug too. I don't know how to fix it.
                  → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
The official solutions for all tasks are now available at the following location http://www.ut.ee/boi/?item=boi.tasks.sol.
→ Reply