Problem 1002: Connections II

Problem 1002 source code

C++

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <limits>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

namespace {

using i64 = std::int64_t;

struct Options {
    std::string file = "resources/documents/1002_input.txt";
    bool run_checkpoints = true;
};

struct Interval {
    int left;
    int right;
};

struct SolveResult {
    bool bipartite;
    int answer;
    i64 crossings;
    int components;
};

bool parse_string_after_prefix(const std::string& arg,
                               const std::string& prefix,
                               std::string& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    value = arg.substr(prefix.size());
    return !value.empty();
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_string_after_prefix(arg, "--file=", options.file)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

class ParityDsu {
  public:
    explicit ParityDsu(const int n) : parent_(n), parity_(n, 0), size_(n, 1), counts_(n, {1, 0}) {
        for (int i = 0; i < n; ++i) {
            parent_[i] = i;
        }
    }

    std::pair<int, int> find(const int x) {
        if (parent_[x] == x) {
            return {x, 0};
        }
        const auto root = find(parent_[x]);
        parity_[x] ^= root.second;
        parent_[x] = root.first;
        return {parent_[x], parity_[x]};
    }

    bool unite(const int a, const int b) {
        const auto [ra, pa] = find(a);
        const auto [rb, pb] = find(b);
        if (ra == rb) {
            return (pa ^ pb) == 1;
        }

        const int link = pa ^ pb ^ 1;
        if (size_[ra] < size_[rb]) {
            parent_[ra] = rb;
            parity_[ra] = link;
            counts_[rb][0] += counts_[ra][link];
            counts_[rb][1] += counts_[ra][link ^ 1];
            size_[rb] += size_[ra];
        } else {
            parent_[rb] = ra;
            parity_[rb] = link;
            counts_[ra][0] += counts_[rb][link];
            counts_[ra][1] += counts_[rb][link ^ 1];
            size_[ra] += size_[rb];
        }
        return true;
    }

    int best_sum() const {
        int total = 0;
        for (std::size_t i = 0; i < parent_.size(); ++i) {
            if (parent_[i] == static_cast<int>(i)) {
                total += std::max(counts_[i][0], counts_[i][1]);
            }
        }
        return total;
    }

    int component_count() const {
        int total = 0;
        for (std::size_t i = 0; i < parent_.size(); ++i) {
            if (parent_[i] == static_cast<int>(i)) {
                ++total;
            }
        }
        return total;
    }

  private:
    std::vector<int> parent_;
    std::vector<int> parity_;
    std::vector<int> size_;
    std::vector<std::array<int, 2>> counts_;
};

std::vector<int> parse_csv_array(const std::string& text) {
    std::vector<int> values;
    std::istringstream input(text);
    std::string token;
    while (std::getline(input, token, ',')) {
        if (token.find_first_not_of(" \t\r\n") == std::string::npos) {
            continue;
        }
        const long long value = std::stoll(token);
        if (value < 0 || value > std::numeric_limits<int>::max()) {
            throw std::runtime_error("Array value is out of range");
        }
        values.push_back(static_cast<int>(value));
    }
    return values;
}

std::vector<int> read_csv_array(const std::string& file_path) {
    std::ifstream input(file_path);
    if (!input) {
        throw std::runtime_error("Could not open input file: " + file_path);
    }

    std::ostringstream buffer;
    buffer << input.rdbuf();
    return parse_csv_array(buffer.str());
}

std::vector<Interval> build_intervals(const std::vector<int>& a) {
    if (a.size() % 2 != 0) {
        throw std::runtime_error("Array length is odd");
    }

    const int n = static_cast<int>(a.size() / 2);
    std::vector<int> first(static_cast<std::size_t>(n), -1);
    std::vector<int> occurrences(static_cast<std::size_t>(n), 0);
    std::vector<Interval> intervals;
    intervals.reserve(static_cast<std::size_t>(n));

    for (int pos = 0; pos < static_cast<int>(a.size()); ++pos) {
        const int value = a[static_cast<std::size_t>(pos)];
        if (value < 0 || value >= n) {
            throw std::runtime_error("Array values must be in [0,n)");
        }
        ++occurrences[static_cast<std::size_t>(value)];
        if (occurrences[static_cast<std::size_t>(value)] == 1) {
            first[static_cast<std::size_t>(value)] = pos;
        } else if (occurrences[static_cast<std::size_t>(value)] == 2) {
            intervals.push_back({first[static_cast<std::size_t>(value)], pos});
        } else {
            throw std::runtime_error("A value occurs more than twice");
        }
    }

    for (const int count : occurrences) {
        if (count != 2) {
            throw std::runtime_error("A value does not occur exactly twice");
        }
    }

    std::sort(intervals.begin(), intervals.end(), [](const Interval& lhs, const Interval& rhs) {
        return lhs.left < rhs.left;
    });
    return intervals;
}

bool crosses(const Interval& lhs, const Interval& rhs) {
    if (lhs.left < rhs.left) {
        return lhs.left < rhs.left && rhs.left < lhs.right && lhs.right < rhs.right;
    }
    return rhs.left < lhs.left && lhs.left < rhs.right && rhs.right < lhs.right;
}

SolveResult solve_array(const std::vector<int>& a) {
    const std::vector<Interval> intervals = build_intervals(a);
    const int n = static_cast<int>(intervals.size());
    ParityDsu dsu(n);
    std::set<std::pair<int, int>> active_by_right;
    i64 crossings = 0;

    for (int i = 0; i < n; ++i) {
        const Interval current = intervals[static_cast<std::size_t>(i)];
        auto it = active_by_right.lower_bound({current.left + 1, -1});
        while (it != active_by_right.end() && it->first < current.right) {
            if (!dsu.unite(i, it->second)) {
                return {false, -1, crossings + 1, 0};
            }
            ++crossings;
            ++it;
        }
        active_by_right.insert({current.right, i});
    }

    return {true, dsu.best_sum(), crossings, dsu.component_count()};
}

SolveResult brute_force_array(const std::vector<int>& a) {
    const std::vector<Interval> intervals = build_intervals(a);
    const int n = static_cast<int>(intervals.size());
    std::vector<std::pair<int, int>> edges;

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (crosses(intervals[static_cast<std::size_t>(i)], intervals[static_cast<std::size_t>(j)])) {
                edges.push_back({i, j});
            }
        }
    }

