Red-Black Boolean Expression SOLUTION RB2CNF

Red-Black Boolean Expression November Challenge 2020

 

Let S be a set of N boolean variables X1,X2,…,XN and their negations ¬X1,¬X2,…,¬XN. You are given the initial values of all variables.

A 2-CNF boolean expression is defined as a conjunction of clauses, where each clause is a disjunction of two elements of the set S. Ada constructed a 2-CNF boolean expression B with M clauses as follows:

 

First, Ada painted each of the variables X1,X2,…,XN with one colour ― either red or black.

Then, she painted the negated variables ― for each valid i, if Xi is painted red, then ¬Xi is painted black, and vice versa (if Xi is black, ¬Xi is painted red).

Finally, she wrote the boolean expression B=(P1∨Q1)∧(P2∨Q2)∧…∧(PM∨QM), in such a way that no clause contains two variables with the same colour and Pi≠¬Qi for each clause.

Ada wants the expression to evaluate to “true”. In order to achieve that, she may change the values of variables; for each valid i, changing the value of Xi (from “true” to “false” or vice versa) is Ci. Find the minimum total cost needed to make the expression B evaluate to “true” or determine that it is impossible.

 

Note that you are not given the colours of variables, but it is guaranteed that the expression B is chosen in such a way that there is at least one valid way to assign colours and the minimum cost is the same for each valid assignment of colours.

 

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains two space-separated integers N and M.

The second line contains a binary string S with length N describing the initial values of the variables. For each valid i, the i-th character of S is ‘1’ if Xi is true or ‘0’ if Xi is false.

The third line contains N space-separated integers C1,C2,…,CN.

M lines follow. For each valid i, the i-th of these lines contains two space-separated integers Pi and Qi. For each valid i, the variable Xi is represented by the integer i and its negation is represented by −i.

Output

For each test case, print a single line containing one integer ― the minimum cost needed to make the boolean expression evaluate to “true”, or −1 if it is impossible.

 

Constraints

1≤T≤105

1≤N≤256

1≤Ci≤256 for each valid i

1≤|Pi|,|Qi|≤N for each valid i

each character of S is either ‘0’ or ‘1’

the sum of M over all test cases does not exceed 43,210

Subtasks

Subtask #1 (1 points): N≤10

Subtask #2 (99 points): original constraints

 

Example Input

1

3 3

101

1 2 3

-1 -2

-1 -3

2 1

Example Output

3

Explanation

Example case 1: The expression B is (¬X1∨¬X2)∧(¬X1∨¬X3)∧(X2∨X1). Ada generated this expression by painting X2 and X3 in red and X1 in black.

One optimal way to make the expression true is changing the value of X3.

 

CLICK HERE

