11443 - Tree in a Grid

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11443 - Tree in a Grid

Post by baodog » Thu Apr 10, 2008 4:20 am

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

Post by Robert Gerbicz » Thu Apr 10, 2008 8:34 pm

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...

Post Reply

Return to “Volume 114 (11400-11499)”