Dynamic One-Dimensional Puzzle
National Olympiad — National round (2017 season)
Submission name: puzzle.cpp
Problem summary
At each numbered position choose one available distinguishable puzzle piece. Its left/right side types are 1 (flat), 2 and 3; matching adjacent sides are 1 with 1, or 2 with 3. Both outside ends must be flat. Count arrangements modulo 1,000,000,007 initially and after every piece insertion/deletion.
Source clarification. The constraints print N≥9, but the official example uses N=3. The implementation and explanation support that example and all positive N.
Input
M N Q; M triples position left right; Q updates type position left right (1 inserts, 2 deletes).
Output
The initial count, then the count after each update.
Constraints
N ≤ M ≤ 100,000; N ≤ 50,000; Q ≤ 250,000; valid deletions. The printed lower bound N≥9 conflicts with the N=3 official example; the algorithm also supports N≥1.
Worked example
An independently prepared example for this explanation.
Input
8 3 5 1 1 1 1 1 2 1 2 1 2 1 2 2 3 3 2 1 3 3 2 1 3 3 2 1 3 3 1 2 3 2 1 1 2 3 2 1 2 3 2 1 3 2 1
Output
2 3 1 2 3 5
Solution analysis
- Use three states representing the required type on the next piece’s left side. A piece with left type l and right type r contributes one transition from l to complement(r), where complement swaps 2 and 3 and keeps 1. The position’s 3×3 matrix counts its available transitions.
- Concatenating adjacent ranges multiplies their transition matrices in left-to-right order. Store these products in a segment tree. Updating one piece changes one matrix entry and only O(log N) ancestor products. Entry (flat,flat) of the whole product is the answer.
- In the official example the initial pieces give two compatible chains. Inserting a final piece with left type 3 and flat right end adds a third. Two otherwise identical inserted pieces are distinguishable, so their transition multiplicities add rather than becoming a Boolean flag.
Why it works
Each matrix transition is one distinguishable piece satisfying the incoming boundary. Matrix multiplication sums over the shared required side type and multiplies independent choices in the two ranges; it therefore counts exactly all compatible concatenations. Induction over the segment tree proves each node stores the correct range count. Starting and ending in the flat state enforces both external boundary conditions.
Watch out. Side types 2 and 3 complement each other; they do not match themselves. Matrix multiplication order matters. Equal pieces still represent separate choices.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
#include<vector>
// Algorithm: Use three states representing the required type on the next piece’s left side.
using namespace std;
const long long MOD=1000000007;
struct Matrix{
array<array<long long,3>,3>value{};
};
Matrix multiply(const Matrix&a,const Matrix&b){
Matrix result;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
result.value[i][j]=(result.value[i][j]+a.value[i][k]*b.value[k][j])%MOD;
}
}
}
return result;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m,n,q;
cin>>m>>n>>q;
int size=1;
while(size<n){
size*=2;
}
vector<Matrix>tree(2*size);
for(int i=n;i<size;i++){
for(int j=0;j<3;j++){
tree[size+i].value[j][j]=1;
}
}
const int complement[3]={0,2,1};
for(int i=0;i<m;i++){
int position,left,right;
cin>>position>>left>>right;
tree[size+position-1].value[left-1][complement[right-1]]++;
}
for(int node=size-1;node;node--){
tree[node]=multiply(tree[2*node],tree[2*node+1]);
}
cout<<tree[1].value[0][0]<<'\n';
while(q--){
int type,position,left,right;
cin>>type>>position>>left>>right;
int node=size+position-1;
long long&entry=tree[node].value[left-1][complement[right-1]];
entry=(entry+(type==1?1:MOD-1))%MOD;
for(node/=2;node;node/=2){
tree[node]=multiply(tree[2*node],tree[2*node+1]);
}
cout<<tree[1].value[0][0]<<'\n';
}
}