    int best = -1;
    for (int mask = 0; mask < (1 << n); ++mask) {
        bool ok = true;
        for (const auto [u, v] : edges) {
            if (((mask >> u) & 1) == ((mask >> v) & 1)) {
                ok = false;
                break;
            }
        }
        if (ok) {
            best = std::max(best, __builtin_popcount(static_cast<unsigned>(mask)));
        }
    }

    return {best >= 0, best, static_cast<i64>(edges.size()), 0};
}

void validate_all_words(const int n,
                        std::vector<int>& word,
                        std::vector<int>& counts,
                        const int pos) {
    if (pos == 2 * n) {
        const SolveResult fast = solve_array(word);
        const SolveResult brute = brute_force_array(word);
        assert(fast.bipartite == brute.bipartite);
        if (fast.bipartite) {
            assert(fast.answer == brute.answer);
            assert(fast.crossings == brute.crossings);
        }
        return;
    }

    for (int value = 0; value < n; ++value) {
        if (counts[static_cast<std::size_t>(value)] == 2) {
            continue;
        }
        ++counts[static_cast<std::size_t>(value)];
        word[static_cast<std::size_t>(pos)] = value;
        validate_all_words(n, word, counts, pos + 1);
        --counts[static_cast<std::size_t>(value)];
    }
}

