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
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.
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.
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).
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:
or like this:
and so on...
and agree that the above solution is acceptable as 3 and 2 are not connected to any element other than 1
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.
What if there is a loop during the construction process?
Very interesting. So this is a Greedy+DFS solution? I'm not sure if this can work on some strange cases like:
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.
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.