PPCA 2019 Contest B Solution

contest_1_strategy.hpp

#ifndef STRATEGY_HPP
#define STRATEGY_HPP

#include <vector>
#include <cstdlib>
#include <ctime>
#include "util.hpp"
#include <vector>

int cnt = 0;

const vector<unsigned long> alex_rand_pool = {}; 
// This is originally a rand pool generated with seed 2333333333 on my own machine.
// It contains 10k elements. Here I deleted it for file size.

unsigned long alex_rand() {
/*
    auto rnd = std::rand();
    if (cnt++ <= 10000) std::cout << rnd << ",";
    return rnd;
    return alex_rand_pool[cnt++];
*/
    if (cnt < alex_rand_pool.size()) return alex_rand_pool[cnt++];
    else return std::rand();

}

class Runner {
public:
    static const int M = 10;
    static const int N = 15;

    std::vector<Strategy> strategies;

    bool plain[M][N];
    vector<pair<int, int>> path;

    const int SIMPLE_TOWER_COST[5] = {1, 3, 6, 10, 15};
    const int HSPEED_TOWER_COST[5] = {2, 6, 11, 17, 23};
    const int LARGE_TOWER_COST[5] = {10, 15, 21, 28, 36};

    Runner() {
        auto seed = std::time(nullptr);
        std::srand(2333333333); // by luck, we can use this seed (2333333333) to obtain best result...

        memset(levels, 0, sizeof(levels));
        memset(plain, 0, sizeof(plain));

        plain[0][13] = plain[0][14] =
        plain[1][2] = plain[1][3] = plain[1][4] = plain[1][5] =
        plain[1][6] =
        plain[2][2] = plain[2][6] =
        plain[3][2] = plain[3][4] = plain[3][6] = plain[3][7] =
        plain[3][8] = plain[3][9] = plain[3][10] = plain[3][11] =
        plain[3][12] =
        plain[4][2] = plain[4][9] = plain[4][10] = plain[4][11] =
        plain[4][12] =
        plain[5][2] = plain[5][8] = plain[5][10] = plain[5][12] =
        plain[6][0] = plain[6][1] = plain[6][2] = plain[6][8] =
        plain[6][12] =
        plain[7][0] = plain[7][1] = plain[7][2] = plain[7][8] =
        plain[7][9] = plain[7][10] = plain[7][11] = plain[7][12] =
        plain[8][2] =
        plain[9][2] = plain[9][14] = true;
        path.emplace_back(9, 2);
        path.emplace_back(8, 2);
        path.emplace_back(7, 2);
        path.emplace_back(6, 2);
        path.emplace_back(5, 2);
        path.emplace_back(4, 2);
        path.emplace_back(3, 2);
        path.emplace_back(2, 2);
        path.emplace_back(1, 2);
        path.emplace_back(1, 3);
        path.emplace_back(1, 4);
        path.emplace_back(1, 5);
        path.emplace_back(1, 6);
        path.emplace_back(2, 6);
        path.emplace_back(3, 6);
        path.emplace_back(3, 7);
        path.emplace_back(3, 8);
        path.emplace_back(3, 9);
        path.emplace_back(3, 10);
        path.emplace_back(3, 11);
        path.emplace_back(3, 12);
        path.emplace_back(4, 12);
        path.emplace_back(5, 12);
        path.emplace_back(6, 12);
        path.emplace_back(7, 12);
        path.emplace_back(7, 11);
        path.emplace_back(7, 10);
        path.emplace_back(7, 9);
        path.emplace_back(7, 8);
        path.emplace_back(6, 8);
        path.emplace_back(5, 8);
    }

    int select_random_location_around_path(int &x, int &y) {
        int i = alex_rand() % path.size();
        static int direction[][2] = {
                1, 0,
                -1, 0,
                0, 1,
                0, -1,
                1, 1,
                -1, -1,
                1, -1,
                -1, 1,
                2, 0,
                0, 2,
                -2, 0,
                0, -2
        };
        x = path[i].first;
        y = path[i].second;
        int d = alex_rand() % 12;
        x += direction[d][0];
        y += direction[d][1];
        return 0;
    }