void run_checkpoints() {
    assert(solve_array({0, 1, 2, 1, 0, 2}).answer == 2);
    assert(solve_array({0, 0, 1, 1, 2, 2}).answer == 3);
    assert(!solve_array({0, 1, 2, 0, 1, 2}).bipartite);

    for (int n = 1; n <= 4; ++n) {
        std::vector<int> word(static_cast<std::size_t>(2 * n), 0);
        std::vector<int> counts(static_cast<std::size_t>(n), 0);
        validate_all_words(n, word, counts, 0);
    }
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints) {
        run_checkpoints();
    }

    try {
        const std::vector<int> input = read_csv_array(options.file);
        const SolveResult result = solve_array(input);
        if (!result.bipartite) {
            throw std::runtime_error("The interval crossing graph is not bipartite");
        }
        std::cout << result.answer << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 2;
    }

    return 0;
}

Python

import sys
from collections import namedtuple

sys.setrecursionlimit(1_000_000)

SolveResult = namedtuple("SolveResult", ["bipartite", "answer", "crossings", "components"])

MASK64 = (1 << 64) - 1


def splitmix64(x):
    x = (x + 0x9E3779B97F4A7C15) & MASK64
    x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK64
    x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK64
    return x ^ (x >> 31)


class TreapNode:
    __slots__ = ("key", "priority", "left", "right")

    def __init__(self, key):
        self.key = key
        self.priority = splitmix64((key[0] << 32) ^ key[1])
        self.left = None
        self.right = None


def rotate_right(root):
    nxt = root.left
    root.left = nxt.right
    nxt.right = root
    return nxt


def rotate_left(root):
    nxt = root.right
    root.right = nxt.left
    nxt.left = root
    return nxt


def treap_insert(root, key):
    if root is None:
        return TreapNode(key)
    if key < root.key:
        root.left = treap_insert(root.left, key)
        if root.left.priority < root.priority:
            root = rotate_right(root)
    elif key > root.key:
        root.right = treap_insert(root.right, key)
        if root.right.priority < root.priority:
            root = rotate_left(root)
    return root


def treap_collect_range(root, lo_key, hi_key, out):
    if root is None:
        return
    if root.key >= lo_key:
        treap_collect_range(root.left, lo_key, hi_key, out)
    if lo_key <= root.key < hi_key:
        out.append(root.key)
    if root.key < hi_key:
        treap_collect_range(root.right, lo_key, hi_key, out)


class ParityDsu:
    def __init__(self, n):
        self.parent = list(range(n))
        self.parity = [0] * n
        self.size = [1] * n
        self.counts = [[1, 0] for _ in range(n)]

    def find(self, x):
        if self.parent[x] == x:
            return x, 0
        root, root_parity = self.find(self.parent[x])
        self.parity[x] ^= root_parity
        self.parent[x] = root
        return self.parent[x], self.parity[x]

    def unite(self, a, b):
        ra, pa = self.find(a)
        rb, pb = self.find(b)
        if ra == rb:
            return (pa ^ pb) == 1

        link = pa ^ pb ^ 1
        if self.size[ra] < self.size[rb]:
            self.parent[ra] = rb
            self.parity[ra] = link
            self.counts[rb][0] += self.counts[ra][link]
            self.counts[rb][1] += self.counts[ra][link ^ 1]
            self.size[rb] += self.size[ra]
        else:
            self.parent[rb] = ra
            self.parity[rb] = link
            self.counts[ra][0] += self.counts[rb][link]
            self.counts[ra][1] += self.counts[rb][link ^ 1]
            self.size[ra] += self.size[rb]
        return True

    def best_sum(self):
        total = 0
        for i in range(len(self.parent)):
            if self.parent[i] == i:
                total += max(self.counts[i][0], self.counts[i][1])
        return total

    def component_count(self):
        return sum(1 for i in range(len(self.parent)) if self.parent[i] == i)


def parse_csv_array(text):
    values = []
    for token in text.split(","):
        if token.strip() == "":
            continue
        value = int(token)
        if value < 0:
            raise ValueError("Array value is out of range")
        values.append(value)
    return values


