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
unlabeled vertices. The length of the bit string 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
A note from my friend ztr: “An algorithm solving graph isomorphism for 90% of the input” may actually exist.
Obviously,
A basic algorithm
Firstly, any labeled graph with
We try to label the vertices in
Now we just need to label the vertices

Then we just need to determine which vertices are in
In order to find vertex
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
This is already the first in the class. But our question is,
Optimization #1
The above algorithm embeds a labeled graph with
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
After all the edges within
When decoding, we try to find all the vertices with odd degrees,
which is

This graph has no nontrivial isomorphism, so we can label it easily.
With this setup, we can embed a labeled graph with
Optimization #2
When we are binary encoding
- Instead of: for any vertex in
with label , it has an edge to if and only of the -th bit in the binary representation of is - We do this: for any vertex in
with label , it has an edge to if and only of the -th bit in the binary representation of is
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) {
= 0;
U2048 ans while (n > 0) {
= 0;
u32 bit if (k == 0 || C[n - 1][k - 1] <= x) {
if(k > 0) {
-= C[n - 1][k - 1];
x }
= 0;
bit } else {
= 1;
bit --k;
}
[--n] = bit;
ans}
return ans;
}
U2048 set2ord(U2048 x, int n, int k) {
= 0;
U2048 ans while (n > 0) {
= x[n - 1];
u32 bit if (bit) {
--k;
} else {
if (k > 0) {
+= C[n - 1][k - 1];
ans }
}
--n;
}
return ans;
}
This introduces a problem. During decoding, we need to identify the
small graph with
The solution is to construct multiple candidate
With this technique, we can encode an extra
Optimization #3
Sure do. We plugged in