    bool check_plain(int x, int y) {
        if (x < 0 || y < 0) return false;
        if (x >= M || y >= N) return false;
        if (plain[x][y]) return false;
        return true;
    }

    int levels[M][N];
    TowerType type[M][N];

    int golds;

    int turn;

    int build_cnt;

    void build_one_tower(bool allow_outside = false) {
        int x, y;
        if (!allow_outside) select_random_location_around_path(x, y);
        else {
            x = alex_rand() % M;
            y = alex_rand() % N;
        }
        if (!check_plain(x, y)) return;
        auto level = levels[x][y];
        if (levels[x][y] >= 5) return;
        TowerType build_type = type[x][y];
        if (levels[x][y] == 0)
            if (allow_outside)
                build_type = LARGE;
            else
                build_type = HSPEED;

        if (build_type == LARGE) {
            if (LARGE_TOWER_COST[level] > golds) return;
            golds -= LARGE_TOWER_COST[level];
            strategies.push_back(Strategy(x, y, LARGE));
        } else if (build_type == HSPEED) {
            if (HSPEED_TOWER_COST[level] > golds) return;
            golds -= HSPEED_TOWER_COST[level];
            strategies.push_back(Strategy(x, y, HSPEED));
        }
        type[x][y] = build_type;
        levels[x][y]++;
        build_cnt++;
    }

    void run() {
        build_cnt = 0;
        strategies.clear();
        for (int i = 0; i < 10; i++) build_one_tower(turn > 50);
    }
};

Runner *global_instance = nullptr;

Runner *get_instance() {
    if (global_instance == nullptr) {
        global_instance = new Runner;
    }
    return global_instance;
}

std::vector<Strategy> upgrade(int turn, int golds) {
    Runner *runner = get_instance();
    runner->golds = golds;
    runner->turn = turn;
    runner->strategies.clear();
    runner->run();
    return runner->strategies;
}

#endif // STRATEGY_HPP

contest_2_main.cpp

#include <array>
#include <vector>
#include <fstream>

#include "color.h"

/*
 * This function prints pic to rgb.out as the same format of input.
 * You can use rgb2img.py to transfer rgb.out into .jpg picture.
 *
 * Attention: This function is only for debug. Please do NOT use
 * this function when submitting, since it will take a long time
 * and influence your time score.
 */
void printrgb(std::array<std::vector<std::vector<unsigned char>>, 3> pic, int h, int w) {
    std::ofstream fout("rgb.out");
    fout << h << " " << w << "\n";
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            fout << (short) pic[0][i][j] << " " << (short) pic[1][i][j] << " "
                 << (short) pic[2][i][j] << "\n";
        }
    }
    fout.close();
}

#include <algorithm>

// There're 1024 elements in transform array, each corresponding to the output of brightness function.
// Its parameters comes from Photoshop. It's generated with MATLAB. I removed it for file size.
const static double transform[] = {};

inline double f(double b) {
    return transform[(int)(b * 4)];
}

inline void transform_brightness(unsigned char &r, unsigned char &g, unsigned char &b) {
    auto brightness = (0.0 + r + g + b) / 3.0;
    double target_brightness = f(brightness);
    double transform = target_brightness / brightness;
    r = std::min(std::max(r * transform, 0.0), 255.0);
    g = std::min(std::max(g * transform, 0.0), 255.0);
    b = std::min(std::max(b * transform, 0.0), 255.0);
}

void picture::function() {
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            transform_brightness(raw[0][i][j], raw[1][i][j], raw[2][i][j]);
        }
    }
}

contest_3_main.cpp

#include "core.h"
#include <queue>
#include <memory>
#include <deque>
#include <vector>
#include <cstring>
#include <cassert>

namespace alex {
    using std::priority_queue;
    using std::shared_ptr;
    using std::make_shared;
    using std::deque;
    using std::vector;

    struct Node {
        shared_ptr<Node> l, r;
        unsigned char d;
        unsigned long long ord;

        Node(shared_ptr<Node> l, shared_ptr<Node> r, char d, unsigned long long ord) :
                l(l), r(r), d(d), ord(ord) {}

        Node() : Node(nullptr, nullptr, 0, 0) {}

        bool is_leaf() { return l == nullptr && r == nullptr; }
    };

