fork(7) download
copy 
  1. #include <iostream>
  2. #include <random>
  3. #include <algorithm>
  4. #include <numeric>
  5. #include <vector>
  6. #include <chrono>
  7. #include <cstdlib>
  8. #include <iomanip>
  9. #include <iterator>
  10. #include <functional>
  11.  
  12. enum
  13. {
  14.     kDPLimit = 5000000000, // 5*10^9, dynamic programming
  15.     kHSLimit = 54,         // Horowitz-Sahni
  16.     kKKLimit = 4,          // Karmarkar-Karp
  17. };
  18.  
  19. using namespace std;
  20. using i64 = int_fast64_t;
  21. using u64 = uint_fast64_t;
  22.  
  23. class Log
  24. {
  25. public:
  26.     Log(size_t size, i64 max_value, i64 sum, u64 seed, ostream& os)
  27.     : os_(os)
  28.     , start_(chrono::steady_clock::now())
  29.     {
  30.         os_ << "size=" << size
  31.             << " max=" << static_cast<double>(max_value)
  32.             << " sum=" << sum
  33.             << " seed=" << seed
  34.             << '\n';
  35.     }
  36.  
  37.     template <typename M>
  38.     void operator() (M msg)
  39.     {
  40.         const chrono::duration<double> d = chrono::steady_clock::now() - start_;
  41.         os_ << d.count() << "s:  " << msg << '\n';
  42.     }
  43.  
  44.     void name(const char* name)
  45.     {
  46.         os_ << name << '\n';
  47.     }
  48.  
  49. private:
  50.     ostream& os_;
  51.     const chrono::time_point<chrono::steady_clock> start_;
  52. };
  53.  
  54. template<typename I>
  55. void dp(I b, I e, i64 sum, Log& log)
  56. {
  57.     log.name("dynamic programming");
  58.     vector<char> subset_sums(sum / 2 + 1, false);
  59.     subset_sums[0] = true;
  60.  
  61.     for_each(b, e, [&](i64 value)
  62.     {
  63.         for (i64 i = sum / 2 - value; i >= 0; --i)
  64.         {
  65.             if (subset_sums[i])
  66.                 subset_sums[i + value] = true;
  67.         }
  68.     });
  69.  
  70.     const auto it = find(subset_sums.rbegin(), subset_sums.rend(), true);
  71.     const auto pos = subset_sums.rend() - it - 1;
  72.     log(sum - 2 * pos);
  73. }
  74.  
  75. void mergeValue(vector<i64>& to, const vector<i64>& from, i64 value)
  76. {
  77.     to.clear();
  78.     auto original = begin(from);
  79.     auto summed = begin(from);
  80.     const auto last = end(from);
  81.  
  82.     while (original != last)
  83.     {
  84.         if (summed == last)
  85.         {
  86.             copy(original, last, back_inserter(to));
  87.             return;
  88.         }
  89.  
  90.         if (*summed + value < *original)
  91.         {
  92.             to.push_back(*summed + value);
  93.             ++summed;
  94.         }
  95.         else
  96.         {
  97.             to.push_back(*original);
  98.             ++original;
  99.         }
  100.     }
  101.  
  102.     transform(summed, last, back_inserter(to),
  103.               [value](i64 x){return x + value;});
  104. }
  105.  
  106. template<typename I>
  107. vector<i64> subsetSums(I b, I e)
  108. {
  109.     auto isize = e - b;
  110.     const auto size = 1 << isize;
  111.     vector<i64> subset_sums;
  112.     subset_sums.reserve(size);
  113.     vector<i64> subset_sums2;
  114.     subset_sums2.reserve(size / 2);
  115.     vector<i64>* const ways[2] {&subset_sums, &subset_sums2};
  116.     ways[isize&1]->push_back(0);
  117.  
  118.     while (isize--)
  119.         mergeValue(*ways[isize&1], *ways[(isize+1)&1], *(b + isize));
  120.  
  121.     return subset_sums;
  122. }
  123.  
  124. template<typename I>
  125. void hs(I b, I e, i64 sum, Log& log)
  126. {
  127.     log.name("Horowitz-Sahni");
  128.     const auto middle = (e - b) / 2;
  129.     const vector<i64> first_half = subsetSums(b, b + middle);
  130.     const vector<i64> second_half = subsetSums(b + middle, e);
  131.     const auto target = sum / 2;
  132.     auto result = sum;
  133.     auto it1 = begin(first_half);
  134.     auto it2 = second_half.rbegin();
  135.  
  136.     while (it1 != end(first_half) && it2 != second_half.rend())
  137.     {
  138.         const auto both = *it1 + *it2;
  139.  
  140.         if (both > target)
  141.         {
  142.             result = min(result, 2 * both - sum);
  143.             ++it2;
  144.         }
  145.         else
  146.         {
  147.             result = min(result, sum - 2 * both);
  148.             ++it1;
  149.         }
  150.  
  151.         if (result <= 1)
  152.             break;
  153.     }
  154.  
  155.     log(result);
  156. }
  157.  
  158. i64 kkMH(const vector<i64>& values, Log& log)
  159. {
  160.     log.name("Karmarkar-Karp max heap");
  161.     vector<i64> pq(values);
  162.     make_heap(begin(pq), end(pq));
  163.  
  164.     while (pq.size() > 1)
  165.     {
  166.         auto first = pq[0];
  167.         pop_heap(begin(pq), end(pq));
  168.         pq.pop_back();
  169.         auto second = pq[0];
  170.         pop_heap(begin(pq), end(pq));
  171.         pq[pq.size() - 1] = first - second;
  172.         push_heap(begin(pq), end(pq));
  173.     }
  174.  
  175.     log(pq[0]);
  176.     return pq[0];
  177. }
  178.  
  179. template<bool Preprocess = false>
  180. i64 kk(const vector<i64>& values, i64 sum, Log& log)
  181. {
  182.     log.name("Karmarkar-Karp");
  183.     vector<i64> pq(values.size() * 2);
  184.     copy(begin(values), end(values), begin(pq) + values.size());
  185.     sort(begin(pq) + values.size(), end(pq));
  186.     auto first = end(pq);
  187.     auto last = begin(pq) + values.size();
  188.  
  189.     while (first - last > 1)
  190.     {
  191.         if (Preprocess && first - last <= kHSLimit)
  192.         {
  193.             hs(last, first, sum, log);
  194.             return 0;
  195.         }
  196.  
  197.         if (Preprocess && static_cast<double>(first - last) * sum <= kDPLimit)
  198.         {
  199.             dp(last, first, sum, log);
  200.             return 0;
  201.         }
  202.  
  203.         const auto diff = *(first - 1) - *(first - 2);
  204.         sum -= *(first - 2) * 2;
  205.         first -= 2;
  206.         //const auto place = find_if(last, first, [diff](i64 x){return x>=diff;});
  207.         const auto place = lower_bound(last, first, diff);
  208.         --last;
  209.         copy(last + 1, place, last);
  210.         *(place - 1) = diff;
  211.     }
  212.  
  213.     const auto result = (first - last)? *last: 0;
  214.     log(result);
  215.     return result;
  216. }
  217.  
  218. // arguments: size, max value, random seed (integers, 0x or 0 prefix allowed)
  219. int main(int argc, char **argv)
  220. {
  221.     size_t size = 10000;
  222.     i64 max_value = 100000000000000ll; // 10^14
  223.     u64 seed  = random_device{}();
  224.  
  225.     if (argc > 1)
  226.         size = min<u64>(size, strtoull(argv[1], nullptr, 0));
  227.  
  228.     if (argc > 2)
  229.         max_value = min<u64>(max_value, strtoull(argv[2], nullptr, 0));
  230.  
  231.     if (argc > 3)
  232.         seed = strtoull(argv[3], nullptr, 0);
  233.  
  234.     mt19937_64 rng(seed);
  235.     uniform_int_distribution<i64> ud(1, max_value);
  236.     auto gen = bind(ud, rng);
  237.     vector<i64> values(size);
  238.     generate_n(begin(values), size, gen);
  239.     const auto sum = accumulate(begin(values), end(values), 0ll);
  240.     Log log(size, max_value, sum, seed, cout);
  241.  
  242.     if (kk(values, sum, log) > 1 && size > kKKLimit)
  243.         kk<true>(values, sum, log);
  244. }
  245.  
Success #stdin #stdout 0.01s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
size=10000 max=1e+14 sum=503700448779778280 seed=2052362949
Karmarkar-Karp
0.0113423s:  0
https://ideone.com/0QYVDA
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!