Independent set <=> clique

An independent set S of G corresponds to a clique containing the same set of vertices S in G’s complement graph (flipping edges in E and not in E). This is because all vertex pair (i, j) in S is not an edge in G is equivalent to all vertex pair (i, j) in S is an edge in G’s complement graph.

Vertex cover <=> independent set

A vertex cover S in graph G corresponds to an independent set $V \setminus S$ in G. If S is a valid vertex cover, any vertex pair (i, j) in $V \setminus S$ is not an edge in G, so $V \setminus S$ is independent set. If $V \setminus S$ is an independent set, for any edge at least one endpoint is in S, so S is a vertex cover. Then MIN-VERTEX-COVER = MAX-INDEPENDENT-SET.

Vertex cover <=> matching (in bipartite graph)

In bipartite graph, the size of any matching is less or equal than the size of any vertex cover, and MAX-MATCHING = MIN-VERTEX-COVER.

(a) Any matching <= any vertex cover

Given a matching in a bipartite graph, we need to select at least one vertex from every matched edge. Otherwise, there exist matched edge that isn’t covered. So matching <= vertex cover.

(b) MAX-MATCHING = MIN-VERTEX-COVER

From a maximum matching M, we can construct a vertex cover by (1) direct all matched edge from Y to X and all unmatched edge from X to Y, (2) run a DFS from all unmatched vertices in X, and (3) construct set R by all unvisited vertices in X and all visited vertices in Y.

The only type of edge that has both endpoints not in R consists of a visited vertex u in X and a unvisited vertex v in Y. If {u, v} is a unmatched edge, then v should be reachable by appending (u, v) to the path to u. If {u, v} is a matched edge, then the only incoming edge towards u is (v, u). Then u cannot be reachable if v is unreachable. Both cases lead to contradiction. So all edge contains some endpoint in R and R is a valid vertex cover.

Unvisited vertices in X corresponds to a matched edge (otherwise they will be initially visited by DFS). Visited vertices in Y corresponds to a matched edge (otherwise we have an augmenting path between two unmatched vertices, but M is a maximum matching). Because unvisited vertices in X are not reachable, these edges can not intersect. So |R| <= |M|. Then there exist some vertex cover whose size is at most |M|, so MIN-VERTEX-COVER <= |M|, and MIN-VERTEX-COVER = MAX-MATCHING.

Append Sort

Problem

Given n-length array, $n \leq 100$, each number is in $1 \leq X_i \leq 10^9$, make this array strictly-increasing by appending digit to any number. Return minimum number of digit needed.

Solution

Greedy, if $X_i \geq X_{i + 1}$, try to make $len(X_{i + 1})$ equal to $len(X_i)$ or $len(X_i)+1$ by comparing their prefix.

Prime Time

Problem

Given a set of at most $10^{15}$ primes, each prime within $2 \leq p_i \leq 500$, return maximum value of $\sum_{p_i \not\in S} p_i = \prod_{p_i \in S} p_i$ if there exist valid solution.

Solution

Test set 1-2 (at most 100 total primes): Since $W = \sum_{p_i \not\in S} p_i \leq \sum p_i \leq 50000$, the product of primes is inside 50000, so we can search for set S such that $\sum_{p_i \in S} p_i + \prod_{p_i \in S} p_i = W$. This can be done in a DP-like way.

Test set 3: W is very large. $\prod_{p_i \in S} p_i \leq \sum p_i \leq 5 \times 10^{17}$, each prime is at least 2, so $|S| \leq 60$, so $\sum_{p_i \in S} p_i \leq 60 \times 500=30000$. Then the valid solution is in $[W - 30000, W]$ because $ans = \prod_{p_i \in S} p_i = W - \sum_{p_i \in S} p_i$.

And the solution value is products of primes in $[2, 500]$. So try and factorize every number in this region and see if it can be expressed by product of available primes and has valid sum.

Hacked Exam

Problem

There are Q true/false problems, given n people’s solution sequence and number of correct answer, all consistent answer sequence have same probability, return a sequence with maximum expected number of correct answer.

Solution

Test set 1-2 ($n \leq 2, Q \leq 40$): We can use DP to compute number of consistent sequence, and for each bit, compute the number of consistent sequence specifying this bit is true/false. Then we have the expected value of each bit being true/false, and sum because of the linearity of expectation.

Test set 3 ($n \leq 3, Q \leq 120$): There are limited types of questions: when n = 3, there are 8 types of questions: FFF, FFT, …, TTT. Symmetrically (by flipping the result in the end to make FFT type -> TTF type), there are only 4 types of questions. We can brute-force number of consistent sequences by counting number of T out of all available T/F (or number of questions in such type) in each of four type, times some combinatorics number, this takes $O((Q/4)^4)$. Then do in a similar way as previous case and count number of consistent sequences after specifying T/F for each bit.

NAT penetration is useful in many cases. For example, if your ISP uses Carrier Grade NAT (CGNAT) and does not have a public IP address, you will need it to expose local service to be accessible from the public Internet. FRP is one powerful and simple to use NAT penetration tool. FRP documentation has more information on using FRP.

