// Comprueba lo que afirman los apuntes. Se compila con sanitizers.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "dag_dp.h"
#include "interval_dp.h"
#include "lis.h"
#include "tree_dp.h"

namespace {

// Distancia de edición con la tabla de la semana 7, para compararla con el camino en el DAG.
int edit_table_value(const std::string& a, const std::string& b) {
    std::vector<std::vector<int>> d(a.size() + 1, std::vector<int>(b.size() + 1, 0));
    for (std::size_t i = 0; i <= a.size(); i++) d[i][0] = static_cast<int>(i);
    for (std::size_t j = 0; j <= b.size(); j++) d[0][j] = static_cast<int>(j);
    for (std::size_t i = 1; i <= a.size(); i++) {
        for (std::size_t j = 1; j <= b.size(); j++) {
            d[i][j] = std::min({d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + (a[i - 1] == b[j - 1] ? 0 : 1)});
        }
    }
    return d[a.size()][b.size()];
}

long long knapsack_brute_small(const std::vector<KnapsackObject>& objects, std::size_t capacity) {
    long long best = 0;
    for (unsigned mask = 0; mask < (1u << objects.size()); mask++) {
        std::size_t weight = 0;
        long long value = 0;
        for (std::size_t i = 0; i < objects.size(); i++) {
            if (mask >> i & 1u) {
                weight += objects[i].weight;
                value += objects[i].value;
            }
        }
        if (weight <= capacity) best = std::max(best, value);
    }
    return best;
}

WeightedDag random_dag(std::mt19937& rng, int n) {
    // Etiquetas barajadas: el orden del DAG no coincide con el de los números.
    std::vector<int> label(static_cast<std::size_t>(n));
    std::iota(label.begin(), label.end(), 0);
    std::shuffle(label.begin(), label.end(), rng);
    WeightedDag g(static_cast<std::size_t>(n));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (rng() % 3 == 0) g[label[i]].push_back({label[j], static_cast<long long>(rng() % 21) - 10});
        }
    }
    return g;
}

void test_longest_path() {
    std::mt19937 rng(91);
    for (int round = 0; round < 3000; round++) {
        const int n = 1 + static_cast<int>(rng() % 9);
        const WeightedDag g = random_dag(rng, n);
        const int source = static_cast<int>(rng() % static_cast<unsigned>(n));

        const std::vector<int> order = topological_order(g);
        std::vector<int> position(static_cast<std::size_t>(n));
        for (int t = 0; t < n; t++) position[order[t]] = t;
        for (int u = 0; u < n; u++) {
            for (const Arc& arc : g[u]) assert(position[u] < position[arc.to]);
        }

        std::vector<long long> best(static_cast<std::size_t>(n), 0);
        std::vector<char> seen(static_cast<std::size_t>(n), 0);
        all_paths(g, source, 0, best, seen);
        const LongestPaths r = longest_paths(g, source);
        for (int v = 0; v < n; v++) {
            assert(r.reached[v] == seen[v]);
            if (!seen[v]) continue;
            assert(r.length[v] == best[v]);
            // El camino reconstruido empieza en el origen, usa aristas del grafo y suma ese largo.
            const std::vector<int> path = path_to(r, v);
            assert(path.front() == source && path.back() == v);
            long long total = 0;
            for (std::size_t t = 0; t + 1 < path.size(); t++) {
                long long arc_best = -1000000;
                for (const Arc& arc : g[path[t]]) {
                    if (arc.to == path[t + 1]) arc_best = std::max(arc_best, arc.weight);
                }
                assert(arc_best != -1000000);
                total += arc_best;
            }
            assert(total == best[v]);
        }
    }
}

void test_longest_path_example() {
    WeightedDag g(7);
    g[0] = {{2, 100}, {6, 1}};
    g[1] = {{2, 3}, {3, 5}};
    g[2] = {{4, -1}};
    g[3] = {{4, -4}, {5, 2}};
    g[4] = {{5, 6}};
    const LongestPaths r = longest_paths(g, 1);
    assert(!r.reached[0] && !r.reached[6]);
    assert(r.length[5] == 8);
    assert(path_to(r, 5) == (std::vector<int>{1, 2, 4, 5}));
    assert(longest_from_anywhere(g)[5] > r.length[5]);  // sin -inf, el nodo 0 contamina
    long long total = 0;
    std::vector<int> walk;
    assert(heaviest_arc_walk(g, 1, 5, total, walk));
    assert(total == 7);
}

