Minimum Shift Alignment
Preview mode. Log in to edit, run, submit, and save progress.
Minimum Shift Alignment
A production wall shows several circular binary strips, all with the same length. In one move, a strip may be rotated left or right by one cell. The operator wants to choose one column and rotate every strip until that column contains a 1 in all strips. For each wall snapshot, report the minimum total number of single-cell rotations needed. If any strip has no 1 at all, the alignment is impossible. Input Format: The first line contains t. Each case starts with n and m, the number of strips and the length of each strip. The next n lines contain binary strings of length m. Output Format: For each case, print the minimum total rotations, or -1 if no common 1-column can be formed.
Examples
1 3 5 00100 10000 00010
3
Explanation: Each row can be rotated until a 1 reaches the chosen column. The output is the smallest total rotation count among all possible columns.
Approach hint
Rows are circular, so column 1 and column m are neighbors.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.