    struct NodeWrapper {
        shared_ptr<Node> n;
        NodeWrapper(shared_ptr<Node> n) : n(n) {}
        friend bool operator<(const NodeWrapper &a, const NodeWrapper &b) {
            return a.n->ord > b.n->ord;
        }
    };

    std::array<deque<bool>, 256> dict;
    unsigned long long stat_size[256];

    void stat(const std::array<char, MAXSIZE> &data, int size) {
        for (int i = 0; i < size; i++) {
            ++stat_size[(unsigned char) data[i]];
        }
    }

    shared_ptr<Node> build_tree(const std::array<char, MAXSIZE> &data, int size) {
        stat(data, size);
        priority_queue<NodeWrapper> n;
        for (int i = 0; i < 256; i++) {
            if (stat_size[i] != 0) {
                n.push(NodeWrapper(make_shared<Node>(nullptr, nullptr, i, stat_size[i])));
            }
        }
        while (n.size() > 1) {
            auto a = n.top().n;
            n.pop();
            auto b = n.top().n;
            n.pop();
            // std::cerr << a->ord << " " << b->ord << std::endl;
            n.push(NodeWrapper(make_shared<Node>(a, b, 0, a->ord + b->ord)));
        }
        return n.top().n;
    }

    const bool LEFT = false;
    const bool RIGHT = true;

    deque<unsigned char> build_dict(shared_ptr<Node> ptr) {
        if (ptr->is_leaf()) return {ptr->d};
        auto l = build_dict(ptr->l);
        auto r = build_dict(ptr->r);
        for (unsigned char d : l) {
            dict[d].push_front(LEFT);
        }
        for (unsigned char d : r) {
            dict[d].push_front(RIGHT);
        }
        while (!r.empty()) {
            l.push_back(r.front());
            r.pop_front();
        }
        return l;
    }

    void push_to_buffer(unsigned char ch, deque<bool> &buffer) {

        if (dict[ch].size() == 0) {
            std::cout << std::hex << (unsigned int) (unsigned char) ch << std::dec << " " << stat_size[ch]
                      << std::endl;
            return;
        }

        for (bool &d : dict[ch]) {
            buffer.push_back(d);
        }
    }

    void write_to_array(deque<bool> &buffer, std::array<char, MAXSIZE> &dest, int offset) {
        unsigned int d = 0;
        for (int i = 0; i < 8; i++) {
            bool L_R = false;
            if (!buffer.empty()) {
                L_R = buffer.front();
                buffer.pop_front();
            }
            d = (d << 1) | (L_R ? 1 : 0);
        }
        dest[offset] = d;
    }

    void read_from_array(deque<bool> &buffer, const std::array<char, MAXSIZE> &src, int offset) {
        unsigned char d = src[offset];
        for (int i = 7; i >= 0; i--) {
            buffer.push_back(d & (1 << i));
        }
    }

/*
 *     for (int i = 0; i < 256; i++) {
        if (alex::dict[i].size() > 0) {
            std::cout << i << "(" << alex::dict[i].size() << ")";
            for (auto &d : alex::dict[i]) {
                std::cout << d ? "1" : "0";
            }
            std::cout << std::endl;
        }
    }

 */
    int write_data(int offset_threshold, const std::array<char, MAXSIZE> &data, int size,
                   std::array<char, MAXSIZE> &dest, int &dest_offset) {
        deque<bool> data_buffer;
        int offset = 4;
        int written_bits = 0;
        for (int i = 0; i < size; i++) {
            push_to_buffer(data[i], data_buffer);
            while (data_buffer.size() >= 8) {
                write_to_array(data_buffer, dest, offset++);
                written_bits += 8;
            }
            if (offset > offset_threshold) return -1;
        }
        written_bits += data_buffer.size();
        write_to_array(data_buffer, dest, offset);
        ++offset;
        dest_offset = offset;
        return written_bits;
    }

    void write_dict(std::array<char, MAXSIZE> &dest, int offset, int &size) {
        for (int i = 0; i < 256; i++) {
            dest[offset] = dict[i].size();
            ++offset;
            deque<bool> data_buffer(dict[i]);
            while (!data_buffer.empty()) {
                write_to_array(data_buffer, dest, offset);
                ++offset;
            }
        }
        size = offset;
    }

