PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author & Editorialist: Alei Reyes
Tester: Suchan Park
DIFFICULTY:
TIE-BREAK
PREREQUISITES:
Graphs
PROBLEM:
A vibrating path is a sequence of distinct vertices V_1, V_2, \ldots, V_K such that the following conditions are satisfied:
- 1 \le K \le 256
- For each valid i, the edge (V_i, V_{i+1}) exists in the graph.
- For each valid i and j \le i-2, the edge (V_i, V_j) does not exist in the graph.
- For each valid i: If i \gt 1, let’s consider the graph without the edge (V_{i-1}, V_i); otherwise, consider the original graph. In this graph, the weight of the edge (V_i, V_{i+1}) is the minimum of weights of all edges adjacent to V_i.
Your task is to make the graph K-vertex-colourable by hitting the vertices. When a vertex u is hit, all the edges on the vibrating path with maximum length that starts at u are removed, the cost of hitting the i-th vertex is C_i.
Explanation
Why such path is called vibrating? I was thinking that a graph could be considered as a real rigid body where the vertices are plates interconnected by ropes, and we can hit its vertices with a hammer. When a vertex u is hit, it starts vibrating and the weakest rope (u,v) breaks (the edge is removed from the graph). Moreover the force is transmitted through the rope, v starts vibrating, and its weakest adjacent edge (v, w) breaks. The process keeps repeating but in no moment there should be two adjacent vibrating vertices. The constraint K \le 256 is there just to make easier to write the checker.
When K=1 the problems is to remove all edges of the graph, for K=2 we have to convert the graph into bipartite, and so on. A general strategy is to find a subgraph that can be coloured with K colours and then remove the extra edges by hitting the vertices, another idea is to keep hitting the vertices until we can find a valid colouring.
Initially the length of the vibrating paths is very small, according to how the vertices are hit the length of the paths can be increased. There are many heuristics that can be used to determine in which order the vertices should be hit, e.g greedily hit the vertex with the longest vibrating path, the one with the highest or lower degree, etc.
The first AC during contest was by agadmator, in his first submission he sorted the vertices in increasing order of cost and hitted each vertex until all its adjacent edges are removed (so the final graph 1-colourable). Then he improved the solution by considering colours, and hitted a vertex only if is not possible to assign a colour different than its neighbours. This solution got 0.5 points at the time when the editorial was written.
run_timeterror was second 3 days before the end of the contest (with a score of 0.87). Let S be the set of the 86 vertices with smaller cost and with non-zero degree. To decide which vertex hit he choosed 20 vibrating paths starting from vertices randomly chosen from S and hitted the one with the longest vibrating path. runtime_terror’s algorithm keeps hitting vertices until it doesn’t find a valid colouring, for colouring a graph he shuffles the vertices and assigns to each vertex a colour equal to the mex of their adjacent vertices.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int rint(char nxt){
char ch=getchar();
int v=0;
int sgn=1;
if(ch=='-')sgn=-1;
else{
assert('0'<=ch&&ch<='9');
v=ch-'0';
}
while(true){
ch=getchar();
if('0'<=ch && ch<='9')v=v*10+ch-'0';
else{
assert(ch==nxt);
break;
}
}
return v*sgn;
}
typedef long long int uli;
const int mxn=1e4+10;
const int mxm=1e5+10;
const int mxl=256;
set<pair<int,int> >e[mxn];
set<int>s[mxn];
const int mxq=1e5;
int deg[mxn];
set<pair<int,int> >du;//(deg[u], u)
int maxlen=0;
int cost[mxn];
int vis[mxn];
void hit(int u){
vector<int> path={u};
while(path.size()<mxl){
if(e[u].empty())break;
int v=e[u].begin()->second;
int w=e[u].begin()->first;
bool ok=true;
for(int i=0;i+1<int(path.size());i++){
int x=path[i];
if(x==v || s[x].count(v)){
ok=false;
break;
}
}
if(!ok)break;
path.push_back(v);
e[u].erase({w,v});
e[v].erase({w,u});
s[u].erase(v);
s[v].erase(u);
u=v;
}
maxlen=max(maxlen,(int)path.size());
for(int x:path){
du.erase({deg[x],x});
--deg[x];
if(x!=path[0] && x!=path.back())--deg[x];
if(deg[x]>0)du.insert({deg[x],x});
}
}
bool bip(int n){
for(int i=0;i<n;i++)vis[i]=-1;
for(int it=0;it<n;it++){
int u=it;
assert(vis[u]>=-1);
if(vis[u]==-1){
queue<int>q;
q.push(u);
vis[u]=1;
while(!q.empty()){
u=q.front();
assert(vis[u]>=0);
q.pop();
for(int v:s[u]){
if(vis[v]==-1){
vis[v]=1-vis[u];
q.push(v);
}
else if(vis[v]!=1-vis[u])return false;
}
}
}
}
for(int i=0;i<n;i++)assert(vis[i]>=0);
return true;
}
int main(){
clock_t tStart = clock();
int n=rint(' ');
int m=rint(' ');
int k=rint('\n');
assert(1<=k&&k<=4);
for(int i=0;i<n;i++){
cost[i]=rint(i==n-1?'\n':' ');
assert(1<=cost[i] && cost[i]<=512);
}
set<int>w;
for(int i=0;i<m;i++){
int u=rint(' ');
int v=rint(' ');
int c=rint('\n');
assert(1<=u&&u<=n);
assert(1<=v&&v<=n);
assert(1<=c&&c<=m);
assert(w.count(c)==0);
w.insert(c);
--u,--v;
deg[u]++;
deg[v]++;
e[u].insert({c,v});
e[v].insert({c,u});
s[u].insert(v);
s[v].insert(u);
}
for(int i=0;i<n;i++){
du.insert({deg[i],i});
}
vector<int>ans;
int cnt=0;
while(!du.empty()){
int u=du.rbegin()->second;
if(rand()%10<=7) u=du.begin()->second;
ans.push_back(u);
hit(u);
if(cnt%10==0 && k>1 && bip(n))break;
cnt++;
}
printf("%d\n",int(ans.size()));
for(int x:ans){
printf("%d ",x+1);
}
puts("");
if(k==1)memset(vis,0,sizeof vis);
for(int i=0;i<n;i++)assert(vis[i]>=0);
for(int i=0;i<n;i++)printf("%d ",vis[i]+1);
puts("");
return 0;
}