void test_subproblem_paths() {
    std::mt19937 rng(92);
    for (int round = 0; round < 1000; round++) {
        std::string a(rng() % 7, 'a');
        std::string b(rng() % 7, 'a');
        for (char& c : a) c = static_cast<char>('a' + rng() % 3);
        for (char& c : b) c = static_cast<char>('a' + rng() % 3);
        const WeightedDag g = edit_subproblem_dag(a, b);
        const LongestPaths r = longest_paths(g, edit_node(0, 0, b.size()));
        assert(-r.length[edit_node(a.size(), b.size(), b.size())] == edit_table_value(a, b));
        // Nodos y aristas: (n + 1)(m + 1) casillas, y 3nm + n + m lecturas.
        std::size_t arcs = 0;
        for (const auto& out : g) arcs += out.size();
        assert(g.size() == (a.size() + 1) * (b.size() + 1));
        assert(arcs == 3 * a.size() * b.size() + a.size() + b.size());
    }
    assert(edit_table_value("casa", "cosas") == 2);
    for (int round = 0; round < 500; round++) {
        std::vector<KnapsackObject> objects(rng() % 7);
        for (KnapsackObject& o : objects) o = {1 + rng() % 6, static_cast<long long>(rng() % 20)};
        const std::size_t capacity = rng() % 16;
        assert(knapsack_as_path(objects, capacity) == knapsack_brute_small(objects, capacity));
    }
    assert(knapsack_as_path({{2, 3}, {3, 4}, {4, 5}, {5, 8}}, 9) == 13);
}

void check_lis_answer(const std::vector<int>& a) {
    const std::vector<int> indices = lis_indices(a);
    for (std::size_t t = 0; t + 1 < indices.size(); t++) {
        assert(indices[t] < indices[t + 1]);
        assert(a[indices[t]] < a[indices[t + 1]]);
    }
    assert(indices.size() == lis_length_tails(a));
}

void test_lis() {
    std::mt19937 rng(93);
    for (int round = 0; round < 3000; round++) {
        std::vector<int> a(rng() % 13);
        const unsigned variety = 1 + rng() % 12;
        for (int& x : a) x = static_cast<int>(rng() % variety) - 3;
        const int best = lis_brute(a);
        assert(lis_length_quadratic(a) == best);
        assert(static_cast<int>(lis_length_tails(a)) == best);
        assert(static_cast<int>(non_decreasing_length_tails(a)) == lis_brute(a, false));
        check_lis_answer(a);

        // Es un camino más largo en el DAG con un origen virtual.
        const int n = static_cast<int>(a.size());
        WeightedDag g(a.size() + 1);
        for (int i = 0; i < n; i++) {
            g[n].push_back({i, 1});
            for (int j = i + 1; j < n; j++) {
                if (a[i] < a[j]) g[i].push_back({j, 1});
            }
        }
        const LongestPaths r = longest_paths(g, n);
        long long longest = 0;
        for (int i = 0; i < n; i++) longest = std::max(longest, r.length[i]);
        assert(longest == best);

        // La invariante del arreglo de finales, contra su definición.
        std::vector<int> tails;
        for (int i = 0; i < n; i++) {
            const auto it = std::lower_bound(tails.begin(), tails.end(), a[i]);
            if (it == tails.end()) {
                tails.push_back(a[i]);
            } else {
                *it = a[i];
            }
            assert(std::adjacent_find(tails.begin(), tails.end(), std::greater_equal<int>()) == tails.end());
            for (std::size_t k = 0; k < tails.size(); k++) {
                // Con el prefijo y solo valores menores o iguales que tails[k] hay largo k + 1,
                // y con valores estrictamente menores, no.
                std::vector<int> below;
                std::vector<int> strictly;
                for (int t = 0; t <= i; t++) {
                    if (a[t] <= tails[k]) below.push_back(a[t]);
                    if (a[t] < tails[k]) strictly.push_back(a[t]);
                }
                assert(lis_length_tails(below) >= k + 1);
                assert(lis_length_tails(strictly) < k + 1);
            }
        }
    }
    assert(lis_length_tails({}) == 0);
    assert(lis_indices({}).empty());
    assert(lis_length_tails({2, 2, 2}) == 1);
    assert(non_decreasing_length_tails({2, 2, 2}) == 3);
    assert(lis_length_tails({1, 3, 3, 5}) == 3);
    assert(non_decreasing_length_tails({1, 3, 3, 5}) == 4);
    assert(lis_greedy_take({5, 1, 2, 3}) == 1);
    assert(lis_length_tails({5, 1, 2, 3}) == 3);
    // Los finales no son una subsecuencia: el 1 está después del 3 y del 7.
    assert(final_tails({2, 5, 3, 7, 1}) == (std::vector<int>{1, 3, 7}));
    assert(lis_length_tails({1, 3, 7}) == 3 && lis_length_tails({2, 5, 3, 7, 1}) == 3);
}

