Harolinch's blog

By Harolinch, history, 7 months ago, In English,

can anyone help me to solve this problem http://codeforces.com/contest/152/problem/E (Garden), i read the editorial but i didn't understand it, may any one clarify it more

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

7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't read the editorial but I can try to explane my solution

Let's use dynamic programming. Define the state as A[mask][x][y] mask is a subset of inportant squares (i-th bit is 1 if i-th important square is in subset), x and y are coordinates. So there are maximum 2**k * n * m different states. A[mask][x][y] is minimum possible number of damageded flowers to cover at least all important squares of subset 'mask', cell with coordinates (x, y) and connect them all to a single component. So the answer is minimum value from A[2**k — 1][1..n][1..m]: 2**k — 1 is full set of important squares must be covered, any other cell is accepted and they all must be connected to a single component.

The trivial states are states where bitcount(mask) == 1: we can easy go from each important square and calculate minimum possible damaged flowers required to connect any cell to the current important square.

Let's go over all masks in non decrising number of bits and calculate next state as A[mask][x][y] = Min(A[mask_1][x][y] + A[bit][x][y]), where x, y are any cell. mask == mask_1 | bit where bitcount(bit) == 1 Just try to connect to existing solution any other important square

This gets best solution for several cells, but some of them can still have non minimum result and we need to do minification using the same approach as for calculating trivial states.

Answer value will be found as Min(A[2**k — 1][1..n][1..m]) and the exact configuration can be restored in a usual way for dynamic progrmming when you just store the states from which you get current state.