Swapping Mouse Blocks
National Olympiad — National round (2013 season)
Submission name: mice.cpp
Problem summary
A permutation of 1..N describes which feeder each mouse uses. One move swaps two adjacent blocks of exactly K elements, preserving order inside each block. Decide whether the permutation can be sorted.
Input
N K, followed by the permutation.
Output
1 if sorting is possible, otherwise 0.
Constraints
4≤N≤100000; 2≤K≤N/2.
Worked example
An independently prepared example for this explanation.
Input
4 2 3 4 1 2
Output
1
Solution analysis
- Every moved element changes its position by exactly K. Therefore its position modulo K is invariant: value p at zero-based position i must satisfy (p−1) mod K=i mod K. Reject immediately if this fails.
- Think of the K residue classes as rows. One block swap exchanges one neighboring pair in every row, so every row permutation changes parity together. Their initial parities must therefore all agree. Compute each row’s parity from its cycle decomposition: a cycle of length L contributes L−1 modulo 2.
- These two conditions are also sufficient. Sort the last residue row by whole-block swaps, then repair successive earlier rows using pairs of offset swaps that induce three-cycles in the row being repaired while restoring all lower rows. Three-cycles can sort any even row permutation; the shared parity condition rules out a remaining isolated transposition. For 3,4,1,2 with K=2 both rows are swapped, so one block swap sorts it; 3,4,2,1 fails the residue condition.
Why it works
The residue and equal-parity conditions are necessary by the move description. For sufficiency, first use aligned swaps to sort the bottom row, making every row even. The composition of two block swaps starting one row apart gives a three-cycle in the current row and restores lower rows; using adjacent three-cycles reduces that row until only its last two positions can remain inverted. Its even parity excludes that final inversion. Induct upward over rows. Thus all rows, and hence the full permutation, can be sorted exactly when the checks pass.
Watch out. Total permutation parity alone is insufficient: compare parity separately in every residue class. The invariant uses position and value with the same indexing convention.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
// Algorithm: Every moved element changes its position by exactly K.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count,block;
cin>>count>>block;
vector<int>permutation(count);
bool valid=true;
for(int i=0;i<count;i++){
cin>>permutation[i];
permutation[i]--;
valid=valid&&permutation[i]%block==i%block;
}
if(!valid){
cout<<0<<'\n';
return 0;
}
vector<bool>visited(count,false);
vector<int>parity(block,0);
for(int i=0;i<count;i++){
if(!visited[i]){
int length=0;
int current=i;
do{
visited[current]=true;
length++;
current=permutation[current];
}
while(!visited[current]);
parity[i%block]^=(length-1)%2;
}
}
for(int row=1;row<block;row++){
if(parity[row]!=parity[0]){
valid=false;
}
}
cout<<(valid?1:0)<<'\n';
}