void test_matrix_chain() {
    // La pregunta de repaso: 10x30, 30x5, 5x60.
    const std::vector<long long> review = {10, 30, 5, 60};
    const ChainTables t = matrix_chain(review);
    assert(t.cost[0][2] == 4500);
    assert(parenthesize(t.split, 0, 2) == "((A0 A1) A2)");
    assert(chain_brute(review) == 4500);

    std::mt19937 rng(94);
    for (int round = 0; round < 1000; round++) {
        std::vector<long long> d(2 + rng() % 7);
        for (long long& x : d) x = 1 + static_cast<long long>(rng() % 20);
        const long long last = static_cast<long long>(d.size()) - 2;
        const long long value = matrix_chain(d).cost[0][last];
        assert(value == chain_brute(d));
        assert(value == matrix_chain_i_descending(d));
        assert(chain_cheapest_first(d) >= value);
        assert(matrix_chain_naive_order(d).answer <= value);  // los ceros solo pueden bajarlo
        if (d.size() >= 4) assert(matrix_chain_naive_order(d).empty_reads > 0);
    }

    // Hay tantas parentizaciones como dice el número de Catalan: C(n - 1) para n matrices.
    std::vector<long long> catalan = {1};
    for (long long m = 0; m < 19; m++) catalan.push_back(catalan[m] * 2 * (2 * m + 1) / (m + 2));
    for (std::size_t n = 1; n <= 9; n++) {
        assert(static_cast<long long>(all_chain_plans(std::vector<long long>(n + 1, 2), 0, static_cast<int>(n) - 1).size()) == catalan[n - 1]);
    }
    assert(catalan[19] == 1767263190LL);

    // La cuenta de combinaciones: (n³ − n) / 6.
    for (long long n = 1; n <= 30; n++) {
        long long combinations = 0;
        matrix_chain(std::vector<long long>(static_cast<std::size_t>(n) + 1, 2), &combinations);
        assert(combinations == (n * n * n - n) / 6);
    }

    assert(chain_cheapest_first({4, 1, 3, 5}) == 72);
    assert(chain_brute({4, 1, 3, 5}) == 35);
    const std::vector<long long> d = {10, 20, 5, 30, 2};
    assert(matrix_chain_naive_order(d).answer < chain_brute(d));
    // Con una sola matriz no hay nada que multiplicar.
    assert(matrix_chain({3, 4}).cost[0][0] == 0);
    // Las dimensiones grandes piden long long: 2000 x 2000 x 2000 = 8e9.
    assert(matrix_chain({2000, 2000, 2000}).cost[0][1] == 8000000000LL);
}

void test_optimal_bst() {
    std::mt19937 rng(95);
    for (int round = 0; round < 1500; round++) {
        std::vector<long long> f(rng() % 8);
        for (long long& x : f) x = static_cast<long long>(rng() % 15);
        const int n = static_cast<int>(f.size());
        const BstTables t = optimal_bst(f);
        assert(t.cost[0][n] == bst_brute(f));
        std::vector<int> depth(f.size(), 0);
        bst_depths(t.root, 0, n, 1, depth);
        assert(cost_from_depths(f, depth) == t.cost[0][n]);
        assert(bst_most_frequent_root(f, 0, n, 1) >= t.cost[0][n]);
        assert(bst_balanced(f, 0, n, 1) >= t.cost[0][n]);
    }
    const std::vector<long long> example = {2, 1, 3, 4};
    assert(optimal_bst(example).cost[0][4] == 18);
    assert(bst_most_frequent_root(example, 0, 4, 1) == 20);
    assert(bst_balanced(example, 0, 4, 1) == 19);
    assert(optimal_bst({}).cost[0][0] == 0);
    assert(optimal_bst({7}).cost[0][1] == 7);
}

RootedTree random_tree(std::mt19937& rng, int n, int low, int high) {
    RootedTree tree{std::vector<std::vector<int>>(static_cast<std::size_t>(n)), 0, std::vector<long long>(static_cast<std::size_t>(n))};
    std::vector<int> label(static_cast<std::size_t>(n));
    std::iota(label.begin(), label.end(), 0);
    std::shuffle(label.begin(), label.end(), rng);
    tree.root = label[0];
    for (int i = 1; i < n; i++) {
        const int boss = label[rng() % static_cast<unsigned>(i)];
        tree.children[boss].push_back(label[i]);
    }
    for (long long& v : tree.value) v = low + static_cast<long long>(rng() % static_cast<unsigned>(high - low + 1));
    return tree;
}

