Background: This is a challenge in our Algorithm Analysis class. The problem is created by kczno1. Here is a pdf version of my slides when I did the sharing in class (in Chinese).
Problem
This is an encoding/decoding problem. You are required to write two program, an encoder and a decoder.
- Your encoder should encode a bit string into an undirected graph with \(N=100\) unlabeled vertices. The length of the bit string \(\ell\) should maximized.
- The judging system would randomize the order among all the edges and vertices of the output of your encoder.
- Your decoder should input the shuffled graph and decode the bit string.
Your algorithm must be deterministic and 100% correct on all possible bit string input. Your program has a time limit of 1s and a memory limit of 2GB.
Basic idea
Denote the encoding and decoding function as \(g=e(s)\) and \(s=d(g)\), where \(s\in S=\{0,1\}^n\) and \(g\in e(S)\). Assuming the two functions are deterministic and 100% accurate, \(d(-)\) can be used to perform graph isomorphism test: \(g_1\cong g_2\iff d(g_1)=d(g_2)\), hense \(d\) can be used to solve graph isomorphism on the set of graphs \(e(S)\), which acts as a limitation of our algorithm.
A note from my friend ztr: “An algorithm solving graph isomorphism for 90% of the input” may actually exist.
Obviously, \(|e(S)|\) will not be more than the number of unlabeled graphs with \(N\) vertices, denoted as \(a(N)\). On OEIS, A000088 provided an approximation formula \(a(N)\approx \frac{2^{N\choose 2}}{N!}\), giving an upper bound to our length \(\ell\): \[ \ell\le \lfloor\log_2 a(N)\rfloor =4425. \]
A basic algorithm
Firstly, any labeled graph with \(v\) vertices naturally encodes \(v\choose 2\) bits of information. A natural idea would be taking a labeled graph \((V_a,E_a)\), add some other vertices and edges to it, and use the extra structure to recover the labels within \(V_a\).
We try to label the vertices in \(V_a\) as binary numbers. Let \(a=|V_a|\), and we create \(b=\lceil \log_2 a\rceil\) new vertices, and set \(V_b=\{\mathfrak b_0,\cdots,\mathfrak b_{b-1}\}\). Then, for any vertex in \(V_a\) with label \(i\), it has an edge to \(\mathfrak b_j\) if and only of the \(j\)-th bit in the binary representation of \(i\) is \(1\).
Now we just need to label the vertices \(V_b\). Let’s denote the subgraph formed by all \(V_b\leftrightarrow V_b\) edges by \(G_b\). As long as this small graph has no nontrivial automorphism (such graphs are called asymmetric), we can tell vertices in \(V_b\) apart. For example, when \(b=7\), we can take this graph as our \(G_b\):
Then we just need to determine which vertices are in \(V_a\), and which are in \(V_b\). We add another vertex \(u\), and connect it to every vertex in \(V_b\). Now, as long as we can identify \(u\), we can identify all of \(V_b\), then we can use \(G_b\) to label \(V_b\), which can then be used to give binary labels to \(V_a\).
In order to find vertex \(u\), we add yet another vertex \(w\), and connect it to every vertex in \(V_a\cup V_b\). With this setup, we can identify \(u\) as long as we identify \(w\), because \(u\) is its only non-neighbor. However, finding \(w\) is easy; it’s simply the vertex with the largest degree. This completes the encoding construction.
This is exactly the problem 航空路線図 from JOI 2018 SC. The above construction (and its code) can be found on the link above. With the algorithm described above, we can find \(a=91,b=7\), thus \({91\choose 2}=4095\) bits of information can be encoded.
This is already the first in the class. But our question is,
.png)
Optimization #1
The above algorithm embeds a labeled graph with \(a\) vertices into an unlabeled graph with \(a+\log a+2\) vertices. The number \(+2\) here looks ugly, and we want to optimize it out. Can we change it to \(+1\)? Turns out, you can.
We can find that the first step in our decoding algorithm has to use some global information, e.g. the degree sequence. As the sole purpose of the vertices \(u, w\) is to telling \(V_a\) from \(V_b\), which is a 2-way classification, we naturally thinks about the parity of the degree sequence.
After all the edges within \(V_a\cup V_b\) are added, the degrees (and especially the parity of the degrees) of these vertices are arbitrary. By adding another vertex \(w\) and connecting some edge from it, we can make the degree of each \(V_a\) vertex, and make the degree of each \(V_b\) vertex odd. Note that \(a=92,b=7\), so the degree of \(w\) would be odd.
When decoding, we try to find all the vertices with odd degrees, which is \(V_b\cup \{w\}\). We can precisely know all the incident edges of each \(\mathfrak b_i\in V_b\), so their degrees are determined. With the degree constraint of \(w\), we can find out that the subgraph induced by \(V_b\cup \{w\}\) looks like this:
This graph has no nontrivial isomorphism, so we can label it easily.
With this setup, we can embed a labeled graph with \(a=92\) vertices into an unlabeled graph with \(a+\log a+1=100\) vertices, which means we can encode \({92\choose 2}=4186\) bits of information. This is indeed an optimization, but our question is,
Optimization #2
When we are binary encoding \(V_a\leftrightarrow V_b\), we treat each of \(0, 1, \cdots, 91\) as \(7\)-digit binary numbers; however, as \(92<128\), we have wasted some information. If we choose any \(92\) numbers in \(0, 1, \cdots, 127\), denoted as \(a_0<a_1<\cdots<a_{91}\), and
- Instead of: for any vertex in \(V_a\) with label \(i\), it has an edge to \(\mathfrak b_j\) if and only of the \(j\)-th bit in the binary representation of \(i\) is \(1\)
- We do this: for any vertex in \(V_a\) with label \(i\), it has an edge to \(\mathfrak b_j\) if and only of the \(j\)-th bit in the binary representation of \(a_i\) is \(1\)
\(\{a_0,\cdots,a_{91}\}\) can be any subset of \(\{0, \cdots, 127\}\) with \(92\) elements, and we can encode \(\log_2 \binom{128}{92}\approx 106\) bits of information into the choice of this set. This is a simple DP.
Click to show the code
// U2048 is a 2048-bit big integer class. Its operator[] obtains a certain binary digit.
// C is a U2048[][] representing binomial numbers.
U2048 ord2set(U2048 x, int n, int k) {
U2048 ans = 0;
while (n > 0) {
u32 bit = 0;
if (k == 0 || C[n - 1][k - 1] <= x) {
if(k > 0) {
x -= C[n - 1][k - 1];
}
bit = 0;
} else {
bit = 1;
--k;
}
ans[--n] = bit;
}
return ans;
}
U2048 set2ord(U2048 x, int n, int k) {
U2048 ans = 0;
while (n > 0) {
u32 bit = x[n - 1];
if (bit) {
--k;
} else {
if (k > 0) {
ans += C[n - 1][k - 1];
}
}
--n;
}
return ans;
}This introduces a problem. During decoding, we need to identify the small graph with \(8\) vertices, and the graph above requires a predetermined degree sequence of \(V_b\). Changing the binary labels of \(V_a\) would change the edges on \(V_a \leftrightarrow V_b\), which changes the parity of the degree of every vertex in \(V_b\), which then changes the edges between \(w\leftrightarrow V_b\).
The solution is to construct multiple candidate \(G_b\) and choose different ones accoding to the sequence \(a_i\). It will be described in detail later.
With this technique, we can encode an extra \(\log_2 \binom{128}{92}\approx 106\) bits of information, making the total encode length \(\left\lfloor \binom{N-b-1}{2}+\log_2 \binom{2^b}{N-b-1}\right\rfloor=4292\) bits. It’s pretty close to our upper bound \(4425\), but our question remains,
Optimization #3
Sure do. We plugged in \(b=7\) into the formula \[ \ell=\left\lfloor \binom{N-b-1}{2}+\log_2 \binom{2^b}{N-b-1}\right\rfloor, \] which is a huge oversight. We kept thinking \(b=\lceil \log_2 N\rceil\) is optimial. However, I throwed several different values into Mathematica and got this result:
Indeed, \(b=7\) does not maximize \(\ell\). We can find that \(\ell\) is maximized when \(b=11\). The only modification in the algorithm is the construction of \(G_b\).
When the edges between \(w\leftrightarrow V_b\) is no less then \(6\), we use the following graph:
with such construction, \(w\) will have the highest degree in the
subgraph induced by \(\{w\}\cup
V_b\).When the edges between \(w\leftrightarrow V_b\) is no more than \(5\), use the complement graph of it, and \(w\) will have the lowest degree in the subgraph induced by \(\{w\}\cup V_b\).
Now we can encode \(\ell=4347\). Now, let me ask,
More optimizations?
- inverse the output graph, \(1\) bit
- we can find multiple \(G_b\) choices, and it’s easy to find \(16\) such small graphs, which gives us an extra \(4\) bit
- ……
Some other minor optimizations exist, but I’m too lazy to write it here.
Analysis
Our lower bound is \(4347\), and the current theoretical upper bound is \(4425\). The gap is not very significant. Consider the ratio \(\frac{\ell}{\ell_\mathrm{OPT}}\), (without the three optimizations above) the ratio is \(1-\Theta\left(\frac{\log N}{N}\right)\), which approaches \(1\) when \(N\to\infty\).
Code
The code is not cleaned up and contains a lot of conjecture verification and small graph brute-force searching code.
Click here to see the whole code
#include "bits/stdc++.h"
using namespace std;
constexpr int graph_size = 100;
using EdgeListGraph = vector<pair<int, int>>;
using SparseGraph = vector<vector<int>>;
std::random_device rd;
std::mt19937 mt{114514};
struct EncoderParameter
{
int labeled_n;
int unlabeled_n;
int lg2;
int tab_len;
};
struct EncoderResult
{
EncoderParameter param;
EdgeListGraph g;
};
SparseGraph graph_cast(int n, const EdgeListGraph &ge) {
SparseGraph g(n);
for (auto x : ge) {
g[x.first].push_back(x.second);
g[x.second].push_back(x.first);
}
return g;
}
EdgeListGraph graph_cleanup(EdgeListGraph g) {
for (auto &x : g) {
if (x.first > x.second) swap(x.first, x.second);
}
sort(g.begin(), g.end());
auto it = unique(g.begin(), g.end());
g.resize(it - g.begin());
return g;
}
EdgeListGraph graph_cast(const SparseGraph &gd) {
EdgeListGraph ge;
for (int x = 0; x < gd.size(); ++x) {
for (auto y : gd[x]) {
if (x < y)
ge.push_back({x, y});
}
}
return ge;
}
vector<int> deg_sequence(int n, const EdgeListGraph &g) {
vector<int> ans(n, 0);
for (auto x : g) {
ans[x.first] += 1;
ans[x.second] += 1;
}
return ans;
}
EdgeListGraph complete_graph(int n) {
EdgeListGraph ans;
ans.reserve(n * (n - 1) / 2);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
ans.push_back({i, j});
}
}
return ans;
}
EdgeListGraph flip_graph(int n, EdgeListGraph g) {
g = graph_cleanup(g);
EdgeListGraph go;
EdgeListGraph Kn = complete_graph(n);
set_difference(Kn.begin(), Kn.end(), g.begin(), g.end(), back_inserter(go));
return go;
}
EdgeListGraph filter_node_dec(const EdgeListGraph &g, int x) {
EdgeListGraph ans;
for (auto e : g) {
if (e.first == x || e.second == x) continue;
if (e.first > x) --e.first;
if (e.second > x) --e.second;
ans.push_back(e);
}
return ans;
}
EdgeListGraph filter_node(const EdgeListGraph &g, int x) {
EdgeListGraph ans;
for (auto e : g) {
if (e.first == x || e.second == x) continue;
ans.push_back(e);
}
return ans;
}
EdgeListGraph permute_graph(EdgeListGraph g, vector<int> perm) {
for (auto &x : g) {
x.first = perm[x.first];
x.second = perm[x.second];
}
return g;
}
pair<EdgeListGraph, vector<int>> shuffle_graph(int n, EdgeListGraph g) {
vector<int> perm(n, 0);
for (int i = 0; i < n; ++i) {
perm[i] = i;
}
shuffle(perm.begin(), perm.end(), mt);
for (auto &x : g) {
x = {perm[x.first], perm[x.second]};
}
return make_pair(g, perm);
}
vector<int> graph_isomorphic(int n, EdgeListGraph g1, EdgeListGraph g2) {
g1 = graph_cleanup(g1);
g2 = graph_cleanup(g2);
vector<int> perm;
for (int i = 0; i < n; ++i) {
perm.push_back(i);
}
do {
EdgeListGraph g11 = permute_graph(g1, perm);
if (graph_cleanup(g11) == g2) {
return perm;
}
} while (next_permutation(perm.begin(), perm.end()));
return {};
}
unsigned popcnt(unsigned x) {
unsigned ans = 0;
while (x) {
ans += (x & 1);
x >>= 1;
}
return ans;
}
int max_deg(const SparseGraph &g) {
pair<int, int> max_deg{-1, -1};
for (int i = 0; i < g.size(); ++i) {
max_deg = max(max_deg, {g[i].size(), i});
}
return max_deg.second;
}
namespace BigInt
{
using u32 = uint32_t;
using u64 = uint64_t;
constexpr u32 bi_size = 2048;
constexpr u32 bi_num = 2048 / 32;
struct U2048
{
struct BitObject
{
private:
u32 &ptr_;
int pos_;
public:
BitObject(u32 &ptr, int pos): ptr_(ptr), pos_(pos) {
}
operator u32() const {
return (ptr_ >> pos_) & 1;
}
u32 operator=(u32 v) {
ptr_ &= ~(1u << pos_);
ptr_ |= ((v & 1u) << pos_);
return v;
}
};
u32 val[bi_num];
U2048(u32 v = 0) {
memset(val, 0, sizeof val);
val[0] = v;
}
U2048(const string &s) {
memset(val, 0, sizeof val);
for (int i = 0, j = 0, k = 0; i < s.size();
i++, j++, k += j / 32, j %= 32) {
val[k] += static_cast<u32>(s[i] - '0') << j;
}
}
U2048(const vector<bool> &s) {
memset(val, 0, sizeof val);
for (int i = 0, j = 0, k = 0; i < s.size();
i++, j++, k += j / 32, j %= 32) {
val[k] += static_cast<u32>(s[i]) << j;
}
}
u32 operator[](int x) const {
return (val[x / 32] >> (x % 32)) & 1;
}
BitObject operator[](int x) {
return BitObject{val[x / 32], x % 32};
}
string to_string(int bits) {
string s;
for (int i = 0; i < bits; ++i) {
s += static_cast<char>('0' + operator[](i));
}
return s;
}
vector<int> bits_1() const {
vector<int> ans;
ans.reserve(bi_num);
for (int i = 0; i < bi_size; i++) {
if (operator[](i) == 1) {
ans.push_back(i);
}
}
return ans;
}
U2048 &operator+=(const U2048 &rhs) {
u64 z = val[0];
z += rhs.val[0];
val[0] = z;
z >>= 32;
for (int i = 1; i < bi_num; ++i) {
z += val[i];
z += rhs.val[i];
val[i] = z;
z >>= 32;
}
return *this;
}
U2048 operator+(const U2048 &rhs) const {
auto t = *this;
t += rhs;
return t;
}
U2048 operator-() const {
auto t = *this;
for (int i = 0; i < bi_num; ++i) {
t.val[i] = ~ t.val[i];
}
return t + 1;
}
U2048 &operator-=(const U2048 &rhs) {
return operator+=(-rhs);
}
U2048 operator-(const U2048 &rhs) const {
return operator+(-rhs);
}
bool operator<(const U2048 &rhs) const {
for (int i = bi_num - 1; i > 0; --i) {
if (val[i] != rhs.val[i])
return val[i] < rhs.val[i];
}
return val[0] < rhs.val[0];
}
bool operator<=(const U2048 &rhs) const {
for (int i = bi_num - 1; i > 0; --i) {
if (val[i] != rhs.val[i])
return val[i] <= rhs.val[i];
}
return val[0] <= rhs.val[0];
}
};
struct BinomTable
{
static const int size = 2048 + 1;
U2048 *C[size];
BinomTable() {
memset(C, 0, sizeof C);
for (int i = 0; i < size; i++) {
C[i] = new U2048[min(i + 2, 100)];
}
C[0][0] = 1;
for (int i = 1; i < size; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i && j <= 97; ++j) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
}
~BinomTable() {
for (int i = 0; i < size; i++) {
delete []C[i];
}
}
U2048 ord2set(U2048 x, int n, int k) {
U2048 ans = 0;
while (n > 0) {
u32 bit = 0;
if (k == 0 || C[n - 1][k - 1] <= x) {
if(k > 0) {
x -= C[n - 1][k - 1];
}
bit = 0;
} else {
bit = 1;
--k;
}
ans[--n] = bit;
}
return ans;
}
U2048 set2ord(U2048 x, int n, int k) {
U2048 ans = 0;
while (n > 0) {
u32 bit = x[n - 1];
if (bit) {
--k;
} else {
if (k > 0) {
ans += C[n - 1][k - 1];
}
}
--n;
}
return ans;
}
} c_table;
}
namespace Index
{
struct TreeDFS
{
int n;
int root;
vector<bool> vis;
SparseGraph g;
using subtree_info = pair<string, vector<int>>;
vector<subtree_info> subtree;
static bool info_cmp(const subtree_info &a, const subtree_info &b) {
if (a.second.size() != b.second.size()) {
return a.second.size() < b.second.size();
}
return a.first < b.first;
}
TreeDFS(int _n, EdgeListGraph _g): n(_n), root(-1), vis(_n, false),
g(graph_cast(_n, _g)), subtree(_n) {
actual_work();
}
void dfs(int x, int p) {
subtree_info info = {"(", {x}};
vector<subtree_info> sons;
for (auto y : g[x]) {
if (y == p) continue;
if (vis[y]) {
throw -1;
}
vis[y] = 1;
dfs(y, x);
sons.push_back(subtree[y]);
}
sort(sons.begin(), sons.end(), info_cmp);
for (auto son : sons) {
info.first += son.first;
copy(son.second.begin(), son.second.end(), back_inserter(info.second));
}
info.first += ")";
subtree[x] = info;
}
subtree_info actual_work() {
root = max_deg(g);
fill(vis.begin(), vis.end(), false);
try {
dfs(root, root);
} catch (int x) {
return {};
}
return subtree[root];
}
subtree_info work() {
return subtree[root];
}
};
int index_n = 11;
EdgeListGraph base_index = {
{0, 1}, {0, 2}, {2, 3}, {0, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9},
{9, 10}
};
TreeDFS base{index_n, base_index};
EdgeListGraph index_encode(int mask) {
EdgeListGraph g;
if (popcnt(mask ^ 1035) <= index_n / 2) {
// mode 1
g = base_index;
} else {
// mode 2
g = flip_graph(index_n, base_index);
}
auto deg = deg_sequence(index_n, g);
for (int i = 0; i < index_n; ++i) {
if ((~((mask >> i) + deg[i])) & 1) {
g.push_back({i, index_n});
}
}
return g;
}
vector<int> index_decode(EdgeListGraph g) {
g = graph_cleanup(g);
if(g.size() >= 30) {
g = flip_graph(index_n + 1, g);
}
SparseGraph gd = graph_cast(index_n + 1, g);
int u = max_deg(gd);
auto g1 = filter_node_dec(g, u);
TreeDFS td(index_n, g1);
auto [str, v] = td.work();
if(v.empty() || str != base.work().first) return {};
vector<int> ans(index_n + 1, -1);
for (int i = 0; i < v.size(); ++i) {
int t = v[i];
if(t >= u) ++t;
ans[t] = i;
}
ans[u] = index_n;
return ans;
}
void test(int T) {
while (T--) {
if (T % 100 == 0) cout << T << endl;
auto x = mt() % 2048;
auto ge = index_encode(x);
auto [g, tr] = shuffle_graph(index_n + 1, ge);
auto v = index_decode(g);
if (v.empty()) {
cout << T<< " ERROR!!!!" << endl;
} else {
for (int i = 0; i < index_n + 1; ++i) {
if (tr[v[i]] != i) {
cout << "wrong " << i << endl;
}
}
}
}
}
}
namespace Encoder
{
EncoderResult graph_encode(EncoderParameter param, EdgeListGraph g,
vector<int> ids) {
int n = param.labeled_n, k = param.lg2;
int un = param.unlabeled_n; // n + k + 1
vector<int> deg(un, 0);
for (int i = 0; i < k; ++i) {
for (int j = 0; j < n; ++j) {
if ((ids[j] >> i) & 1) {
g.push_back({i + n, j});
}
}
}
for (auto x : g) {
deg[x.first]++;
deg[x.second]++;
}
int u = k + n;
for (int i = 0; i < n; ++i) {
if (deg[i] % 2 != 0) {
g.push_back({i, u});
}
}
int mask = 0;
for (int i = 0; i < k; ++i) {
mask += (deg[i + n] % 2) << i;
}
EdgeListGraph index = Index::index_encode(mask);
for (auto x : index) {
g.push_back({x.first + n, x.second + n});
}
return EncoderResult{param, g};
}
EncoderParameter encode_param(int un) {
assert(un == graph_size);
return EncoderParameter{88, 100, 11, 519};
}
int encode_accept_len(EncoderParameter param) {
int n = param.labeled_n;
return n * (n - 1) / 2 + param.tab_len + 1;
}
EncoderResult encode(EncoderParameter param, vector<bool> str) {
int n = param.labeled_n;
EdgeListGraph g;
auto it = str.begin();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (*it) {
g.push_back({i, j});
}
++it;
}
}
vector<bool> ord_str(it, str.end() - 1);
BigInt::U2048 ord{ord_str};
// cerr << ord.to_string(106) << endl;
auto sets = BigInt::c_table.ord2set(ord, 1 << param.lg2, n);
// cerr << sets.to_string(128) << endl;
auto convert = sets.bits_1();
auto gout = graph_encode(param, g, convert);
if (str.back()) {
gout.g = flip_graph(param.unlabeled_n, gout.g);
}
return gout;
}
};
namespace Decoder
{
using Permutation = vector<int>;
struct DecodeResult
{
vector<int> num;
BigInt::U2048 num_set;
vector<int> perm;
bool flip;
};
namespace Test
{
bool is_permutation(Permutation perm) {
sort(perm.begin(), perm.end());
for (int i = 0; i < perm.size(); ++i) {
if (perm[i] != i) return false;
}
return true;
}
}
DecodeResult perm_decode(EncoderParameter param, EdgeListGraph ge) {
int n = param.labeled_n;
int un = param.unlabeled_n;
SparseGraph g = graph_cast(un, ge);
bool flip = false;
int oddc = 0;
map<int, int> odds;
for (int i = 0; i < un; i++) {
if (g[i].size() % 2 == 1) {
odds[i] = oddc++;
}
}
if (odds.size() > un / 2) {
flip = true;
ge = flip_graph(un, ge);
g = graph_cast(un, ge);
odds.clear();
oddc = 0;
for (int i = 0; i < un; i++) {
if (g[i].size() % 2 == 1) {
odds[i] = oddc++;
}
}
}
assert(odds.size() == param.lg2 + 1);
EdgeListGraph odd_subgraph;
for (int i = 0; i < ge.size(); ++i) {
auto e = ge[i];
if (odds.count(e.first) && odds.count(e.second)) {
odd_subgraph.push_back({odds[e.first], odds[e.second]});
}
}
auto index = Index::index_decode(odd_subgraph);
for (auto &x : odds) {
x.second = index[x.second];
}
vector<int> oddv(param.lg2 + 1, 0);
for (auto x : odds) {
oddv[x.second] = x.first;
}
int u = oddv[param.lg2];
BigInt::U2048 num_set = 0;
vector<int> num(un, 0);
vector<int> perm(un, -1);
for (int i = 0; i < param.lg2; ++i) {
int x = oddv[i];
for (auto y : g[x]) {
num[y] += 1 << i;
}
}
for (int i = 0; i <= param.lg2; ++i) {
int x = oddv[i];
num[x] = 114514;
}
map<int, int> num2id;
for (int x = 0; x < un; ++x) {
if (num[x] != 114514) {
num2id[num[x]] = 0;
num_set[num[x]] = 1;
}
}
int cnt = 0;
for (auto &id : num2id) {
id.second = cnt++;
}
for (int x = 0; x < un; ++x) {
if (num[x] != 114514) {
perm[x] = num2id[num[x]];
} else {
perm[x] = odds[x] + n;
}
}
return DecodeResult{num, num_set, perm, flip};
}
vector<bool> decode(EncoderResult res) {
const auto ¶m = res.param;
auto g = res.g;
auto [num, num_set, perm, flip] = perm_decode(param, g);
#ifdef _DEBUG
if (!Test::is_permutation(perm)) {
throw exception("not a permutation -- perm_decode");
}
#endif
if (flip) g = flip_graph(param.unlabeled_n, g);
auto gi = graph_cleanup(permute_graph(g, perm));
vector<bool> ans(Encoder::encode_accept_len(param), false);
int n = param.labeled_n;
auto it = ans.begin();
auto jt = gi.begin();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
pair<int, int> p = {i, j};
while (jt != gi.end() && *jt < p) ++jt;
if (jt != gi.end() && *jt == p) {
*it = true;
}
++it;
}
}
// cerr << num_set.to_string(128) << endl;
auto num_ord = BigInt::c_table.set2ord(num_set, 1 << param.lg2, n);
// cerr << num_ord.to_string(106) << endl;
for (int i = 0; i < param.tab_len; ++i) {
*it++ = num_ord[i];
}
*it++ = flip;
return ans;
}
}
namespace Test
{
bool test(EncoderParameter param) {
int len = Encoder::encode_accept_len(param);
vector<bool> arr(len, false);
bernoulli_distribution bd;
for (int i = 0; i < len; ++i) {
arr[i] = bd(mt);
}
auto res = Encoder::encode(param, arr).g;
vector<int> perm(param.unlabeled_n, 0);
for (int i = 0; i < param.unlabeled_n; ++i) {
perm[i] = i;
}
shuffle(perm.begin(), perm.end(), mt);
for (auto &x : res) {
x = {perm[x.first], perm[x.second]};
}
shuffle(res.begin(), res.end(), mt);
res = graph_cleanup(res);
auto dec = Decoder::decode(EncoderResult{param, res});
return dec == arr;
}
}
int main(int argc, char *argv[]) {
//freopen("1.in", "r", stdin);
//freopen("1.out", "w", stdout);
cin.sync_with_stdio(false);
cin.tie(nullptr);
const auto param = Encoder::encode_param(graph_size);
string s;
cin >> s;
if (s[0] == 'T') {
int bound;
cin >> bound;
for (int i = 0; i < bound; ++i) {
if (!Test::test(param)) {
cout << "ERROR!" << endl;
} else if (i % 100 == 0) {
cout << i << endl;
}
}
} else if (s[0] == 'N') {
cout << Encoder::encode_accept_len(param) << endl;
} else if (s[0] == 'A') {
string input;
cin >> input;
vector<bool> arr(input.size(), false);
transform(input.begin(), input.end(), arr.begin(), [](char c)
{
return c == '1';
});
auto g = Encoder::encode(param, arr).g;
cout << g.size() << '\n';
for (auto x : g) {
cout << x.first + 1 << ' ' << x.second + 1 << '\n';
}
} else if (s[0] == 'B') {
int e;
cin >> e;
EdgeListGraph g;
g.reserve(e);
for (int i = 0; i < e; ++i) {
int u, v;
cin >> u >> v;
g.push_back({u - 1, v - 1});
}
auto arr = Decoder::decode({param, g});
string output;
transform(arr.begin(), arr.end(), back_inserter(output), [](bool c)
{
return c ? '1' : '0';
});
cout << output << '\n';
}
return 0;
}
namespace Trash
{
int base_n = 7;
EdgeListGraph base_graph = {{0, 1}, {0, 2}, {2, 3}, {0, 4}, {4, 5}, {5, 6}};
EdgeListGraph base_graph1 = {
{0, 1}, {0, 2}, {2, 3}, {0, 4}, {4, 5}, {5, 6}
};
vector<int> bad_set(int n, EdgeListGraph ge, vector<int> candidate) {
auto gd = graph_cast(n, ge);
vector<int> s;
for (int i : candidate) {
//// cerr << i << endl;
EdgeListGraph gn = ge;
for (int j = 0; j < n; ++j) {
int deg = gd[j].size() + ((i >> j) & 1);
if (deg % 2 == 0) {
gn.push_back({j, n});
}
}
bool bad = false;
for (int j = 0; j < n; ++j) {
EdgeListGraph gj = filter_node_dec(gn, j);
if (graph_isomorphic(n, gj, ge).size()) {
bad = true;
break;
}
}
if (bad) {
s.push_back(i);
}
}
return s;
}
int main() {
vector<int> cand;
for (int i = 0; i < (1 << base_n); ++i) {
cand.push_back(i);
}
auto vec = bad_set(base_n, flip_graph(base_n, base_graph1), cand);
for (auto x : vec) {
cout << x << ",";
}
cout << endl;
vector<int> perm;
for (int i = 0; i < base_n; ++i) {
perm.push_back(i);
}
do {
auto base_graph2 = graph_cleanup(permute_graph(base_graph, perm));
auto vec2 = bad_set(base_n, base_graph2, vec);
vector<int> vec3;
set_intersection(vec.begin(), vec.end(), vec2.begin(), vec2.end(),
back_inserter(vec3));
if (vec3.size() == 1 && rand() % 50) continue;
for (auto x : perm) cout << x;
cout << ' ' << vec3.size() << endl;
for (auto x : perm) cerr << x;
// cerr << ' ' << vec3.size() << endl;
} while (next_permutation(perm.begin(), perm.end()));
return 0;
}
}