rec.cc

/*
 * $File: c.cc
 * $Date: Fri Jul 10 15:00:27 2015 +0800
 * $Author: Xiaoyu Liu <i[at]vuryleo[dot]com>
 */

#include <iostream>
#include <memory>
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>
#include <numeric>

using namespace std;

class rectangle
{
public:
    int id, width, height;
    void print(int left = 0, int bottom = 0){
        cout << "id: " << id << " l: " << left << " b: " << bottom << " w " << width << " h: " << height << endl;
    };
};

class layout
{
public:
    virtual void print(int = 0, int = 0) = 0;
    virtual int getHeight() = 0;
    virtual int getWidth() = 0;
};

class singleLayout final : public layout
{
public:
    rectangle rec;
    singleLayout(rectangle s_rec) : rec(s_rec) { };
    void print(int left = 0, int bottom = 0) override {
        rec.print(left, bottom);
    };
    int getHeight() override { return rec.height; };
    int getWidth() override { return rec.width; };
};

class multiLayout : public layout
{
public:
    multiLayout(vector<shared_ptr<layout>> s_layouts) : layouts{s_layouts} {};
    vector<shared_ptr<layout>> layouts;
};

class stackLayout final : public multiLayout
{
public:
    stackLayout(vector<shared_ptr<layout>> s_layouts) : multiLayout(s_layouts) {};
    void print(int left = 0, int bottom = 0) override {
        cout << "stackly" << endl;
        for (auto & i : layouts)
        {
            i -> print(left, bottom);
            bottom += i -> getHeight();
        }
    };
    int getHeight() override {
        return accumulate(layouts.begin(), layouts.end(), 0,
                [](const int & a, shared_ptr<layout> b){
                    return a + b -> getHeight();
                });
    };
    int getWidth() override {
        return layouts.front() -> getWidth();
    };
};

class parallelLayout final : public multiLayout
{
public:
    parallelLayout(vector<shared_ptr<layout>> s_layouts) : multiLayout(s_layouts) {};
    void print(int left = 0, int bottom = 0) override {
        cout << "parallelly" << endl;
        for (auto & i : layouts)
        {
            i -> print(left, bottom);
            left += i -> getWidth();
        }
    };
    int getHeight() override {
        return accumulate(layouts.begin(), layouts.end(), 0,
                [](const int & a, shared_ptr<layout> b){
                    return max(a, b -> getHeight());
                });
    };
    int getWidth() override {
        return accumulate(layouts.begin(), layouts.end(), 0,
                [](const int & a, shared_ptr<layout> b){
                    return a + b -> getWidth();
                });
    };
};

class windmillLayout final: public multiLayout
{
public:
    windmillLayout(vector<shared_ptr<layout>> s_layouts) : multiLayout(s_layouts) {};
    void print(int left = 0, int bottom = 0) override {
        cout << "windmillly" << endl;
        layouts[0] -> print(left, bottom);
        layouts[1] -> print(left + layouts[0] -> getWidth(), bottom);
        layouts[2] -> print(left, bottom + layouts[0] -> getHeight());
        int right = layouts[1] -> getHeight();
        if (layouts[4])
            right = max(right, layouts[0] -> getHeight() + layouts[4] -> getHeight());
        layouts[3] -> print(left + layouts[2] -> getWidth(), right);
        if (layouts[4])
            layouts[4] -> print(left + layouts[2] -> getWidth(), bottom + layouts[0] -> getWidth());
    };
    int getHeight() override {
        int left = layouts[0] -> getHeight() + layouts[2] -> getHeight();
        int right = layouts[1] -> getHeight() + layouts[3] -> getHeight();
        if (layouts[4])
        {
            right = max(right, layouts[0] -> getHeight() +
                    layouts[4] -> getHeight() + layouts[3] -> getHeight());
        }
        return max(left, right);
    };
    int getWidth() override {
        return layouts[0] -> getWidth() + layouts[1] -> getWidth();
    }
};

class complexLayout final: public multiLayout
{
public:
    complexLayout(vector<shared_ptr<layout>> s_layouts) : multiLayout(s_layouts) {};
    void print(int left = 0, int bottom = 0) override {
        cout << "complex" << endl;
        for(auto & i: layouts)
            i -> print(left, bottom);
    }
    int getHeight() override {
        return layouts[0] -> getHeight();
    }
    int getWidth() override {
        return layouts[0] -> getWidth();
    }
};

