### Swift's blog

By Swift, history, 10 months ago, ,

I actually got accepted on most of these problems, but they're shown as "red", why is that?

•
• +49
•

By Swift, 21 month(s) ago, ,

There are infinite number of people, each one has a whether red or blue hat. Everyone can see everyone's hat but can't see their own. Is it possible that with a strategy, only a finite number of people guess their hat color wrong?

•
• +48
•

By Swift, 4 years ago, ,

Hi codeforces community.

I thought there is no good 2-SAT tutorial in the internet, so I decided to write one.

2-SAT is a special case of boolean satisfiability.

Good question! Boolean satisfiability or just SAT determines whether we can give values (TRUE or FALSE only) to each boolean variable in such a way that the value of the formula become TRUE or not. If we can do so, we call formula satisfiable, otherwise we call it unsatisfiable. Look at the example below:

f = A ∧ ¬B, is satisfiable, cause A = TRUE and B = FALSE makes it TRUE.

but g = A ∧ ¬A, is unsatisfiable, look at this table:

 A ¬A A ∧ ¬A TRUE FALSE FALSE FALSE TRUE FALSE

As you can see g is unsatisfiable cause whatever values of its boolean variables are, g is FALSE.

Note: ¬ in ¬X is boolean not operation. in X ∧ Y is boolean and operation and finally in X ∨ Y is boolean or operation.

SAT is a NP-Complete problem, though we can solve 1-SAT and 2-SAT problems in a polynomial time.

#### 1-SAT

Note: This doesn't really exist, I define it cause it help understanding 2-SAT.

Consider f = x1 ∧ x2 ∧ ...  ∧ xn.

Problem: Is f satisfiable?

Solution: Well 1-SAT is an easy problem, if there aren't both of xi and ¬xi in f, then f is satisfiable, otherwise it's not.

#### 2-SAT

Consider f = (x1 ∨ y1) ∧ (x2 ∨ y2) ∧ ...  ∧ (xn ∨ yn).

Problem: Is f satisfiable?

But how to solve this problem? xi ∨ yi and and are all equivalent. So we convert each of (xi ∨ yi) s into those two statements.

Now consider a graph with 2n vertices; For each of (xi ∨ yi) s we add two directed edges

1. From ¬xi to yi

2. From ¬yi to xi

f is not satisfiable if both ¬xi and xi are in the same SCC (Strongly Connected Component) (Why?) Checking this can be done with a simple Kosaraju's Algorithm.

Assume that f is satisfiable. Now we want to give values to each variable in order to satisfy f. It can be done with a topological sort of vertices of the graph we made. If ¬xi is after xi in topological sort, xi should be FALSE. It should be TRUE otherwise.

Some problems:

#### Pseudo Code

func dfsFirst(vertex v):
marked[v] = true
for each vertex u adjacent to v do:
if not marked[u]:
dfsFirst(u)
stack.push(v)

func dfsSecond(vertex v):
marked[v] = true
for each vertex u adjacent to v do:
if not marked[u]:
dfsSecond(u)
component[v] = counter

for i = 1 to n do:
for i = 1 to n do:
if not marked[x[i]]:
dfsFirst(x[i])
if not marked[y[i]]:
dfsFirst(y[i])
if not marked[not x[i]]:
dfsFirst(not x[i])
if not marked[not y[i]]:
dfsFirst(not y[i])

set all marked values false
counter = 0
flip directions of edges // change v -> u to u -> v

while stack is not empty do:
v = stack.pop
if not marked[v]
counter = counter + 1
dfsSecond(v)

for i = 1 to n do:
if component[x[i]] == component[not x[i]]:
it is unsatisfiable
exit
if component[y[i]] == component[not y[i]]:
it is unsatisfiable
exit

it is satisfiable
exit


•
• +144
•

By Swift, history, 4 years ago, ,

#### **EDIT: A shorter error function **

WARNING: Many of these things belong to C++11 so use C++11 in order to test anything here :)

I just write a short version for this article, because it's now in the main page. I recommend you to click on "Read more »" and read more :) Here is a short trick for the short version:

I see lots of programmers write code like this one:

pair<int, int> p;
vector<int> v;
// ...
p = make_pair(3, 4);
v.push_back(4); v.push_back(5);


while you can just do this:

pair<int, int> p;
vector<int> v;
// ...
p = {3, 4};
v = {4, 5};