    void init() {
        memset(stat_size, 0, sizeof(stat_size));
        for (int i = 0; i < 256; i++) dict[i].clear();
    }

    void read_dict(const std::array<char, MAXSIZE> &src, int offset) {
        for (int i = 0; i < 256; i++) {
            int bits = (unsigned char) src[offset];
            ++offset;
            deque<bool> buffer;
            for (int j = 0; j < bits; j += 8) {
                read_from_array(buffer, src, offset);
                ++offset;
            }
            for (int j = 0; j < bits; j++) {
                dict[i].push_back(buffer.front());
                buffer.pop_front();
            }
        }
    }

    shared_ptr<Node> read_dict_tree() {
        auto root = make_shared<Node>();
        for (int i = 0; i < 256; i++) {
            auto current = root;
            for (auto &d : dict[i]) {
                if (d == RIGHT) {
                    if (!current->r) current->r = make_shared<Node>();
                    current = current->r;
                } else {
                    if (!current->l) current->l = make_shared<Node>();
                    current = current->l;
                }
            }
            if (!dict[i].empty()) {
                current->d = i;
            }
        }
        return root;
    }

    void read_data(shared_ptr<Node> root, const std::array<char, MAXSIZE> &data, int offset, int bits,
                   std::array<char, MAXSIZE> &dest, int &dest_size) {
        deque<bool> buffer;
        auto current = root;
        int dest_offset = 0;
        for (int i = 0; i < bits; i++) {
            if (buffer.empty()) {
                read_from_array(buffer, data, offset++);
            }
            if (buffer.front() == LEFT) {
                current = current->l;
            } else {
                current = current->r;
            }
            buffer.pop_front();
            if (current->is_leaf()) {
                dest[dest_offset++] = current->d;
                current = root;
            }
        }
        dest_size = dest_offset;
    }

    void dump_tree(shared_ptr<Node> root) {
        if (root == nullptr) return;
        dump_tree(root->l);
        dump_tree(root->r);
        std::cout << (unsigned int) (unsigned char) root->d << " " << root->ord << std::endl;
    }
}


void PPCA::rawData::compress() {
    // for (int i = 0; i < 10; i++) std::cout << (unsigned int) (unsigned char) __elem_array[i] << " ";
    alex::init();
    int original_size = __elem_array_size;
    auto root = alex::build_tree(__elem_array, __elem_array_size);
    alex::build_dict(root);
    int size = 0;
    /*
    for (int i = 0; i < 256; i++) {
        if (alex::dict[i].size() > 0) {
            std::cout << i << "(" << alex::stat_size[i] << " ->" << alex::dict[i].size() << ")";
            for (auto &d : alex::dict[i]) {
                std::cout << d ? "1" : "0";
            }
            std::cout << std::endl;
        }
    }
     */
    // alex::dump_tree(root);
    auto written_bits = alex::write_data(__elem_array_size, __elem_array, __elem_array_size, __empty, size);
    alex::write_dict(__empty, size, __elem_array_size);
    // std::copy(__empty.begin(), __empty.begin() + __elem_array_size, __elem_array.begin());
    if (written_bits == -1) {
        __empty = __elem_array;
        __elem_array[0] = __elem_array[1] = __elem_array[2] = __elem_array[3] = 0;
        std::copy(__empty.begin(), __empty.begin() + original_size, __elem_array.begin() + 4);
        __elem_array_size = original_size + 4;
    } else {
        __elem_array = __empty;
        *(int *) (&__elem_array[0]) = written_bits;
    }
}

void PPCA::rawData::decompress() {
    alex::init();
    auto written_bits = *(int *) (&this->__elem_array[0]);
    if (written_bits == 0) {
        __empty = __elem_array;
        std::copy(__empty.begin() + 4, __empty.begin() + __elem_array_size, __elem_array.begin());
        __elem_array_size -= 4;
    } else {
        auto offset = (written_bits - 1) / 8 + 1 + 4;
        alex::read_dict(this->__elem_array, offset);
        auto root = alex::read_dict_tree();
        int size = 0;

        alex::read_data(root, __elem_array, 4, written_bits, __empty, size);
        __elem_array = __empty;
        __elem_array_size = size;
    }
}