auto trisection(int l, int h, function<int(int)> f)
{
    while(l < h - 1)
    {
        int third = (h - l - 1) / 3;
        int ml = l + third, mh = h - 1 - third;
        if (f(ml) > f(mh))
            l = ml + 1;
        else
            h = mh;
    }
    return l;
}

map<pair<vector<int>, int>, shared_ptr<layout>> cache;

auto arrange(vector<int> ids, int left, int bottom, int width, function<int(int, int)> getHeight)
{
    {
        auto result = cache.find(make_pair(ids, width));
        if( result != cache.end())
            return result -> second;
    }
    assert(ids.size() > 0);
    if (ids.size() == 1) // only one
    {
        auto s = rectangle{ids.front(), width, getHeight(ids.front(), width)};
        return shared_ptr<layout>(new singleLayout{s});
    }
    else {
        shared_ptr<layout> stackly, parallelly, windmillly;
        // stack some at the bottom
        {
            for (auto pos = ids.begin() + 1; pos < ids.end(); pos ++)
            {
                vector<int> bottoms(ids.begin(), pos);
                auto bottomLayout = arrange(vector<int>(ids.begin(), pos),
                                            left,
                                            bottom,
                                            width,
                                            getHeight);
                auto topLayout = arrange(vector<int>(pos, ids.end()),
                                         left,
                                         bottom + bottomLayout -> getHeight(),
                                         width,
                                         getHeight);
                auto result = shared_ptr<layout>(new stackLayout(vector<shared_ptr<layout>>{bottomLayout, topLayout}));
                if (!stackly)
                    stackly = result;
                else if (result -> getHeight() < stackly -> getHeight())
                    stackly = result;
            }
        }
        // parallel some at the left
        {
            for (auto pos = ids.begin() + 1; pos < ids.end(); pos ++)
            {
                // use trisection
                int l = trisection(1, width, [&](auto w) {
                        return max(arrange(vector<int>(ids.begin(), pos),
                                           left,
                                           bottom,
                                           w,
                                           getHeight) -> getHeight(),
                                   arrange(vector<int>(pos, ids.end()),
                                           left + w,
                                           bottom,
                                           width - w,
                                           getHeight) -> getHeight());
                    });
                auto leftLayout = arrange(vector<int>(ids.begin(), pos),
                                          left,
                                          bottom,
                                          l,
                                          getHeight);
                auto rightLayout = arrange(vector<int>(pos, ids.end()),
                                           left + l,
                                           bottom,
                                           width - l,
                                           getHeight);
                auto result = shared_ptr<layout>(new parallelLayout(vector<shared_ptr<layout>>{leftLayout, rightLayout}));
                if (!parallelly)
                    parallelly = result;
                else if (result -> getHeight() < parallelly -> getHeight())
                    parallelly = result;
            }
        }
        // a windmill
        if (ids.size() > 3)
        {
            // generate a integer partition of five parts
            // select 4 interspace between the numbers or the tail as partition flags
            // e.g) 0 1 2 3
            //   -> 0 | 1 | 2 | 3 |
            vector<bool> flag(4, true);
            flag.resize(ids.size());
            do
            {
                vector<vector<int>> parts(5);
                parts[0].push_back(ids.front());
                vector<vector<int>>::size_type currentPart = 0;
                vector<int>::size_type currentId = 1;
                for (vector<bool>::size_type pos = 0; pos < flag.size(); pos ++)
                {
                    if (flag[pos]) // switch to next part
                        currentPart ++;
                    if (currentId < ids.size())
                        parts[currentPart].emplace_back(ids[currentId ++]);
                }

                // the five parts will be arranged as
                // +--------+------------------+
                // |        |      part 3      |
                // | part 2 +------------------+
                // |        | part 4 |         |
                // +--------+--------+  part 1 |
                // |      part 0     |         |
                // +-----------------+---------+
                //  while part 4 can be empty
                auto gen = [&](auto p) {
                    vector<shared_ptr<layout>> partLayouts(5);
                    partLayouts[0] = arrange(parts[0], left, bottom, p, getHeight);
                    partLayouts[1] = arrange(parts[1], left + p, bottom, width - p, getHeight);

                    // use trisection to search for the boundary of part 2 & 3
                    auto f = [&](auto w)
                    {
                        auto result = max(arrange(parts[2],
                                                  left,
                                                  bottom + partLayouts[0] -> getHeight(),
                                                  w,
                                                  getHeight) -> getHeight()
                                              + partLayouts[0] -> getHeight(),
                                          arrange(parts[3],
                                                  left + w,
                                                  bottom + partLayouts[1] -> getHeight(),
                                                  width - w,
                                                  getHeight) -> getHeight()
                                              + partLayouts[1] -> getHeight()
                                          );
                        if (parts[4].empty())
                            return result;
                        else
                            return max(result, arrange(parts[4],
                                                       left + w,
                                                       bottom + partLayouts[0] -> getHeight(),
                                                       p - w,
                                                       getHeight) -> getHeight()
                                                    + partLayouts[0] -> getHeight());
                    };
                    int l = trisection(1, p, f);
                    partLayouts[2] = arrange(parts[2],
                                             left,
                                             bottom + partLayouts[0] -> getHeight(),
                                             l,
                                             getHeight);
                    if (parts[4].empty())
                    {
                        partLayouts[3] = arrange(parts[3],
                                                 left + l,
                                                 bottom + partLayouts[1] -> getHeight(),
                                                 width - p,
                                                 getHeight);
                    }
                    else
                    {
                        partLayouts[4] = arrange(parts[4],
                                                 left + l,
                                                 bottom + partLayouts[0] -> getHeight(),
                                                 p - l,
                                                 getHeight);
                        partLayouts[3] = arrange(parts[3],
                                                 left + l,
                                                 bottom + max(partLayouts[1] -> getHeight(),
                                                              partLayouts[0] -> getHeight() + partLayouts[4] -> getHeight()),
                                                 width - l,
                                                 getHeight);
                    }
                    auto s = new windmillLayout(partLayouts);
                    return shared_ptr<layout>(s);
                };

                //// trisection the boundary of part 0 & 1
                auto l = trisection(1, width, [&](auto w) {
                    return gen(w) -> getHeight();
                });
                auto result = gen(l);
                if (!windmillly)
                    windmillly = result;
                else if (result -> getHeight() < windmillly -> getHeight())
                    windmillly = result;

                // enumerate the boundary of part 0 & 1
                //For (int p = 1; p < width; p ++)
                //{
                //    auto result = gen(p);
                //    //cout << p << ' ' << result -> getHeight() << endl;
                //    if (!windmillly)
                //        windmillly = result;
                //    else if (result -> getHeight() < windmillly -> getHeight())
                //        windmillly = result;
                //}
            } while (prev_permutation(flag.begin(), flag.end()));
        }
        vector<shared_ptr<layout>> results = {stackly, parallelly};
        if (windmillly)
            results.emplace_back(windmillly);
        auto result = * max_element(results.begin(), results.end(), [](auto a, auto b) {
                    return a -> getHeight() > b -> getHeight();
                });
        cache[make_pair(ids, width)] = result;
        return result;
    }
};

int main()
{
    int n, w;
    cin >> n >> w;
    vector<vector<int>> coms(n);
    for (auto & r : coms)
    {
        r.resize(w);
        for (auto & e : r)
            cin >> e;
        r.emplace(r.begin(), 0);
    }
    vector<int> ids(n);
    shared_ptr<layout> best;
    iota(ids.begin(), ids.end(), 0);
    do
    {
        auto result = arrange(ids, 0, 0, w, [&coms](int id, int width) {
                    return coms[id][width];
                });
        if (!best)
            best = result;
        else if(result -> getHeight() < best -> getHeight())
            best = result;
    } while(next_permutation(ids.begin(), ids.end()));
    cout << best -> getHeight() << endl;
    best -> print();
    return 0;
}

/**
 * vim: syntax=cpp1z foldmethod=marker
 */

example input:
4 5
5 4 3 2 2
4 3 3 2 2
3 3 2 2 2
2 2 2 2 1