SOLUTION:
t = int(input())
for _ in range(t):
   n, m = [int(j) for j in input().split()]
   string = [0 for _ in range(n)]
   s = input()
   for i in range(n):
      string[i] = 2 * int(s[i]) – 1
   costs = [int(j) for j in input().split()]
   edges = [0 for _ in range(m)]
   for i in range(m):
      edges[i] = [int(j) for j in input().split()]
   
   critical_edges = []
   first_list = [[] for _ in range(n)]
   second_list = [[] for _ in range(n)]
   third_list = [[] for _ in range(n)]
   forth_list = [[] for _ in range(n)]
   for i in range(m):
      if (edges[i][0] * string[abs(edges[i][0])-1] < 0) and (edges[i][1] * string[abs(edges[i][1])-1] < 0):
         first_list[abs(edges[i][0])-1].append(abs(edges[i][1])-1)
         first_list[abs(edges[i][1])-1].append(abs(edges[i][0])-1)
         critical_edges.append([abs(edges[i][0])-1,abs(edges[i][1])-1])
      elif edges[i][0] * string[abs(edges[i][0])-1] < 0:
         second_list[abs(edges[i][0])-1].append(abs(edges[i][1])-1)
         third_list[abs(edges[i][1])-1].append(abs(edges[i][0])-1)
      elif edges[i][1] * string[abs(edges[i][1])-1] < 0:
         second_list[abs(edges[i][1])-1].append(abs(edges[i][0])-1)
         third_list[abs(edges[i][0])-1].append(abs(edges[i][1])-1)
      else:
         forth_list[abs(edges[i][0])-1].append(abs(edges[i][1])-1)
         forth_list[abs(edges[i][1])-1].append(abs(edges[i][0])-1)
   
   all_min_cost = 0
   no_edge = (len(critical_edges) == 0)
   while len(critical_edges) != 0:
      root = critical_edges[0][0]
      chosen = [False for _ in range(n)]
      chosen[root] = True
      chosen_vertices = [root]
      while len(chosen_vertices) != 0:
         vertex = chosen_vertices.pop()
         for v in first_list[vertex]:
            if not chosen[v]:
               chosen[v] = True
               chosen_vertices.append(v)
         for v in second_list[vertex]:
            if not chosen[v]:
               chosen[v] = True
               chosen_vertices.append(v)
         for v in third_list[vertex]:
            if not chosen[v]:
               chosen[v] = True
               chosen_vertices.append(v)
         for v in forth_list[vertex]:
            if not chosen[v]:
               chosen[v] = True
               chosen_vertices.append(v)
      main_edges = []
      for i in range(len(critical_edges)-1,-1,-1):
         if chosen[critical_edges[i][0]]:
            main_edges.append(critical_edges.pop(i))
   
      min_cost = 1000000
      last_replaced = []
      cost_on_replace = []
      coloring_on_replace = []
      
      new_colored = []
      current_cost = 0
      coloring = [0 for _ in range(n)]
      
      i = 0
      replaced = False
      should_break = False
      important_edges = len(main_edges)
      while i < important_edges:
         if coloring[main_edges[i][0]] == 0 and coloring[main_edges[i][1]] == 0:
            if replaced:
               coloring[main_edges[i][1]] = 1
               current_cost += costs[main_edges[i][1]]
               new_colored = [main_edges[i][1]]
               replaced = False
            else:
               last_replaced.append(i)
               cost_on_replace.append(current_cost)
               coloring_on_replace.append(list(coloring))
               coloring[main_edges[i][0]] = 1
               current_cost += costs[main_edges[i][0]]
               new_colored = [main_edges[i][0]]
            while len(new_colored) != 0:
               colored_index = new_colored.pop()
               if coloring[colored_index] == -1:
                  for v in first_list[colored_index]:
                     if coloring[v] == 0:
                        coloring[v] = 1
                        current_cost += costs[v]
                        if current_cost >= min_cost:
                           should_break = True
                           break
                        new_colored.append(v)
                     elif coloring[v] == -1:
                        should_break = True
                        break
                  if should_break:
                     break
                  for v in second_list[colored_index]:
                     if coloring[v] == 0:
                        coloring[v] = -1
                        new_colored.append(v)
                     elif coloring[v] == 1:
                        should_break = True
                        break
                  if should_break:
                     break
               else:
                  for v in third_list[colored_index]:
                     if coloring[v] == 0:
                        coloring[v] = 1
                        current_cost += costs[v]
                        if current_cost >= min_cost:
                           should_break = True
                           break
                        new_colored.append(v)
                     elif coloring[v] == -1:
                        should_break = True
                        break
                  if should_break:
                     break
                  for v in forth_list[colored_index]:
                     if coloring[v] == 0:
                        coloring[v] = -1
                        new_colored.append(v)
                     elif coloring[v] == 1:
                        should_break = True
                        break
                  if should_break:
                     break
         if should_break:
            if len(last_replaced) != 0:
               i = last_replaced.pop()
               current_cost = cost_on_replace.pop()
               coloring = list(coloring_on_replace.pop())
               should_break = False
               replaced = True
            else:
               break
         elif i == important_edges – 1:
            min_cost = min(min_cost,current_cost)
            if len(last_replaced) != 0:
               i = last_replaced.pop()
               current_cost = cost_on_replace.pop()
               coloring = list(coloring_on_replace.pop())
               replaced = True
            else:
               break
         else:
            i += 1
      all_min_cost += min_cost
   if no_edge:
      print(0)
   else:
      print(all_min_cost)
 

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

Leave a Comment

close
error: Content is protected !!
Free Udemy Courses and Hacking Resources Join Us on TelegramClick Here
+