mutsuki's blog

A strange problem
By mutsuki, history, 23 months ago, In English

I came up with a strange problem and find it hard for me to solve it, so i write this topic to ask for help.

Consider a point grid, for example, a 2x3 point grid may looks like this:

o o o
o o o

Now we connect each pair of adjacent points.

o--o--o
|  |  |
o--o--o

As we have some points and edges, it now becomes a graph! Now we are gonna find one of its spanning tree. Like this one:

o--o--o
|  |
o  o--o

We can see that this tree is a 'rectangle'. Trees obtained by this way is called a rect-tree. Now, consider this rect-tree:

n=6
1 6
1 2
2 3
2 4
4 5

We can turn it back into a grid. Like this:

1  2  3
o--o--o
|  |
o  o--o
6  4  5

The problem is here:

Give you a rect-tree, please turn it back into a grid. Output the points in the grid from top to bottom, left to right.

Input: Integer n,m, then n*m-1 lines which describes the tree.

Output: n*m numbers.

Case 1: Input 2 3

1 6
1 2
2 3
2 4
4 5

Output:

1 2 3
6 4 5

At first, i thought this problem was a piece of cake and can be easily solved with 2 < n,m < 5000. However, now I find it hard to solve even when 2< n,m < 5. Can anyone help me?

By the way, here are some more testcases.

Input:

3 3
1 2
1 3
1 4
4 5
4 6
5 7
4 8
6 9

Output:

2 1 3
5 4 6
7 8 9

It looks like this

o--o--o
   |
o--o--o
|  |  |
o  o  o
  • Vote: I like it
  • +43
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
23 months ago, # |
  Vote: I like it +24 Vote: I do not like it

For small constraints you can brute force all rect-trees and then solve your problem using tree equivalence.

As for the problem from theoretical perspective, I think that it is not solvable in polynomial time, but I have no formal argument yet.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your solution! This solution may work when n,m is very small because there are about 40000 rect-trees when n=4, m=4. However when n become bigger(even a little bigger, 6), the solution won't work again. Now i'm wondering if this is a constructive problem.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did you count the number of all rect-trees or only non-equivalent? The second number should be much smaller, so the precalc solution should still work for slightly bigger numbers.

      And for $$$n, m > 10$$$ I don't think it is solvable at all (if we don't include Monte Carlo stuff). I'd propose to start looking for the reduction of some problem that is widely believed not to be solvable in polynomial time (and, possibly, even NP-hard).

      → Reply
»
23 months ago, # |
  Vote: I like it -29 Vote: I do not like it

There are at least 5 more acceptable output for each query (you can make them by flipping and rotating the original output). In my opinion, you should take the most appear element then put it in the middle of the grid, then spanning each branch from the middle to the edge, always consider the most related to the mid first.

For example, in your last test case: (please note that * is blank) - we got 4 appear the most, then we got:

*  *  *
*  4  *
*  *  *
  • Then we have 1 appears 3 times, that means 1 is linked to 3 other elements (include 4 means 1 is near the middle), we put it like this:
*  1  *
*  4  *
*  *  *

or like this:

*  *  *
*  4  1
*  *  *

and so on...

  • In this step I'll take the first one after putting 1 into the table, we put 2 elements that is connected to 1:
3  1  2
*  4  *
*  *  *

and agree that the above solution is acceptable as 3 and 2 are not connected to any element other than 1

  • In this step, we can see that 5 appear twice, connected to the middle (4), we put it near 4:
3  1  2
*  4  *
*  5  *
  • Consider all other elements connect to 5 are single (that means only connected to 5), then put them to the place you want:
3  1  2
*  4  *
7  5  *
  • Now, we have 6 to put in the table, but this is a bit tricky: you can not put it at the left of 4, once you come to this step, you know we have to backtrack (check in many different ways, whether you have enough place or will it contradict other statement, it doesn't matter). After backtracking, we put it the right of 4, with 9 follows:
3  1  2
*  4  6
7  5  9
  • Now put in the last element:
3  1  2
5  4  6
7  5  9

You can see my output is ACCEPTABLE, and in conclusion, my solution use backtracking alongside greedy to solve this problem, hope this help!

P/S: Sorry about my bad English, I translated myself, and also sorry if I can't make it clearer.

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    What if there is a loop during the construction process?

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very interesting. So this is a Greedy+DFS solution? I'm not sure if this can work on some strange cases like:

    o--o--o
|  |
o  o  o
   |  |
o--o--o

    In this case there is no node with 4 degrees, and both 3-degree nodes are not in the center. And the most important thing is, if you put the one of the 3-degree node in the center, it becomes unsolvable, like this.

    o--o  o
   |  |
o--o  o
   |  |
   o--o--o
    → Reply
»
23 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I find it as hard as finding a Hamiltonian path; replacing a few edges in a Hilbert curve would make a complex case for backtracking solutions.

If you're interested, 102191J - Graph to Grid is similar but on a 2xN grid, and the graph is not necessarily a tree.

→ Reply