def read_csv_array(path):
    with open(path) as fin:
        return parse_csv_array(fin.read())


def build_intervals(a):
    if len(a) % 2 != 0:
        raise ValueError("Array length is odd")

    n = len(a) // 2
    first = [-1] * n
    occurrences = [0] * n
    intervals = []

    for pos, value in enumerate(a):
        if value < 0 or value >= n:
            raise ValueError("Array values must be in [0,n)")
        occurrences[value] += 1
        if occurrences[value] == 1:
            first[value] = pos
        elif occurrences[value] == 2:
            intervals.append((first[value], pos))
        else:
            raise ValueError("A value occurs more than twice")

    for count in occurrences:
        if count != 2:
            raise ValueError("A value does not occur exactly twice")

    intervals.sort(key=lambda iv: iv[0])
    return intervals


def crosses(lhs, rhs):
    if lhs[0] < rhs[0]:
        return lhs[0] < rhs[0] and rhs[0] < lhs[1] and lhs[1] < rhs[1]
    return rhs[0] < lhs[0] and lhs[0] < rhs[1] and rhs[1] < lhs[1]


def solve_array(a):
    intervals = build_intervals(a)
    n = len(intervals)
    dsu = ParityDsu(n)
    active_by_right = None  # treap of (right, index)
    crossings = 0

    for i in range(n):
        left, right = intervals[i]
        crossing_keys = []
        treap_collect_range(active_by_right, (left + 1, -1), (right, -1), crossing_keys)
        for _, other in crossing_keys:
            if not dsu.unite(i, other):
                return SolveResult(False, -1, crossings + 1, 0)
            crossings += 1
        active_by_right = treap_insert(active_by_right, (right, i))

    return SolveResult(True, dsu.best_sum(), crossings, dsu.component_count())


def brute_force_array(a):
    intervals = build_intervals(a)
    n = len(intervals)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            if crosses(intervals[i], intervals[j]):
                edges.append((i, j))

    best = -1
    for mask in range(1 << n):
        ok = True
        for u, v in edges:
            if ((mask >> u) & 1) == ((mask >> v) & 1):
                ok = False
                break
        if ok:
            best = max(best, bin(mask).count("1"))

    return SolveResult(best >= 0, best, len(edges), 0)


def validate_all_words(n, word, counts, pos):
    if pos == 2 * n:
        fast = solve_array(word)
        brute = brute_force_array(word)
        assert fast.bipartite == brute.bipartite
        if fast.bipartite:
            assert fast.answer == brute.answer
            assert fast.crossings == brute.crossings
        return

    for value in range(n):
        if counts[value] == 2:
            continue
        counts[value] += 1
        word[pos] = value
        validate_all_words(n, word, counts, pos + 1)
        counts[value] -= 1


def run_checkpoints():
    assert solve_array([0, 1, 2, 1, 0, 2]).answer == 2
    assert solve_array([0, 0, 1, 1, 2, 2]).answer == 3
    assert not solve_array([0, 1, 2, 0, 1, 2]).bipartite

    for n in range(1, 5):
        word = [0] * (2 * n)
        counts = [0] * n
        validate_all_words(n, word, counts, 0)


def main(argv):
    file_path = "resources/documents/1002_input.txt"
    do_checkpoints = True
    for arg in argv[1:]:
        if arg == "--skip-checkpoints":
            do_checkpoints = False
        elif arg.startswith("--file="):
            file_path = arg[len("--file="):]
        else:
            sys.stderr.write("Unknown argument: " + arg + "\n")
            return 1

    if do_checkpoints:
        run_checkpoints()

    values = read_csv_array(file_path)
    result = solve_array(values)
    if not result.bipartite:
        sys.stderr.write("The interval crossing graph is not bipartite\n")
        return 2
    print(result.answer)
    return 0


if __name__ == "__main__":
    sys.exit(main(sys.argv))

Java

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

public class Euler1002 {

