PROBLEM LINK:
Author: Aniswar Srivatsa Krishnan
Editorialist: Aniswar Srivatsa Krishnan
DIFFICULTY:
Hard
PREREQUISITES:
Graph Algorithms, Math.
PROBLEM:
Given a k-Square configuration, solve it!
\qquad \qquad \qquad \qquad \qquad \qquad (example of a move)
EXPLANATION:
The solved configuration has all positive numbers, with each number in reading order across rows then columns. To check if a configuration is solved, loop through the rows, then loop through the columns, making sure that the first number is 1 and each subsequent number is exactly one more than the previous. This procedure checks the value of each of the k^2 elements in the configuration in O(1) time, so it takes O(k^2) time in total.
There are 2k possible moves (s, i) for s in (“row”, “col”) and i in {0,...., k-1}. For each move, copy the input configuration in O(k^2) time, and then reverse and negate the row or column affected by the move. Doing this for all moves then takes O(k^3) time.
Each coordinate of a cubie originally at position (x,y) is transformed by a move by a reflection, so can only ever be in row y or (k - 1) - y and column x or (k - 1) - x, i.e. one of four positions. In addition, a cubie may be rightside-up or upside-down, so each cubie may exist in at most one of eight oriented positions, leading to at most 8k^2 configurations of the square. A tighter upper bound of 4k^2 is possible by noting that a cubie can only exist in a position in one orientation.
Run a breadth-first search on a graph having vertices corresponding to configurations of the k-Square and an edge between two configurations when one can be transformed into the other via a single move. Start the search with the initial configurations, and when the solved configuration is found, return a shortest solving sequence of moves to reach the solved state by following parent pointers along the BFS tree back to the original configuration. When processing a configuration, compute its neighboring configurations using the algorithm from step 2 in O(k^3) time. Since breadth-first search processes each of O(c^{k^2}) vertices at most once, and O(k^3) work is performed per vertex, this search takes O(k^3c^{k^2}) time.
SOLUTION:
Setter's Solution (Python)
from collections import deque
def is_solved(config):
"Return whether input config is solved"
k=len(config)
for i in range(0,k):
for j in range(0,k):
if config[i][j] != k*i + j + 1:
return False
return True
def move(config, mv):
"Return a new configuration made by moving config by move mv"
k = len(config)
(s, i) = mv # s in ("row", "col") and i in range(k)
config1=[]
for l in range(k):
config1.append(list(config[l]))
config=config1
if s=="row":
config[i].reverse()
for j in range(k):
config[i][j]=-config[i][j]
else:
col=[]
for j in range(k):
col.append(config[j][i])
col.reverse()
for j in range(k):
config[j][i]=-col[j]
return tuple([tuple(row) for row in config])
def solve_ksquare(config):
"Return a list of moves that solves config"
parent, solved = bfs(config)
i=solved
path=[]
while i!=config:
path.append(parent[i][1])
i=parent[i][0]
return path[::-1]
def bfs(config):
k=len(config)
parent={config:[config,()]}
q = deque([])
q.append(config)
while q:
curr=q.popleft()
for i in range(k):
nex = move(curr,('col',i))
if nex not in parent:
parent[nex]= [curr,('col',i)]
if is_solved(nex):
return parent, nex
q.append(nex)
for i in range(k):
nex = move(curr,('row',i))
if nex not in parent:
parent[nex]= [curr,('row',i)]
if is_solved(nex):
return parent, nex
q.append(nex)
return parent , config
def main():
n = int(input())
config=[]
for i in range(n):
con=[]
ks = input().split()
for j in range(n):
k = int(ks[j])
con.append(k)
con=tuple(con)
config.append(con)
config = tuple(config)
moves = solve_ksquare(config)
print(len(moves))
for move in moves:
print(str(move[0])+" "+str(move[1]))
if __name__ == "__main__":
main()