VBR - Editorial

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;
  }

agadmator’s solution

run_timeterror’s solution

1 Like

My initial solution was same as that of agadmator-
Hit the minimum cost vertex (with degree>0 obviously) at any stage until we detach the whole graph and make it 1-colorable.
Optimization 1- For k=2, we can stop when graph becomes bipartite.

Optimization 2- For k=3/4, we can use Welsh–Powell Algorithm (It’s quite obvious) to check if the graph becomes 3/4 colorable. If the max degree of any vertex is 3 then the graph becomes sure-shot 4 colorable ( Graph must have become 4 colorable before that as well). Ran this algorithm on some random test cases and got good results. It stopped even when max degree was around 17. (Graph must have become 4 colorable before I stopped as well but getting the exact stop point is definitely NP).

Optimization 3- Instead of taking vertices in exactly ascending order, I randomized the first few vertices and it definitely improves score.
I didn’t inculcate of longest vibrating path in choosing the vertices which I now think I should’ve chosen.

1 Like