    static final class SolveResult {
        final boolean bipartite;
        final int answer;
        final long crossings;
        final int components;

        SolveResult(boolean bipartite, int answer, long crossings, int components) {
            this.bipartite = bipartite;
            this.answer = answer;
            this.crossings = crossings;
            this.components = components;
        }
    }

    static final class ParityDsu {
        private final int[] parent;
        private final int[] parity;
        private final int[] size;
        private final int[][] counts;

        ParityDsu(int n) {
            parent = new int[n];
            parity = new int[n];
            size = new int[n];
            counts = new int[n][2];
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
                size[i] = 1;
                counts[i][0] = 1;
                counts[i][1] = 0;
            }
        }

        // returns { root, parityToRoot }
        int[] find(int x) {
            if (parent[x] == x) {
                return new int[] { x, 0 };
            }
            int[] root = find(parent[x]);
            parity[x] ^= root[1];
            parent[x] = root[0];
            return new int[] { parent[x], parity[x] };
        }

        boolean unite(int a, int b) {
            int[] fa = find(a);
            int[] fb = find(b);
            int ra = fa[0], pa = fa[1];
            int rb = fb[0], pb = fb[1];
            if (ra == rb) {
                return (pa ^ pb) == 1;
            }

            int link = pa ^ pb ^ 1;
            if (size[ra] < size[rb]) {
                parent[ra] = rb;
                parity[ra] = link;
                counts[rb][0] += counts[ra][link];
                counts[rb][1] += counts[ra][link ^ 1];
                size[rb] += size[ra];
            } else {
                parent[rb] = ra;
                parity[rb] = link;
                counts[ra][0] += counts[rb][link];
                counts[ra][1] += counts[rb][link ^ 1];
                size[ra] += size[rb];
            }
            return true;
        }

        int bestSum() {
            int total = 0;
            for (int i = 0; i < parent.length; ++i) {
                if (parent[i] == i) {
                    total += Math.max(counts[i][0], counts[i][1]);
                }
            }
            return total;
        }

