## 11443 - Tree in a Grid

Moderator: Board moderators

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### 11443 - Tree in a Grid

I think this requires O(n^2) dp, where n is 200x8 max, with a bitmask approach.
However, I can't find the proper recursive relationship.
I try to use decompose, but if there is more than one edge coming
out of a node, I don't know how to ensure there is no cycle in the rest of the tree.
It has to be two disjoint trees rooted at the given node I try to decompose.
So there is this decomposition into disjoint forests that span all nodes, but won't fit
in memory (reuires O(n^3) memory space).

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: 11443 - Tree in a Grid

Now I think how to avoid TLE on this problem, I haven't coded so far:

Spanning tree a graph if and only if it hasn't got a circle and is connected.
Computation by dp: suppose that you know the number of graphs that hasn't got circle and it is possible to finish it to a spanning tree
, (*) so there is no component which hasn't got points on the current column, for example this is invalid:

Code: Select all

``````.-.S.
|S|S|
.S.S.
SSSS|
.-.-.
``````
. Let A[{x_1,...x_k},{y_1,...,y_l},{z_1,...,z_m},...,] is the number of possible configurations if the x_1,...,x_k points on the current column are connected, y_1,...,y_l are connected and so on, these sets is a partition of the numbers from 1 to c or from 1 to c-1, depending on what is the current stage: horizontal or vertical.
For example: let c=4 and A[{1,4},{2},{3}] horizontal stage and you want to extend this to a vertical stage.
Note that not not all possible configurations are valid, since for example A[{1,3},{2,4}] is invalid, it isn't possible to connect 1,3 and 2,4.
If the last column is vertical you want to extend it by horizontal elements or it is horizontal then by vertical elements and it is also possible that a given element is given so you have no choice for that. You have to assure that * is true, by dp the computation is possible in O(row*2^c*config(c)) time and using O(2^c) memory, where config(c)<=c!, but this is a lot smaller because there are many invalid configurations.
The answer will be A[{1,2,...,n}] because all points has to be in the same component.

Ps. and try to avoid the circles...