SOPC013 Editorial

PROBLEM LINK:

Practice
Contest

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()
1 Like