        int componentCount() {
            int total = 0;
            for (int i = 0; i < parent.length; ++i) {
                if (parent[i] == i) {
                    ++total;
                }
            }
            return total;
        }
    }

    static int[] parseCsvArray(String text) {
        List<Integer> values = new ArrayList<>();
        for (String token : text.split(",")) {
            if (token.trim().isEmpty()) {
                continue;
            }
            long value = Long.parseLong(token.trim());
            if (value < 0 || value > Integer.MAX_VALUE) {
                throw new RuntimeException("Array value is out of range");
            }
            values.add((int) value);
        }
        int[] result = new int[values.size()];
        for (int i = 0; i < result.length; ++i) {
            result[i] = values.get(i);
        }
        return result;
    }

    static int[] readCsvArray(String path) throws IOException {
        return parseCsvArray(new String(Files.readAllBytes(Paths.get(path))));
    }

    // intervals[i] = { left, right }, sorted by left
    static int[][] buildIntervals(int[] a) {
        if (a.length % 2 != 0) {
            throw new RuntimeException("Array length is odd");
        }
        int n = a.length / 2;
        int[] first = new int[n];
        int[] occurrences = new int[n];
        for (int i = 0; i < n; ++i) {
            first[i] = -1;
        }
        List<int[]> intervals = new ArrayList<>();

        for (int pos = 0; pos < a.length; ++pos) {
            int value = a[pos];
            if (value < 0 || value >= n) {
                throw new RuntimeException("Array values must be in [0,n)");
            }
            ++occurrences[value];
            if (occurrences[value] == 1) {
                first[value] = pos;
            } else if (occurrences[value] == 2) {
                intervals.add(new int[] { first[value], pos });
            } else {
                throw new RuntimeException("A value occurs more than twice");
            }
        }

        for (int count : occurrences) {
            if (count != 2) {
                throw new RuntimeException("A value does not occur exactly twice");
            }
        }

        intervals.sort((x, y) -> Integer.compare(x[0], y[0]));
        return intervals.toArray(new int[0][]);
    }

    static boolean crosses(int[] lhs, int[] rhs) {
        if (lhs[0] < rhs[0]) {
            return lhs[0] < rhs[0] && rhs[0] < lhs[1] && lhs[1] < rhs[1];
        }
        return rhs[0] < lhs[0] && lhs[0] < rhs[1] && rhs[1] < lhs[1];
    }

    static SolveResult solveArray(int[] a) {
        int[][] intervals = buildIntervals(a);
        int n = intervals.length;
        ParityDsu dsu = new ParityDsu(n);
        // encode active intervals as (right << 20) | index, ordered by right then index
        TreeSet<Long> activeByRight = new TreeSet<>();
        long crossings = 0;

        for (int i = 0; i < n; ++i) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            Long e = activeByRight.ceiling((long) (left + 1) << 20);
            while (e != null && (e >> 20) < right) {
                int other = (int) (e & 0xFFFFF);
                if (!dsu.unite(i, other)) {
                    return new SolveResult(false, -1, crossings + 1, 0);
                }
                ++crossings;
                e = activeByRight.higher(e);
            }
            activeByRight.add(((long) right << 20) | i);
        }

        return new SolveResult(true, dsu.bestSum(), crossings, dsu.componentCount());
    }

    static SolveResult bruteForceArray(int[] a) {
        int[][] intervals = buildIntervals(a);
        int n = intervals.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (crosses(intervals[i], intervals[j])) {
                    edges.add(new int[] { i, j });
                }
            }
        }

        int best = -1;
        for (int mask = 0; mask < (1 << n); ++mask) {
            boolean ok = true;
            for (int[] edge : edges) {
                if (((mask >> edge[0]) & 1) == ((mask >> edge[1]) & 1)) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                best = Math.max(best, Integer.bitCount(mask));
            }
        }

        return new SolveResult(best >= 0, best, edges.size(), 0);
    }

    static void validateAllWords(int n, int[] word, int[] counts, int pos) {
        if (pos == 2 * n) {
            SolveResult fast = solveArray(word);
            SolveResult brute = bruteForceArray(word);
            assert fast.bipartite == brute.bipartite;
            if (fast.bipartite) {
                assert fast.answer == brute.answer;
                assert fast.crossings == brute.crossings;
            }
            return;
        }

        for (int value = 0; value < n; ++value) {
            if (counts[value] == 2) {
                continue;
            }
            ++counts[value];
            word[pos] = value;
            validateAllWords(n, word, counts, pos + 1);
            --counts[value];
        }
    }

    static void runCheckpoints() {
        assert solveArray(new int[] { 0, 1, 2, 1, 0, 2 }).answer == 2;
        assert solveArray(new int[] { 0, 0, 1, 1, 2, 2 }).answer == 3;
        assert !solveArray(new int[] { 0, 1, 2, 0, 1, 2 }).bipartite;

        for (int n = 1; n <= 4; ++n) {
            int[] word = new int[2 * n];
            int[] counts = new int[n];
            validateAllWords(n, word, counts, 0);
        }
    }

    public static void main(String[] args) throws IOException {
        String filePath = "resources/documents/1002_input.txt";
        boolean doCheckpoints = true;
        for (String arg : args) {
            if (arg.equals("--skip-checkpoints")) {
                doCheckpoints = false;
            } else if (arg.startsWith("--file=")) {
                filePath = arg.substring("--file=".length());
            } else {
                System.err.println("Unknown argument: " + arg);
                System.exit(1);
            }
        }

        if (doCheckpoints) {
            runCheckpoints();
        }

        int[] values = readCsvArray(filePath);
        SolveResult result = solveArray(values);
        if (!result.bipartite) {
            System.err.println("The interval crossing graph is not bipartite");
            System.exit(2);
        }
        System.out.println(result.answer);
    }
}