Machine Lines
National Olympiad — Regional round (2021 season)
Submission name: machines.cpp
Problem summary
Each production line lists distinct machine types in their required order. Determine whether one ordering of all used types can preserve every line order.
Input
K followed by K lines, each containing its length and the machine types in order.
Output
1 if such an ordering exists; otherwise 0.
Constraints
2 ≤ K ≤ 100; machine types are integers from 1 to 20000; types are distinct within a line.
Worked example
An independently prepared example for this explanation.
Input
2 3 1 2 3 4 1 3 5 6
Output
1
Solution analysis
- For each line, add a directed edge from each machine type to its immediate successor. Preserving these adjacent relationships automatically preserves all earlier/later pairs in the line by transitivity.
- Apply Kahn’s topological sorting algorithm to the graph of used types. Repeatedly remove a vertex with indegree zero and decrease its successors’ indegrees. Count how many used vertices can be removed.
- In the displayed first official test, edges require 1 before 2 before 3 and 1 before 3 before 5 before 6; order 1,2,3,5,6 works. In the second official test, the requirements include 1 before 4 before 150 before 1, forming a cycle.
Why it works
A feasible ordering must respect every directed edge, so a directed cycle makes it impossible. Conversely, if Kahn’s algorithm removes every used vertex, the removal order respects every edge and hence every complete original line. If vertices remain, each remaining vertex has a predecessor, implying a cycle in this finite graph.
Watch out. Only consecutive edges are needed. Repeated edges across lines are safe if indegrees and edge removals count each copy consistently. The official statement displays five separate tests; the example here is its first test.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<queue>
// Algorithm: For each line, add a directed edge from each machine type to its immediate
// successor.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<vector<int>>graph(20001);
vector<int>indegree(20001,0);
vector<bool>used(20001,false);
int lines;
cin>>lines;
for(int line=0;line<lines;++line){
int length,previous=-1;
cin>>length;
for(int i=0;i<length;++i){
int type;
cin>>type;
used[type]=true;
if(previous!=-1){
graph[previous].push_back(type);
++indegree[type];
}
previous=type;
}
}
queue<int>ready;
int total=0;
for(int type=1;type<=20000;++type){
if(used[type]){
++total;
if(indegree[type]==0){
ready.push(type);
}
}
}
int removed=0;
while(!ready.empty()){
int type=ready.front();
ready.pop();
++removed;
for(int next:graph[type]){
if(--indegree[next]==0){
ready.push(next);
}
}
}
cout<<(removed==total?1:0)<<'\n';
}