Swift's blog

By Swift, history, 4 months ago, In English,

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

Read more »

Tags bug
 
 
 
 
  • Vote: I like it  
  • +49
  • Vote: I do not like it  

By Swift, 16 months ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it  
  • +48
  • Vote: I do not like it  

By Swift, 3 years ago, In English,

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:
    addEdge(not x[i], y[i])
    addEdge(not y[i], x[i])
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

Read more »

 
 
 
 
  • Vote: I like it  
  • +144
  • Vote: I do not like it  

By Swift, history, 3 years ago, In English,

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

Read more »

Discussion of Delete2
 
 
 
 
  • Vote: I like it  
  • +971
  • Vote: I do not like it