Submission #624175

#	Time	Username	Problem	Language	Result	Execution time	Memory
624175		jophyyjh	Packing Biscuits (IOI20_biscuits)	C++14	77 / 100	1085 ms	1356 KiB

biscuits

/**
 * Binary. Hmm, interesting. I started with [S2], which I solved with recursion in
 * O(kq). The basic idea is to treat two 2^i biscuits in the bag as one 2^(i+1).
 * 
 * A few greedy observations:
 * (1)  Given x, can we determine if it's possible? Well, we can simply iterate i
 *      from large to small. If the additional tastiness x we still need for a
 *      certain bag satisfies x >= 2^i, put a biscuit 2^i in the bag if there's one.
 * (2)  Biscuits of the same type can be distributed as evenly as possible, i.e.
 *      there is an optimal partition s.t. for every i
 *              |#2^i_biscuits_in_bag_1 - #2^i_biscuits_in_big_2| <= 1.
 * (3)  Unlike (1), (2), we consider from small to large. If x is odd, each bag needs
 *      at least 1 2^0 biscuit. After that, every 2 2^O biscuits can be grouped to
 *      form 1 2^1 biscuit, so we can add this num to the original num of 2^1
 *      biscuits. Well, let's write this recursively:
 *           def find():
 *               total = 0
 *               if #2^0 >= x:
 *                   add floor((#2^0 - x) / 2) to #2^1 and recurse downdwards
 *               add floor(#2^0 / 2) to 2^1 and recurse downwards
 *               ...
 * 
 * Can we AC this problem with (3)? I guess that the num of configurations given to
 * find() isn't too many, so we can optimize it with memoization. Indeed, we can
 * prove that in each level of find(), the num. of unique calls the next level of
 * find() is bounded by x. This is because x >= x/2 + x/4 + x/8 + x/16 + .... [S1-3]
 * are solved.
 * 
 * In impl1, the function search(p, first) doesn't decrease as first increases.
 * Furthermore, if search(p, w) and search(p, z) are both called, |w-z| <= x+2. (For
 * each p, the val first only varies in a range with len <= x.) We can binary search
 * for the largest / smallest value for first that attains a certain search(p, ..).
 * I'm not sure about the actual num. of distinct values of search(p, ..), but I
 * guess the num is <= 10. Let's give it a go
 * 
 * Time Complexity: O(kq * log(x))
 * Implementation 1.6       (Full solution (?!), greedy + binary search + maths)
*/

#include <bits/stdc++.h>
#include "biscuits.h"

typedef long long	ll;

const ll INF = 0x3f3f3f3f3f3f3f3f;

ll wrap(int p, ll first);       // wraper function for search()
ll search(int p, ll first);


ll x;
std::vector<ll> a;

std::vector<ll> upper, lower;
std::vector<std::map<ll, ll>> cache1;
std::vector<std::map<ll, ll, std::greater<ll>>> cache2;

// std::vector<std::vector<ll>> debug;

ll wrap(int p, ll first) {
    auto v1 = cache1[p].lower_bound(first);
    auto v2 = cache2[p].lower_bound(first);
    if (v1 != cache1[p].end() && v2 != cache2[p].end()) {
        if (v1->second == v2->second)
            return v1->second;
    }
    ll val = search(p, first);
    ll high = first, low = first;
    for (ll step = x / 2 + 1; step >= 1; step /= 2) {
        while (high + step <= upper[p] && search(p, high + step) == val)
            high += step;
        while (low - step >= lower[p] && search(p, low - step) == val)
            low -= step;
    }
    cache1[p][high] = cache2[p][low] = val;
    // debug[p].push_back(val);
    return val;
}

ll search(int p, ll first) {
    int k = a.size();
    if (p == k - 1)
        return first / x + 1;
    ll total = wrap(p + 1, a[p + 1] + first / 2);
    if (first >= x)
        total += wrap(p + 1, a[p + 1] + (first - x) / 2);
    return total;
}

ll count_tastiness(ll _x, std::vector<ll> _a) {
    x = _x, a = _a;
    int k = _a.size();
    cache1.assign(k, std::map<ll, ll>());
    cache2.assign(k, std::map<ll, ll, std::greater<ll>>());
    upper.resize(k);
    lower.resize(k);
    for (ll i = 0, current = 0; i < k; i++) {
        current += a[i];
        upper[i] = current, lower[i] = std::max(upper[i] - (x + 2), ll(0));
        current /= 2;
    }
    // debug.assign(k, std::vector<ll>());
    return search(0, a[0]);
    // for (int i = 0; i < k; i++) {
    //     std::cerr << "[debug] " << i << ": ";
    //     for (int v : debug[i])
    //         std::cerr << v << ' ';
    //     std::cerr << std::endl;
    // }
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 35 / 35
• Subtask 5: 0 / 23