bool is_independent(const RootedTree& tree, const std::vector<int>& nodes) {
    std::vector<char> inside(tree.value.size(), 0);
    for (int v : nodes) inside[v] = 1;
    for (std::size_t v = 0; v < tree.value.size(); v++) {
        if (!inside[v]) continue;
        for (int c : tree.children[v]) {
            if (inside[c]) return false;
        }
    }
    return true;
}

void test_tree_dp() {
    std::mt19937 rng(96);
    for (int round = 0; round < 4000; round++) {
        const int n = 1 + static_cast<int>(rng() % 13);
        const bool signed_values = round % 2 == 1;
        const RootedTree tree = random_tree(rng, n, signed_values ? -9 : 0, 20);
        const long long best = independent_set_brute(tree);
        assert(independent_set_value(tree) == best);
        assert(best >= 0);  // el conjunto vacío siempre es válido

        const std::vector<int> nodes = independent_set_nodes(tree);
        assert(is_independent(tree, nodes));
        long long total = 0;
        for (int v : nodes) total += tree.value[v];
        assert(total == best);

        // Los greedy y las versiones con error nunca se pasan si no eligen vecinos.
        assert(largest_value_first(tree) <= best);
        assert(forced_children_value(tree) <= best);
        if (!signed_values) assert(alternate_levels(tree) <= best);

        // Cobertura: directa, por fuerza bruta y por el complemento, también con pesos negativos.
        const long long sum = std::accumulate(tree.value.begin(), tree.value.end(), 0LL);
        const long long cover = min_cover_brute(tree);
        assert(min_cover_value(tree) == cover);

        // Los tamaños por orden inverso de BFS, contra un recorrido con pila desde cada nodo.
        const std::vector<int> sizes = subtree_sizes_bfs_order(tree.children, tree.root);
        for (int v = 0; v < n; v++) {
            int count = 0;
            std::vector<int> pending = {v};
            while (!pending.empty()) {
                const int u = pending.back();
                pending.pop_back();
                count++;
                for (int c : tree.children[u]) pending.push_back(c);
            }
            assert(sizes[v] == count);
        }
        assert(cover == sum - best);
    }

    // Los ejemplos del texto.
    const RootedTree chain{{{1}, {2}, {3}, {}}, 0, {10, 1, 1, 10}};
    assert(independent_set_value(chain) == 20);
    assert(forced_children_value(chain) == 11);
    assert(alternate_levels(chain) == 11);
    const RootedTree company{{{1, 2}, {3, 4}, {5}, {}, {}, {6, 7}, {}, {}}, 0, {4, 9, 6, 5, 5, 8, 3, 4}};
    assert(independent_set_value(company) > alternate_levels(company));
    assert(independent_set_value(company) > largest_value_first(company));
    assert(independent_set_value(company) > forced_children_value(company));
    assert(!is_independent(company, choose_each_node_alone(company)));
    const RootedTree negative{{{1, 2}, {}, {}}, 0, {-4, -1, -2}};
    assert(independent_set_value(negative) == 0);
    assert(independent_set_nodes(negative).empty());

    // Un árbol de un solo nodo, con valor positivo y negativo.
    assert(independent_set_value(RootedTree{{{}}, 0, {7}}) == 7);
    assert(independent_set_value(RootedTree{{{}}, 0, {-7}}) == 0);
    assert(min_cover_value(RootedTree{{{}}, 0, {7}}) == 0);
    assert(min_cover_value(RootedTree{{{}}, 0, {-7}}) == -7);  // una sola opción negativa sí conviene

    // Una cadena larga sin recursión: el orden inverso de BFS no usa la pila.
    const int n = 200000;
    std::vector<std::vector<int>> children(static_cast<std::size_t>(n));
    for (int v = 0; v + 1 < n; v++) children[v].push_back(v + 1);
    const std::vector<int> sizes = subtree_sizes_bfs_order(children, 0);
    assert(sizes[0] == n && sizes[n - 1] == 1);
}

}  // namespace

int main() {
    test_longest_path();
    test_longest_path_example();
    test_subproblem_paths();
    test_lis();
    test_matrix_chain();
    test_optimal_bst();
    test_tree_dp();
    std::cout << "Todas las pruebas de la semana 9 pasaron.\n";
}