Two Edges and Distances
National Olympiad — National round (2023 season)
Submission name: graph.cpp
Problem summary
Choose four distinct vertices u1,v1,u2,v2 with edges u1–v1 and u2–v2, and finite distances between u1,u2 and v1,v2. Minimize the sum of those two distances.
Input
n, followed by upper-triangular adjacency strings: row i describes edges from i to i+1 through n−1.
Output
The minimum distance sum, or −1 if no valid four vertices exist.
Constraints
1 ≤ n ≤ 5000; the graph is simple and undirected.
Worked example
An independently prepared example for this explanation.
Input
4 111 11 1
Output
2
Solution analysis
- A valid choice implies two disjoint edges in one connected component. Whenever such a choice exists, there is a simple path with three edges, giving an upper bound of four. The answer can therefore only be 2,3,4, or −1. A sum of two is equivalent to a four-cycle.
- For every vertex, enumerate pairs of its neighbors. If a pair has already appeared for a different center, those centers and the pair form a four-cycle. Otherwise store the common-neighbor relation as bitsets. Until a four-cycle is found each vertex pair is recorded at most once, so this enumeration is O(n²).
- Without a four-cycle, a sum of three is possible exactly when a component with at least four vertices contains a triangle, or when there is a five-cycle. A triangle is found when an edge’s endpoints have a common neighbor. After ruling triangles out in eligible components, a five-cycle exists exactly when the two endpoints of some edge have a common vertex in their distance-two bitsets. In the complete four-vertex sample a four-cycle immediately gives two; a four-vertex path gives four, while a star has no two disjoint edges and gives −1.
Why it works
A sum of two requires both connecting distances to be one and hence a four-cycle, and every four-cycle gives such a choice. For sum three, join its length-one connection and length-two connection with the two selected edges. If the intermediate vertex repeats one of the four endpoints, there is a triangle with an additional vertex; otherwise these edges form a five-cycle. Both structures give sum three. If neither occurs, a simple three-edge path gives four. The code tests existence of that path by examining an edge whose endpoints each have another distinct neighbor; this also excludes stars and isolated triangles.
Watch out. A component with four vertices can still be a star, which has no valid four-vertex choice. Ignore isolated triangles when testing answer three. Store the common-neighbor relation symmetrically.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<string>
#include<cstdint>
// Algorithm: A valid choice implies two disjoint edges in one connected component.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<vector<int>>graph(n);
for(int i=0;i+1<n;++i){
string row;
cin>>row;
for(int j=i+1;j<n;++j){
if(row[j-i-1]=='1'){
graph[i].push_back(j);
graph[j].push_back(i);
}
}
}
int words=(n+63)/64;
vector<vector<uint64_t>>common(n,vector<uint64_t>(words,0));
for(int center=0;center<n;++center){
const auto&neighbors=graph[center];
for(int i=0;i<static_cast<int>(neighbors.size());++i){
for(int j=i+1;j<static_cast<int>(neighbors.size());++j){
int a=neighbors[i],b=neighbors[j];
uint64_t bit=uint64_t(1)<<(b%64);
if(common[a][b/64]&bit){
cout<<"2\n";
return 0;
}
common[a][b/64]|=bit;
common[b][a/64]|=uint64_t(1)<<(a%64);
}
}
}
vector<int>component(n,-1),componentSize;
for(int start=0;start<n;++start){
if(component[start]!=-1){
continue;
}
int id=static_cast<int>(componentSize.size());
vector<int>order(1,start);
component[start]=id;
for(int i=0;i<static_cast<int>(order.size());++i){
for(int next:graph[order[i]]){
if(component[next]==-1){
component[next]=id;
order.push_back(next);
}
}
}
componentSize.push_back(static_cast<int>(order.size()));
}
bool hasPath=false;
for(int a=0;a<n;++a){
for(int b:graph[a]){
if(a>=b||componentSize[component[a]]<4){
continue;
}
if(common[a][b/64]&(uint64_t(1)<<(b%64))){
cout<<"3\n";
return 0;
}
if(graph[a].size()>=2&&graph[b].size()>=2){
int otherA=graph[a][0]==b?graph[a][1]:graph[a][0];
int otherB=graph[b][0]==a?graph[b][1]:graph[b][0];
if(otherA!=otherB||graph[a].size()>2||graph[b].size()>2){
hasPath=true;
}
}
for(int word=0;word<words;++word){
if(common[a][word]&common[b][word]){
cout<<"3\n";
return 0;
}
}
}
}
cout<<(hasPath?4:-1)<<'\n';
}