To use frp, first download frp server and client (frps and frpc) binaries, and create a regular user for frps/frpc with useradd on the server and client for security reason.

Server configuration

FRP server binds a main port for the tunnel traffic, as well as allows clients to map other server ports back to client services. Then, client services can be accessed using server ip and the reqested port.

Server can specify a simple token or password to authenicate client. FRP also supports using OpenID for authenication.

The server also needs to open the TCP or UDP (if KCP is used) port in the firewall to allow incoming traffic.

1
2
3
4
5
6

[common]
bind_port = <main port>
kcp_bind_port = <main port>
allow_ports = <allowed mapping port region>
authentication_method = token
token = <token>

Also, you can create a systemd service to control the frps process. Client can configure systemd service in a similar way.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

[Unit]
Description=<your description>
After=network.target

[Service]
Type=simple
User=frps
Group=frps
Restart=on-failure
RestartSec=5s
ExecStart=/usr/bin/frps -c /etc/frp/frps.ini

[Install]
WantedBy=multi-user.target

Client configuration

Client connects to server port and requests to map local service to one server port. You can optionally use KCP instead of usual TCP as transport protocol for tunnel traffic, because KCP is a UDP-based protocol and it can reduce service latency.

One client configuration file can contain multiple services and request one server port for each service. Also optionally enable or disable compression and encryption for each service.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

[common]
server_addr = <server address>
server_port = <main port>
# protocol = kcp
authentication_method = token
token = <token>

[<service name>]
type = tcp/udp
local_ip = localhost
local_port = <local service port>
remote_port = <requested server port>
# use_encryption = true
# use_compression = true

Finally, enable and start both frps and frpc with systemd, and your local service should be accessible from the Internet!

V2ray is a network proxy tool. One possible configuration is to use WebSocket transport along with TLS, so network traffic looks like good normal HTTPS/WSS traffic in public network, very nice and effective against China’s firewall. This can be used along with web servers such as Apache or Nginx for reverse proxy. The entire network route looks like

1

browser <=> v2ray client <=> webserver <=> v2ray server

First, download v2ray binaries for both client and server.

V2ray Client Configuration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

{
  "inbound": {
    "port": <local socks port>,
    "listen": "127.0.0.1",
    "protocol": "socks"
  },
  "outbound": {
    "protocol": "vmess",
    "settings": {
      "vnext": [
        {
          "address": "<server address>",
          "port": 443,
          "users": [
            {
              "id": "<uuid>"
            }
          ]
        }
      ]
    },
    "streamSettings": {
      "network": "ws",
      "security": "tls",
      "wsSettings": {
        "path": "/<path>/"
      }
    },
  "mux": {"enabled": false}
  }
}

Sometimes MUX will cause entire connection to hang if one of them is broken, so I turn off this function.

V2ray Server Configuration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

{
  "log": {
      "access": "<access log file path>",
      "error": "<error log file path>",
      "loglevel": "warning"
  },
  "inbound": {
    "port": <port number>,
    "listen":"127.0.0.1",
    "protocol": "vmess",
    "settings": {
      "clients": [
        {
          "id": "<uuid>"
        }
      ]
    },
    "streamSettings":{
      "network":"ws",
      "wsSettings": {
         "path": "/<path>/"
     }
    }
  },
  "outbound": {
    "protocol": "freedom",
    "settings": {}
  }
}

Apache Configuration

Webserver needs to have valid TLS certificate, such as getting one from Let’s Encrypt by certbot, to encrypt traffic in public network. The webserver decrypts TLS traffic and “proxypass” the WebSocket content to backend localhost:port number v2ray server.

1
2
3
4
5
6
7

<LocationMatch "<path>">
  ProxyPass ws://127.0.0.1:<port number>/<path>/
  ProxyAddHeaders Off
  ProxyPreserveHost On
  RequestHeader set Host %{HTTP_HOST}s
  RequestHeader set X-Forwarded-For %{REMOTE_ADDR}s
</LocationMatch>

Security

To improve security, run v2ray as regular user instead of root, so that possible security vulnerbility in v2ray does not compromise the entire system. Create a Linux user using useradd and configure systemd service to run v2ray with that user and group. Set the port number to be large enough that does not require superuser permission.

Further Steps

V2ray has new features such as QUIC and HTTP/2 transport. Maybe I will try them later.

Install Nodejs

Install hexo

1

$ npm install -g hexo-cli

Create blog folder

1
2

$ hexo init blog
$ npm install

Install deployer and next theme

1
2

$ npm install hexo-deployer-git 
$ npm install hexo-theme-next

Copy and customize theme file

1

$ cp node-modules/hexo-theme-next/_config.yml _config.next.yml

Create new post

1
2

$ hexo n "post-title"
$ hexo n page "page-title"

Generate

1

$ hexo g

Local testing server

1

$ hexo s	# or hexo s -g for generate

Deploy

1

$ hexo d	# or hexo d -g for generate

Hello World!!!

This is my first post!