Indeed,
When the edges between
is no less then , we use the following graph:with such construction,
will have the highest degree in the subgraph induced by .When the edges between
is no more than , use the complement graph of it, and will have the lowest degree in the subgraph induced by .
Now we can encode
More optimizations?
- inverse the output graph,
bit - we can find multiple
choices, and it’s easy to find such small graphs, which gives us an extra bit - ……
Some other minor optimizations exist, but I’m too lazy to write it here.
Analysis
Our lower bound is
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) {
[x.first].push_back(x.second);
g[x.second].push_back(x.first);
g}
return g;
}
EdgeListGraph graph_cleanup(EdgeListGraph g) {
for (auto &x : g) {
if (x.first > x.second) swap(x.first, x.second);
}
(g.begin(), g.end());
sortauto it = unique(g.begin(), g.end());
.resize(it - g.begin());
greturn g;
}
EdgeListGraph graph_cast(const SparseGraph &gd) {
;
EdgeListGraph gefor (int x = 0; x < gd.size(); ++x) {
for (auto y : gd[x]) {
if (x < y)
.push_back({x, y});
ge}
}
return ge;
}
vector<int> deg_sequence(int n, const EdgeListGraph &g) {
vector<int> ans(n, 0);
for (auto x : g) {
[x.first] += 1;
ans[x.second] += 1;
ans}
return ans;
}
EdgeListGraph complete_graph(int n) {
;
EdgeListGraph ans.reserve(n * (n - 1) / 2);
ansfor (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
.push_back({i, j});
ans}
}
return ans;
}
EdgeListGraph flip_graph(int n, EdgeListGraph g) {
= graph_cleanup(g);
g ;
EdgeListGraph go= complete_graph(n);
EdgeListGraph Kn (Kn.begin(), Kn.end(), g.begin(), g.end(), back_inserter(go));
set_differencereturn go;
}
EdgeListGraph filter_node_dec(const EdgeListGraph &g, int x) {
;
EdgeListGraph ansfor (auto e : g) {
if (e.first == x || e.second == x) continue;
if (e.first > x) --e.first;
if (e.second > x) --e.second;
.push_back(e);
ans}
return ans;
}
EdgeListGraph filter_node(const EdgeListGraph &g, int x) {
;
EdgeListGraph ansfor (auto e : g) {
if (e.first == x || e.second == x) continue;
.push_back(e);
ans}
return ans;
}
EdgeListGraph permute_graph(EdgeListGraph g, vector<int> perm) {
for (auto &x : g) {
.first = perm[x.first];
x.second = perm[x.second];
x}
return g;
}
pair<EdgeListGraph, vector<int>> shuffle_graph(int n, EdgeListGraph g) {
vector<int> perm(n, 0);
for (int i = 0; i < n; ++i) {
[i] = i;
perm}
(perm.begin(), perm.end(), mt);
shufflefor (auto &x : g) {
= {perm[x.first], perm[x.second]};
x }
return make_pair(g, perm);
}
vector<int> graph_isomorphic(int n, EdgeListGraph g1, EdgeListGraph g2) {
= graph_cleanup(g1);
g1 = graph_cleanup(g2);
g2 vector<int> perm;
for (int i = 0; i < n; ++i) {
.push_back(i);
perm}
do {
= permute_graph(g1, perm);
EdgeListGraph g11 if (graph_cleanup(g11) == g2) {
return perm;
}
} while (next_permutation(perm.begin(), perm.end()));
return {};
}
unsigned popcnt(unsigned x) {
unsigned ans = 0;
while (x) {
+= (x & 1);
ans >>= 1;
x }
return ans;
}
int max_deg(const SparseGraph &g) {
pair<int, int> max_deg{-1, -1};
for (int i = 0; i < g.size(); ++i) {
= max(max_deg, {g[i].size(), i});
max_deg }
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:
&ptr_;
u32 int pos_;
public:
(u32 &ptr, int pos): ptr_(ptr), pos_(pos) {
BitObject}
operator u32() const {
return (ptr_ >> pos_) & 1;
}
operator=(u32 v) {
u32 ptr_ &= ~(1u << pos_);
ptr_ |= ((v & 1u) << pos_);
return v;
}
};
[bi_num];
u32 val
(u32 v = 0) {
U2048memset(val, 0, sizeof val);
[0] = v;
val}
(const string &s) {
U2048memset(val, 0, sizeof val);
for (int i = 0, j = 0, k = 0; i < s.size();
++, j++, k += j / 32, j %= 32) {
i[k] += static_cast<u32>(s[i] - '0') << j;
val}
}
(const vector<bool> &s) {
U2048memset(val, 0, sizeof val);
for (int i = 0, j = 0, k = 0; i < s.size();
++, j++, k += j / 32, j %= 32) {
i[k] += static_cast<u32>(s[i]) << j;
val}
}
operator[](int x) const {
u32 return (val[x / 32] >> (x % 32)) & 1;
}
operator[](int x) {
BitObject return BitObject{val[x / 32], x % 32};
}
string to_string(int bits) {
string s;
for (int i = 0; i < bits; ++i) {
+= static_cast<char>('0' + operator[](i));
s }
return s;
}
vector<int> bits_1() const {
vector<int> ans;
.reserve(bi_num);
ansfor (int i = 0; i < bi_size; i++) {
if (operator[](i) == 1) {
.push_back(i);
ans}
}
return ans;
}
&operator+=(const U2048 &rhs) {
U2048 = val[0];
u64 z += rhs.val[0];
z [0] = z;
val>>= 32;
z for (int i = 1; i < bi_num; ++i) {
+= val[i];
z += rhs.val[i];
z [i] = z;
val>>= 32;
z }
return *this;
}
operator+(const U2048 &rhs) const {
U2048 auto t = *this;
+= rhs;
t return t;
}
operator-() const {
U2048 auto t = *this;
for (int i = 0; i < bi_num; ++i) {
.val[i] = ~ t.val[i];
t}
return t + 1;
}
&operator-=(const U2048 &rhs) {
U2048 return operator+=(-rhs);
}
operator-(const U2048 &rhs) const {
U2048 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;
*C[size];
U2048
() {
BinomTablememset(C, 0, sizeof C);
for (int i = 0; i < size; i++) {
[i] = new U2048[min(i + 2, 100)];
C}
[0][0] = 1;
Cfor (int i = 1; i < size; ++i) {
[i][0] = 1;
Cfor (int j = 1; j <= i && j <= 97; ++j) {
[i][j] = C[i - 1][j - 1] + C[i - 1][j];
C}
}
}
~BinomTable() {
for (int i = 0; i < size; i++) {
delete []C[i];
}
}
U2048 ord2set(U2048 x, int n, int k) {
= 0;
U2048 ans while (n > 0) {
= 0;
u32 bit if (k == 0 || C[n - 1][k - 1] <= x) {
if(k > 0) {
-= C[n - 1][k - 1];
x }
= 0;
bit } else {
= 1;
bit --k;
}
[--n] = bit;
ans}
return ans;
}
U2048 set2ord(U2048 x, int n, int k) {
= 0;
U2048 ans while (n > 0) {
= x[n - 1];
u32 bit if (bit) {
--k;
} else {
if (k > 0) {
+= C[n - 1][k - 1];
ans }
}
--n;
}
return ans;
}
} c_table;
}
namespace Index
{
struct TreeDFS
{
int n;
int root;
vector<bool> vis;
;
SparseGraph gusing 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;
}
(int _n, EdgeListGraph _g): n(_n), root(-1), vis(_n, false),
TreeDFS(graph_cast(_n, _g)), subtree(_n) {
g();
actual_work}
void dfs(int x, int p) {
= {"(", {x}};
subtree_info info vector<subtree_info> sons;
for (auto y : g[x]) {
if (y == p) continue;
if (vis[y]) {
throw -1;
}
[y] = 1;
vis(y, x);
dfs.push_back(subtree[y]);
sons}
(sons.begin(), sons.end(), info_cmp);
sortfor (auto son : sons) {
.first += son.first;
info(son.second.begin(), son.second.end(), back_inserter(info.second));
copy}
.first += ")";
info[x] = info;
subtree}
subtree_info actual_work() {
= max_deg(g);
root (vis.begin(), vis.end(), false);
filltry {
(root, root);
dfs} 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}
};
{index_n, base_index};
TreeDFS base
EdgeListGraph index_encode(int mask) {
;
EdgeListGraph gif (popcnt(mask ^ 1035) <= index_n / 2) {
// mode 1
= base_index;
g } else {
// mode 2
= flip_graph(index_n, base_index);
g }
auto deg = deg_sequence(index_n, g);
for (int i = 0; i < index_n; ++i) {
if ((~((mask >> i) + deg[i])) & 1) {
.push_back({i, index_n});
g}
}
return g;
}
vector<int> index_decode(EdgeListGraph g) {
= graph_cleanup(g);
g if(g.size() >= 30) {
= flip_graph(index_n + 1, g);
g }
= graph_cast(index_n + 1, g);
SparseGraph gd 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;
[t] = i;
ans}
[u] = index_n;
ansreturn 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) {
.push_back({i + n, j});
g}
}
}
for (auto x : g) {
[x.first]++;
deg[x.second]++;
deg}
int u = k + n;
for (int i = 0; i < n; ++i) {
if (deg[i] % 2 != 0) {
.push_back({i, u});
g}
}
int mask = 0;
for (int i = 0; i < k; ++i) {
+= (deg[i + n] % 2) << i;
mask }
= Index::index_encode(mask);
EdgeListGraph index for (auto x : index) {
.push_back({x.first + n, x.second + n});
g}
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 gauto it = str.begin();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (*it) {
.push_back({i, j});
g}
++it;
}
}
vector<bool> ord_str(it, str.end() - 1);
::U2048 ord{ord_str};
BigInt// 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()) {
.g = flip_graph(param.unlabeled_n, gout.g);
gout}
return gout;
}
};
namespace Decoder
{
using Permutation = vector<int>;
struct DecodeResult
{
vector<int> num;
::U2048 num_set;
BigIntvector<int> perm;
bool flip;
};
namespace Test
{
bool is_permutation(Permutation perm) {
(perm.begin(), perm.end());
sortfor (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;
= graph_cast(un, ge);
SparseGraph g bool flip = false;
int oddc = 0;
map<int, int> odds;
for (int i = 0; i < un; i++) {
if (g[i].size() % 2 == 1) {
[i] = oddc++;
odds}
}
if (odds.size() > un / 2) {
= true;
flip = flip_graph(un, ge);
ge = graph_cast(un, ge);
g .clear();
odds= 0;
oddc for (int i = 0; i < un; i++) {
if (g[i].size() % 2 == 1) {
[i] = oddc++;
odds}
}
}
assert(odds.size() == param.lg2 + 1);
;
EdgeListGraph odd_subgraphfor (int i = 0; i < ge.size(); ++i) {
auto e = ge[i];
if (odds.count(e.first) && odds.count(e.second)) {
.push_back({odds[e.first], odds[e.second]});
odd_subgraph}
}
auto index = Index::index_decode(odd_subgraph);
for (auto &x : odds) {
.second = index[x.second];
x}
vector<int> oddv(param.lg2 + 1, 0);
for (auto x : odds) {
[x.second] = x.first;
oddv}
int u = oddv[param.lg2];
::U2048 num_set = 0;
BigIntvector<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]) {
[y] += 1 << i;
num}
}
for (int i = 0; i <= param.lg2; ++i) {
int x = oddv[i];
[x] = 114514;
num}
map<int, int> num2id;
for (int x = 0; x < un; ++x) {
if (num[x] != 114514) {
[num[x]] = 0;
num2id[num[x]] = 1;
num_set}
}
int cnt = 0;
for (auto &id : num2id) {
.second = cnt++;
id}
for (int x = 0; x < un; ++x) {
if (num[x] != 114514) {
[x] = num2id[num[x]];
perm} else {
[x] = odds[x] + n;
perm}
}
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 bdfor (int i = 0; i < len; ++i) {
[i] = bd(mt);
arr}
auto res = Encoder::encode(param, arr).g;
vector<int> perm(param.unlabeled_n, 0);
for (int i = 0; i < param.unlabeled_n; ++i) {
[i] = i;
perm}
(perm.begin(), perm.end(), mt);
shufflefor (auto &x : res) {
= {perm[x.first], perm[x.second]};
x }
(res.begin(), res.end(), mt);
shuffle= graph_cleanup(res);
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);
(input.begin(), input.end(), arr.begin(), [](char c)
transform{
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.reserve(e);
gfor (int i = 0; i < e; ++i) {
int u, v;
cin >> u >> v;
.push_back({u - 1, v - 1});
g}
auto arr = Decoder::decode({param, g});
string output;
(arr.begin(), arr.end(), back_inserter(output), [](bool c)
transform{
return c ? '1' : '0';
});
cout << output << '\n';
}
return 0;
}
namespace Trash
{
int base_n = 7;
= {{0, 1}, {0, 2}, {2, 3}, {0, 4}, {4, 5}, {5, 6}};
EdgeListGraph base_graph
= {
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;
= ge;
EdgeListGraph gn for (int j = 0; j < n; ++j) {
int deg = gd[j].size() + ((i >> j) & 1);
if (deg % 2 == 0) {
.push_back({j, n});
gn}
}
bool bad = false;
for (int j = 0; j < n; ++j) {
= filter_node_dec(gn, j);
EdgeListGraph gj if (graph_isomorphic(n, gj, ge).size()) {
= true;
bad break;
}
}
if (bad) {
.push_back(i);
s}
}
return s;
}
int main() {
vector<int> cand;
for (int i = 0; i < (1 << base_n); ++i) {
.push_back(i);
cand}
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) {
.push_back(i);
perm}
do {
auto base_graph2 = graph_cleanup(permute_graph(base_graph, perm));
auto vec2 = bad_set(base_n, base_graph2, vec);
vector<int> vec3;
(vec.begin(), vec.end(), vec2.begin(), vec2.end(),
set_intersection(vec3));
back_inserterif (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;
}
}