i have ben thinking about this problem for a few weeks now, here is the problem:
given a grid of size n x n and T ammount of starting and ending positions in the grid, for each position determine if its possible to start from the starting position, visit all vertex in the grid exactly once, and finish in the finishing position
for example: n=4, t=3 start=(1,1), end=(4,4)
start=(1,1), end=(3,2)
start=(1,2) end=(2,1)
answer shound be yes,yes,no
(N<=10), (T<=20)
how to solve this problem? i could only think of pruned recursive backtracking (if the current vertex is pos, next vertex we visit is x, check if the degree of adjacent unvisited vertex (other then x), and reduce them by 1, if any of them is less then 2 (less then 1 for target vertex), then we cannot visit x next).
I believe this problem appeared on opencup once, tho i dont remeber when
Seems like it is ifsmirnov's favorite problem, maybe he'll help. There is a linear in terms of the size of input solution with many
if's.http://www.cs.technion.ac.il/~itai/publications/Algorithms/Hamilton-paths.pdf
I cannot seem to open this in my browsers, how to open this?
I've seen such a problem in a training camp (not sure that it was the opencup though). The solution for your variant of the problem is extremely simple: provided 2 ≤ n, m, the solution exists if and only if the parity of the starting and finishing cells allows to make a Hamiltonian path (kinda x1 + y1 + x2 + y2 + nm is odd or something like that). I don't have any easy proof, though.
However, the problem I recall was not only to check whether the path exists but to build it. And this one, as Kostroma said, is solved with a bunch of if's. You just have to write some primitives, like "go from a corner to a corner", "go from a corner to any cell", "go from any cell to any other cell, provided there is a vertical splitting line" and so on. A piece of cake, ugh? I thought so. Until I realized that I already have a dozen of cases in my solution, ~30 lines of code each, and the end is not even close.
Hello, if i use that formula, for starting (1,2) and finish (2,1) on 3x3 grid it would be odd, while there is no solutiob
I didn't say that this is the formula, I said it looks like this.
In your case there are 5 white cells and 4 black, and you want to have a path of length 9 start and end in a black cell. This is clearly impossible. Can you figure out why? Can you describe it with a formula?
i see... so if we color the squares black and white. so if we are in a black square, we can only go to a white square, vice versa
in 3x3 grid, there are 5 white and 4 black, so if we start at a black and visit all the squares, it will be like b-w-b-w-b-w-b-w-b (impossible because only 4 blacks)
if its white, then it will be like w-b-w-b-w-b-w-b-w (possible), so in an odd grid, its only impossible if the start or end is a white using same logic, for even grid, if the start and end color is the same, then there is no solution. a square (x,y) is white if the parity of x and y is the same, or (x+y) = 0 mod 2, black otherwise
if(nxn is odd), we need (x1+y1) even, and (x2+y2) even
if(nxn is even), we need (x1+y1+x2+y2) even (same color)
is this correct? now it is proven that there can be a path, if the following condition is true, but do we only need the following conditions to be true, for there to be a path?
This?
https://ipsc.ksp.sk/2013/real/problems/g.html
Editorial of this problem is available.
https://ipsc.ksp.sk/2013/real/solutions/booklet.pdf
But I don't solve it yet :)
I feel I've seen a similar problem somewhere else.
BTW, for this problem, I think DP managing connected component(appending cell one by one) works.