PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author & Editorialist: Alei Reyes
Tester: Felipe Mota
DIFFICULTY:
Hard
PREREQUISITES:
Tree-decompositions, dynamic programming
PROBLEM:
You are given a boolean expression B in conjunctive normal form with N variables and M clauses.
B was constructed from a K-tree with N vertices, where each vertex represents one of the variables. For each clause P_1 \lor P_2 \ldots \lor P_L in B is guaranteed that exists a clique in the graph with vertices |P_1|, \ldots, |P_L|.
You are given the inital value of each variable. The cost of changing the value of variable i is C_i. Find the minimum cost to make the expression evaluate to true.
QUICK EXPLANATION:
The graph has a perfect elimination order, construct a tree decomposition with width K and run a dynamic programming
EXPLANATION:
For solving 2-SAT is useful to transform the clauses to implicative form (u \lor v = \neg u \rightarrow v) and construct a graph connecting the respective variables. When each clause contains many variables, there are many useful graph representations:
- each variable is a vertex, and draw an edge from each pair of vertices that are in the same clause
- draw an edge from each clause to the variables it contains.
- draw an edge from each pair of clauses that contains the same variable.
We’ll use the first graph representation, let’s call it G, note that it creates a clique for each clause. The graph described in the problem is a K-tree, ― a subclass of chordal graphs. Our graph G is a subgraph of the k-tree.
A tree-decomposition of a graph is a tree where each node is a bag (set) that contains some of the vertices of the graph. Let’s denote the i-th set (bag) by S_i. The same vertex of the graph can be in many bags, as long as the following conditions are satisfied:
- Each vertex of the graph is in at least one bag
- For each vertex u, if we take all the bags that contains it, they form a connected component, this is called the coherence property.
- For each edge (u,v) in the graph, there is a bag containing u and v.
A graph can have many tree-decompositions, we are interested in finding the tree-decomposition that has the biggest bag (treewidth) as small as possible. That will allow us to do dynamic programming on the tree by trying all possibilities of assigning values to the variables of each bag.
There is no known algorithm that runs in polynomial time that constructs the tree-decomposition with minimum treewidth for an arbitrary graph. However our graph is special, it is chordal moreover it is the maximal graph with a given treewidth.
It is possible to construct a tree-decomposition starting from an elimination order.
Given a graph, we can play the following Elimination game:
- choose one of the vertices of the graph u. Let adj_u be the adjacent vertices of u in the graph.
- add one edge (if it does not exists in the graph) for each pair of distinct vertices of adj_u.
- remove u from the graph.
It turns out that the maximum size of adj_u in the second step of the elimination game is equivalent to the treewidth!
The order of choosing the vertices to minimize adj_u can be found by running an algorithm that finds the perfect elimination order in chordal graphs, however since our graph is special we can just remove the vertices in decreasing order of degree.
Note that step 2 may increase the degrees of some vertices, and step 3 decreases the degrees of some vertices.
The following algorithm finds the tree-decomposition starting from a elimination ordering v_1, \ldots, v_N.
- If N=1, return a tree with only one node {v_1}.
- Find the tree-decomposition T of v_2,...,v_N.
- Let u be the vertex adjacent to v_1 in the graph with minimum position in the elimination ordering. \min \{j: (v_1, v_j ) \in E \}
- create a new bag containing v_1 and all its adjacent vertices, and add an edge connecting v_1 and u in the tree.
(the proof is left to the reader)
Each bag in the tree-decomposition of G has degree at most K, that makes possible to perform a dynamic programming of the type $f_{u,b}=$minimum cost of assigning values to the variables of node u, given that the variables in bag_u \cap bag_{parent[u]} have already fixed values given by the set (bitmask) b. While bruteforcing all the possibilities of values for the variables in each bag, we have to make sure all the clauses are satisfied.
About CCNF
Is interesting when NP problems can be solved optimally in special cases. In my problem RB2CNF I described a condition that allows to solve optimally the max 2-SAT. For this problem I tried to solve the max-sat for clauses with more variables. Last year 300iq setted a problem also related with elimination orderings: EGGFREE.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
const int mxn=144;
const int mxk=9;
const int oo=1e9;
int normalize(int x){
int b=0;
if(x<0)x=-x,b=1;
return ((x-1)*2)^b;
}
int bat(int b,int i){
if(b&(1<<i))return 1;
return 0;
}
vector<vector<int>>tree;
vector<vector<int>>bag;
//f[u][b] = min cost of assigning values to the variables on subtree u
//given that the values of bag[u] n bag[parent[u]] are in bitmask b
int f[mxn+mxn+5][(1<<(mxk+1))+2];
int position(vector<int>&x,int v){
int at=lower_bound(x.begin(),x.end(),v)-x.begin();
if(at<int(x.size()) && x[at]==v)return at;
return -1;
}
vector<int>initial;
vector<int>cost;
vector<vector<int>>clauses;
vector<bool>vis;
int K;
void dfs(int u,int pu){
vis[u]=true;
for(int v:tree[u])if(v!=pu)dfs(v,u);
int szu=bag[u].size();
assert(szu<=K);
//bag[u] n bag[pu]
int mask=0;
for(int i=0;i<int(bag[u].size());i++){
int x=bag[u][i];
int idx=position(bag[pu],x);
if(idx!=-1)mask|=(1<<i);
}
for(int b=0;b<(1<<szu);b++)f[u][b]=oo;
//try all possible values for bag[u]
for(int b=0;b<(1<<szu);b++){
//check if clauses are satisfied
bool ok=true;
for(int it=0;it<int(clauses.size()) && ok;it++){
ok=false;
auto &clause=clauses[it];
if(clause.size()>bag[u].size()){
ok=true;
continue;
}
int found=0;
for(int i=0;i<int(bag[u].size());i++){
int x=bag[u][i];
int idx=position(clause,x);
int inc=0;
if(idx==-1){
idx=position(clause,x^1);
inc=1;
}
if(idx==-1)continue;
found++;
if(bat(b,i)^inc){
ok=true;
break;
}
}
if(found<int(clause.size()))ok=true;
}
if(!ok)continue;
int bpu=(b&mask);
//cost of setting values of bag[u]-bag[pu]
int better=0;
for(int i=0;i<szu;i++){
if(mask&(1<<i))continue;
int x=bag[u][i];
if(bat(b,i)!=initial[x]){
better+=cost[x];
}
}
//children cost
for(int v:tree[u]){
if(v==pu)continue;
//bag[v] n bag[u]
int c=0;
for(int i=0;i<int(bag[u].size());i++){
if(bat(b,i)==0)continue;
int x=bag[u][i];
int idx=position(bag[v],x);
if(idx!=-1){
c|=(1<<idx);
}
}
better+=f[v][c];
better=min(better,oo);
}
f[u][bpu]=min(f[u][bpu],better);
}
}
int main(){
int t=rint('\n');
assert(1<=t&&t<=10);
for(int tt=0;tt<t;tt++){
int n=rint(' ');
assert(1<=n&&n<=mxn);
int m=rint(' ');
assert(1<=m&&m<=mxn);
int k=rint('\n');
K=k;
assert(1<=k&&k<=mxk);
string s=rword('\n');
assert(int(s.size())==n);
for(int i=0;i<n;i++)assert('0'<=s[i]&&s[i]<='1');
initial.resize(n+n,0);
for(int i=0;i<n;i++){
initial[i+i]=s[i]-'0';
initial[i+i+1]=1-initial[i+i];
}
cost.resize(n+n);
for(int i=0;i<n;i++){
cost[i+i]=rint(i==n-1?'\n':' ');
cost[i+i+1]=cost[i+i];
assert(1<=cost[i+i]&&cost[i+i]<=256);
}
vector<set<int> >g(n+n);
clauses.clear();
for(int i=0;i<m;i++){
int l=rint(' ');
assert(2<=l && l<=n);
vector<int>clause;
for(int j=0;j<l;j++){
int x=rint(j==l-1?'\n':' ');
assert(-n<=x && x<=n && x!=0);
x=normalize(x);
clause.push_back(x);
}
sort(clause.begin(),clause.end());
for(int j=1;j<l;j++)assert(clause[j]!=clause[j-1]);
clauses.push_back(clause);
//g=(V,E), E={(u,v) : there is a clause containing u and v}
for(int x=0;x<l;x++){
for(int y=x+1;y<l;y++){
int u=clause[x];
int v=clause[y];
//making variables positive
u=min(u,u^1);
v=min(v,v^1);
assert(0<=u&&u<n+n);
assert(0<=v&&v<n+n);
g[u].insert(v);
g[v].insert(u);
}
}
}
//perfect elimination order
vector<int>p;
vector<bool>rem(n+n,false);
vector<vector<set<int> > > graphs;
for(int it=0;it<n;it++){
graphs.push_back(g);
int u=-1;
for(int i=0;i<n+n;i+=2)
if(!rem[i] && (u==-1 || g[i].size()<g[u].size()))
u=i;
rem[u]=true;
p.push_back(u);
vector<int>adj;
for(int v:g[u])if(!rem[v])adj.push_back(v);
for(int x:adj)g[x].erase(u);
int sz=adj.size();
for(int i=0;i<sz;i++){
int x=adj[i];
for(int j=i+1;j<sz;j++){
int y=adj[j];
g[x].insert(y);
g[y].insert(x);
}
}
}
//tree-decomposition
bag.clear();
bag.resize(n+n+1);
tree.clear();
tree.resize(n+n);
for(int i=n-1;i>=0;i--){
int u=p[i];
bag[u]={u};
rem[u]=false;
for(int v:graphs[i][u])if(!rem[v])bag[u].push_back(v);
sort(bag[u].begin(),bag[u].end());
//find leftmost neighbour in the elimination order
int who=-1;
for(int j=i+1;j<int(p.size());j++){
int v=p[j];
if(graphs[i][u].count(v)){
who=v;
break;
}
}
assert(int(bag[u].size())<=K);
if(who==-1)continue;
tree[u].push_back(who);
tree[who].push_back(u);
}
vis.resize(n+n);
fill(vis.begin(),vis.end(),false);
int ans=0;
for(int i=0;i<n+n;i+=2)if(!vis[i]){
dfs(i,n+n);
ans+=f[i][0];
ans=min(ans,oo);
}
if(ans>=oo)ans=-1;
printf("%d\n",ans);
}
assert(getchar()==EOF);
return 0;
}