Codeforces Round #356 (Div. 2) D. Bear and Tower of Cubes

Summary:

Given m < 10^15, find the largest (k, X) such that a[1]+a[2]+...+a[k] = X <= m, each a[i] is a perfect cube, and for a given X, a[i] is the largest cube such that a[1] + ... + a[i] <= X.

Solution:

The editorial has a very nice solution: http://codeforces.com/blog/entry/45310. I am discussing the solution here mostly for my own future reference.

The idea in the solution is a complete search on choices of cubes. Let Max(m) be the recursion that returns k the maximum length of cube tower that can be constructed and X the maximum sum we can get from such tower such that X <= m.

Let a be an integer such that a^3 <= m < (a+1)^3. The first cube can be of length 1 to a. If the length of the first cube is chosen to be a, then we recursively compute Max(m-a^3).

Otherwise, if the first cube is chosen to be a-1, then current X must be at most a^3-1, which means the next recursion call is Max((a-1)^3-1-(a-1)^3). We do not consider any other cases below s < a-1, since Max(S) <= Max(T) where S < T, and choosing s < a-1 will lead us to call Max with smaller argument then if we choose a-1.

Hence Max(m) = max{Max(m-a^3) + (1, a^3), Max(a^3-1-(a-1)^3) + (1, (a-1)^3)}.

Another cool thing about this solution is that we can make bounds on the runtime complexity:

Since each call Max(m) will lead to call to Max(m-a^3) and Max(a^3-1-(a-1)^3), where m is a polynomial of degree 3 in terms of a. Notice that both m-a^3 and a^3-1-(a-1)^3 has degree at most 2 in terms of a, hence there is a reduction from m = O(a^3) to O(a^2) which means each call on Max reduces its argument by power of 2/3. From here we can empirically compute k that reduces m = 10^15 to 1, and we get k somewhere around k = 18 to 19 steps, and hence by expanding the recursion tree we know that Max() is called at most 2^(k+1)-1 times or at most 2^20-1.

Code:

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <utility> #include <map> using namespace std; int GetK(int64_t m) { int lo=1,hi=100000, mid; while(lo<=hi) { mid = (lo+hi)/2; int64_t cur = 1LL*mid*mid*mid; if (cur < m) { lo = mid+1; } else { hi = mid-1; } } int64_t cur = 1LL*lo*lo*lo; if (cur == m) return lo; return hi; } pair<int64_t, int64_t> MaxCubes(int64_t m) { if (m <= 0) return {0, 0}; int k = GetK(m); int64_t k3 = 1LL*k*k*k; int64_t k_13 = 1LL*(k-1)*(k-1)*(k-1); pair<int64_t, int64_t> s = MaxCubes(m-k3); pair<int64_t, int64_t> t = MaxCubes(k3-1LL-k_13); s.first += 1; s.second += k3; t.first += 1; t.second += k_13; if (s.first == t.first) { return s.second > t.second ? s : t; } return s.first > t.first ? s : t; } int main(){ int64_t m; cin >> m; pair<int64_t,int64_t> p = MaxCubes(m); cout << p.first << " " << p.second << endl; return 0; }

## No comments:

## Post a Comment