APUZZLE - Editorial

Problem Link - A Puzzle

Problem Statement

You are given two N×N square arrays of integers. Your task is to find out if the second one can be obtained from the first by a legal sequence of moves.

There are two kinds of moves:

Column Move: You may pick any column of the array and rotate it up or down by one step. For example, consider the following array:

12 29 40  3
39 25 14 12
14 71  9 61
47 21 53 11 

Rotating the fourth column of this array up by one step gives

12 29 40 12
39 25 14 61
14 71  9 11
47 21 53  3 

Row Move: You may pick any row of the array and rotate it to the right or left by one step. For example, rotating the third row of the array above to the left by one results in

12 29 40 12
39 25 14 61
71 9  11 14
47 21 53  3 

Continuing, we could now rotate the first row to the right by one and get

12 12 29 40
39 25 14 61
71  9 11 14 
47 21 53  3 

A legal sequence of moves consists of a single column move followed by any sequence of row moves. Thus, the sequence of moves carried out above is a legal sequence of moves.

Given, two arrays, you task is to find if the second one can be obtained from the first by any legal sequence of moves.

Approach

The solution checks every possible starting state of the array after a single column move and verifies if the second array can be obtained by performing row moves from this state. For each column, rotate its elements upward or downward to create new intermediate arrays. For each intermediate array, check if all rows in the transformed array can match their corresponding rows in the target array through circular shifts. This involves iterating over each row and attempting to align it with the target row by shifting the row left or right. If successful, record the moves used. If all rows align for any intermediate array, the answer is “YES”; otherwise, after checking all columns, the answer is “NO”.

Time Complexity

The complexity is O(N^3) because we evaluate all N columns, perform O(N^2) operations for the rotations, and validate each state row-wise.

Space Complexity

The space complexity is O(N^2), as additional storage is required for the intermediate states of the arrays during the transformations.