Align Cyclic Sequences
National Olympiad — National round (2018 season)
Submission name: puzzle.cpp
Problem summary
Several equal-length integer sequences may be rotated left, one operation moving the first element to the end. Find the minimum total operations making all sequences equal, or −1.
Input
m, n, then m rows of n values.
Output
The minimum total number of left rotations, or −1.
Constraints
2 ≤ m ≤ 20; 2 ≤ n ≤ 100; 1 ≤ values < 10000000.
Worked example
Input and output for the worked example discussed below.
Input
3 5 1 2 3 4 5 3 4 5 1 2 5 1 2 3 4
Output
4
Solution analysis
- Any common final sequence must be one of the n rotations of the first sequence. Enumerate that target rotation rather than trying arbitrary combinations of all m shifts.
- For a fixed target, scan shifts 0…n−1 of every row and take its smallest matching shift. If any row has no matching rotation, that target is impossible. Sum the minimal shifts and keep the smallest feasible total.
- The sample can align all rows to [5,1,2,3,4], using shifts 4,2,0, total 6, but [3,4,5,1,2] costs 2,0,2, total 4 and is optimal. Repeated values may create several matching shifts; choose the smallest.
Why it works
Every feasible common target appears among the first row’s rotations, and once a target is fixed each row’s cost is independent, so summing its minimum matching shifts is optimal for that target.
Watch out. A shift must move left, not right. Match whole sequences, not just their first element. Periodic sequences can have more than one valid shift.
Commented C++17 solution
An independently written complete program with standard headers.
// Every feasible common target appears among the first row’s rotations, and once a target is fixed each row’s
// cost is independent, so summing its minimum matching shifts is optimal for that target..
#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
int rows,length;
cin>>rows>>length;
vector<vector<int>>values(rows,vector<int>(length));
for(auto&row:values){
for(int&value:row){
cin>>value;
}
}
int answer=numeric_limits<int>::max();
for(int target=0;target<length;target++){
int total=0;
bool possible=true;
for(int row=0;row<rows;row++){
int best=length;
for(int shift=0;shift<length;shift++){
bool equal=true;
for(int index=0;index<length;index++){
if(values[row][(index+shift)%length]!=values[0][(index+target)%length]){
equal=false;
break;
}
}
if(equal){
best=shift;
break;
}
}
possible=possible&&best<length;
total+=best;
}
if(possible){
answer=min(answer,total);
}
}
cout<<(answer==numeric_limits<int>::max()?-1:answer)<<'\n';
}