Problem 328: Lowest-cost Search
View on Project EulerProject Euler Problem 328 Solution
EulerSolve provides an optimized solution for Project Euler Problem 328, Lowest-cost Search, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary An unknown integer lies in \([1,n]\). If we guess \(k\) and we are wrong, we pay a cost of \(k\), and we are only told whether the hidden number is smaller or larger. We then continue recursively on the surviving interval. Let \(C(n)\) be the minimum possible worst-case cost, and define $$S(N)=\sum_{n=1}^{N}C(n).$$ The task is to compute \(S(200000)\). Mathematical Approach 1) Canonical minimax interval DP. For a general interval \([l,r]\), define $$F(l,r)=\min_{k\in[l,r]}\Bigl(k+\max(F(l,k-1),F(k+1,r))\Bigr),$$ with base case $$F(l,l)=0.$$ The quantity we want is $$C(n)=F(1,n).$$ 2) Why the naive DP is hopeless. There are \(O(n^2)\) intervals, and for each one the naive transition tries all \(O(n)\) pivots. So the standard interval DP is cubic. That is completely infeasible for $$n=200000.$$ 3) Rewrite the first guess using the suffix length. Suppose the first guess for \([1,n]\) is \(k\). Write $$m=n-k,$$ so \(m\) is the length of the right suffix \([k+1,n]\). Then the left branch has length \(k-1=n-m-1\), so its cost is exactly $$L_n(m)=k+C(k-1)=(n-m)+C(n-m-1).$$ This part depends only on the already-known values \(C(1),C(2),\dots\). 4) The right branch is not translation-invariant, but it is almost affine. The right interval is \([k+1,n]\), not \([1,m]\)....
Detailed mathematical approach
Problem Summary
An unknown integer lies in \([1,n]\). If we guess \(k\) and we are wrong, we pay a cost of \(k\), and we are only told whether the hidden number is smaller or larger. We then continue recursively on the surviving interval. Let \(C(n)\) be the minimum possible worst-case cost, and define
$$S(N)=\sum_{n=1}^{N}C(n).$$
The task is to compute \(S(200000)\).
Mathematical Approach
1) Canonical minimax interval DP.
For a general interval \([l,r]\), define
$$F(l,r)=\min_{k\in[l,r]}\Bigl(k+\max(F(l,k-1),F(k+1,r))\Bigr),$$
with base case
$$F(l,l)=0.$$
The quantity we want is
$$C(n)=F(1,n).$$
2) Why the naive DP is hopeless.
There are \(O(n^2)\) intervals, and for each one the naive transition tries all \(O(n)\) pivots. So the standard interval DP is cubic. That is completely infeasible for
$$n=200000.$$
3) Rewrite the first guess using the suffix length.
Suppose the first guess for \([1,n]\) is \(k\). Write
$$m=n-k,$$
so \(m\) is the length of the right suffix \([k+1,n]\).
Then the left branch has length \(k-1=n-m-1\), so its cost is exactly
$$L_n(m)=k+C(k-1)=(n-m)+C(n-m-1).$$
This part depends only on the already-known values \(C(1),C(2),\dots\).
4) The right branch is not translation-invariant, but it is almost affine.
The right interval is \([k+1,n]\), not \([1,m]\). Every guess inside that interval is shifted upward by \(k=n-m\), so each wrong step on the right picks up an extra additive offset of \(k\).
The implementation exploits a structural fact: for a suffix of length \(m\), if
$$d=\lfloor \log_2 m\rfloor,$$
then the optimal right-branch envelope can be represented by two affine pieces in the shift \(k=n-m\):
$$R_{n,d}^{(1)}(m)=(n-m)(d+1)+A(m),$$
$$R_{n,d}^{(2)}(m)=(n-m)d+B(m).$$
Here \(A(m)\) and \(B(m)\) are precomputed one-dimensional arrays that summarize the additive constants for the two relevant depth layers.
5) Therefore each candidate pivot is evaluated by a max of three terms.
For fixed \(n\) and suffix length \(m\), the first-guess cost becomes
$$\operatorname{Obj}(n,m)=\max\Bigl(L_n(m),R_{n,d}^{(1)}(m),R_{n,d}^{(2)}(m)\Bigr),$$
where \(d=\lfloor\log_2 m\rfloor\).
So instead of solving a two-dimensional interval DP, the program only needs to minimize this objective over
$$m=1,2,\dots,n-1.$$
6) What the arrays \(A(m)\) and \(B(m)\) mean.
They encode the optimal worst-case additive costs of the right suffix after factoring out the linear dependence on the global shift \(k=n-m\). The code fills them in increasing order of \(m\), using the fact that intervals with the same
$$d=\lfloor\log_2 m\rfloor$$
belong to one depth band
$$2^d\le m\le 2^{d+1}-1.$$
Inside one band, the candidate formulas become simple linear transforms of \(A(m)\) and \(B(m)\), which makes range-minimum preprocessing possible.
7) Why sparse tables appear.
For each depth band \(d\), the code stores
$$A(m)-m(d+1)\quad\text{and}\quad B(m)-md$$
in sparse tables. That allows fast RMQ queries inside any subrange of that band, so the best candidate of each affine family can be recovered in
$$O(1)$$
time after preprocessing.
8) Why only a few candidates per band are tested.
The code also uses monotonicity tests. Define the left cost
$$L_n(m)=(n-m)+C(n-m-1),$$
and compare it with the right envelope. Their crossings move monotonically as \(m\) changes, so once the crossing location is bracketed, only a tiny neighborhood around that point can contain the minimizer. That is why the implementation checks only a handful of values near band boundaries, RMQ minima, and crossing points.
9) Small exact validation.
The program still computes the exact cubic interval DP for
$$n\le 200$$
and asserts that the accelerated values match it. This is the correctness safety net for the optimization.
10) Checkpoints.
The code validates
$$C(1)=0,\qquad C(2)=1,\qquad C(3)=2,\qquad C(8)=12,\qquad C(100)=400,$$
and also
$$\sum_{n=1}^{100}C(n)=17575.$$
These are strong consistency checks for both the exact and accelerated paths.
Algorithm
1) Build the helper envelopes \(A(m)\) and \(B(m)\) for all \(m\le N\).
2) For each depth band, build sparse-table RMQ structures.
3) Compute \(C(n)\) for \(n=2,3,\dots,N\) by scanning depth bands and checking only the relevant local candidates.
4) Accumulate the running sum \(S(N)\).
Complexity Analysis
The optimized method runs in roughly
$$O(N\log N)$$
time with linear arrays plus RMQ tables. This replaces the impossible cubic interval DP by a method that is fast enough for
$$N=200000.$$
Checks And Final Result
The checkpoints are
$$C(1)=0,\quad C(2)=1,\quad C(3)=2,\quad C(8)=12,\quad C(100)=400,$$
$$\sum_{n=1}^{100}C(n)=17575.$$
The final answer is
$$S(200000)=260511850222.$$
Further Reading
- Problem page: https://projecteuler.net/problem=328
- Minimax decision trees: https://en.wikipedia.org/wiki/Minimax
- Sparse table RMQ: https://cp-algorithms.com/data_structures/sparse-table.html
Problem 328 source code
C++
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
static inline int depth_int(int m) {
if (m <= 0) return -1;
return 31 - __builtin_clz(static_cast<unsigned>(m));
}
struct BandRMQ {
int d = 0;
int start = 0;
int end = 0;
int len = 0;
vector<long long> s1;
vector<long long> s2;
vector<int> lg;
vector<vector<int>> st1;
vector<vector<int>> st2;
void build(int d_, int start_, int end_,
const vector<long long>& A,
const vector<long long>& B) {
d = d_;
start = start_;
end = end_;
len = end - start + 1;
s1.resize(len);
s2.resize(len);
for (int i = 0; i < len; i++) {
int m = start + i;
s1[i] = A[m] - 1LL * m * (d + 1);
s2[i] = B[m] - 1LL * m * d;
}
lg.assign(len + 1, 0);
for (int i = 2; i <= len; i++) lg[i] = lg[i / 2] + 1;
int K = lg[len] + 1;
st1.assign(K, vector<int>(len));
st2.assign(K, vector<int>(len));
for (int i = 0; i < len; i++) {
st1[0][i] = i;
st2[0][i] = i;
}
for (int k = 1; k < K; k++) {
int span = 1 << (k - 1);
int limit = len - (1 << k) + 1;
for (int i = 0; i < limit; i++) {
int i1 = st1[k - 1][i];
int i2 = st1[k - 1][i + span];
st1[k][i] = (s1[i1] <= s1[i2]) ? i1 : i2;
int j1 = st2[k - 1][i];
int j2 = st2[k - 1][i + span];
st2[k][i] = (s2[j1] <= s2[j2]) ? j1 : j2;
}
}
}
inline int rmqArgMin1Abs(int lAbs, int rAbs) const {
int l = lAbs - start;
int r = rAbs - start;
int L = r - l + 1;
int k = lg[L];
int i1 = st1[k][l];
int i2 = st1[k][r - (1 << k) + 1];
int idx = (s1[i1] <= s1[i2]) ? i1 : i2;
return start + idx;
}
inline int rmqArgMin2Abs(int lAbs, int rAbs) const {
int l = lAbs - start;
int r = rAbs - start;
int L = r - l + 1;
int k = lg[L];
int i1 = st2[k][l];
int i2 = st2[k][r - (1 << k) + 1];
int idx = (s2[i1] <= s2[i2]) ? i1 : i2;
return start + idx;
}
};
static vector<long long> compute_exact_small(int n) {
const long long INF = numeric_limits<long long>::max() / 4;
vector<vector<long long>> dp(n + 2, vector<long long>(n + 2, 0));
for (int len = 2; len <= n; ++len) {
for (int l = 1; l + len - 1 <= n; ++l) {
int r = l + len - 1;
long long best = INF;
for (int k = l; k <= r; ++k) {
long long cost = static_cast<long long>(k) +
max(dp[l][k - 1], dp[k + 1][r]);
if (cost < best) best = cost;
}
dp[l][r] = best;
}
}
vector<long long> out(n + 1, 0);
for (int i = 1; i <= n; ++i) out[i] = dp[1][i];
return out;
}
int main() {
const int N = 200000;
const long long INF = (1LL << 62);
int maxD = depth_int(N);
// ---- Compute A(m) ----
vector<long long> A(N + 1, 0), B(N + 1, 0);
vector<vector<long long>> sufMinVal(maxD + 1);
vector<vector<int>> sufArgVal(maxD + 1);
vector<char> built(maxD + 1, 0);
built[0] = 1;
auto buildSuf = [&](int d) {
int lo = 1 << (d - 1);
int hi = (1 << d) - 1;
int len = hi - lo + 1;
sufMinVal[d].assign(len, 0);
sufArgVal[d].assign(len, 0);
long long best = A[hi] - 1LL * hi * d;
int arg = hi;
sufMinVal[d][len - 1] = best;
sufArgVal[d][len - 1] = arg;
for (int i = len - 2; i >= 0; i--) {
int q = lo + i;
long long v = A[q] - 1LL * q * d;
if (v < best) {
best = v;
arg = q;
}
sufMinVal[d][i] = best;
sufArgVal[d][i] = arg;
}
built[d] = 1;
};
for (int m = 2; m <= N; m++) {
int d = depth_int(m);
if (d >= 1 && !built[d]) buildSuf(d);
if (d == 0) {
A[m] = 0;
continue;
}
int base = 1 << (d - 1);
int qLo = max(base, m - (1 << d));
long long rightCost = 1LL * m * d + sufMinVal[d][qLo - base];
long long leftCost = INF;
int p = m - base + 1;
if (p <= (1 << d)) {
leftCost = 1LL * p + A[p - 1];
}
A[m] = min(leftCost, rightCost);
}
for (int d = 1; d <= maxD; d++) {
if (!built[d]) buildSuf(d);
}
// ---- Compute B(m) ----
auto B_cand_for_q = [&](int m, int q) -> long long {
int d = depth_int(m);
int p = m - q;
int L = p - 1;
long long best = 1LL * p * (d - 1) + B[q];
int Dl = depth_int(L);
if (Dl == d - 1) {
best = max(best, 1LL * p + B[L]);
} else if (Dl == d - 2) {
best = max(best, 1LL * p + A[L]);
}
return best;
};
for (int m = 2; m <= N; m++) {
int d = depth_int(m);
if (d == 0) {
B[m] = 0;
continue;
}
int base = 1 << (d - 1);
int p0 = m - base + 1;
long long leftA = INF;
if (p0 <= (1 << d)) {
leftA = 1LL * p0 + A[p0 - 1];
}
int qLo = max(base, m - (1 << d));
long long rightBestA = 1LL * m * d + sufMinVal[d][qLo - base];
if (leftA == A[m]) {
int L = p0 - 1;
int R = m - p0;
long long bestB = max(1LL * p0 + B[L], 1LL * p0 * (d - 1) + A[R]);
if (rightBestA == A[m]) {
int q = sufArgVal[d][qLo - base];
long long cand = B_cand_for_q(m, q);
bestB = min(bestB, cand);
}
B[m] = bestB;
} else {
int q = sufArgVal[d][qLo - base];
B[m] = B_cand_for_q(m, q);
}
}
// ---- Build RMQ per depth band ----
vector<BandRMQ> bands(maxD + 1);
vector<char> hasBand(maxD + 1, 0);
for (int d = 1; d <= maxD; d++) {
int start = 1 << d;
int end = min((1 << (d + 1)) - 1, N);
if (start <= end) {
bands[d].build(d, start, end, A, B);
hasBand[d] = 1;
}
}
// ---- Compute C(n) and sum ----
vector<long long> C(N + 1, 0);
long long sum = 0;
auto obj = [&](int n, int d, int m) -> long long {
int k = n - m;
long long L = 1LL * k + C[k - 1];
long long g1 = 1LL * k * (d + 1) + A[m];
long long g2 = 1LL * k * d + B[m];
return max(L, max(g1, g2));
};
for (int n = 2; n <= N; n++) {
long long best = INF;
// d=0 band: m=1
{
int m = 1;
int k = n - m;
long long cand = 1LL * k + C[k - 1];
best = min(best, cand);
}
int maxDn = depth_int(n - 1);
for (int d = 1; d <= maxDn; d++) {
int mLo = 1 << d;
int mHi = min((1 << (d + 1)) - 1, n - 1);
if (mLo > mHi) continue;
auto rightCost = [&](int m) -> long long {
int k = n - m;
long long t1 = 1LL * k * d + A[m];
long long t2 = 1LL * k * (d - 1) + B[m];
return max(t1, t2);
};
auto P = [&](int m) -> bool {
int k = n - m;
return C[k - 1] <= rightCost(m);
};
auto h = [&](int m) -> long long {
int k = n - m;
return 1LL * k + A[m] - B[m];
};
if (!P(mHi)) {
for (int m : {mHi, mHi - 1}) {
if (m < mLo || m > mHi) continue;
best = min(best, obj(n, d, m));
}
continue;
}
int mP;
if (P(mLo)) {
mP = mLo;
} else {
int lo = mLo, hi = mHi;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (P(mid)) hi = mid; else lo = mid + 1;
}
mP = lo;
for (int m : {mP - 1, mP}) {
if (m < mLo || m > mHi) continue;
best = min(best, obj(n, d, m));
}
}
int subLo = mP;
int subHi = mHi;
for (int m : {subLo, subHi, subHi - 1, subHi - 2}) {
if (m < subLo || m > subHi) continue;
best = min(best, obj(n, d, m));
}
long long hLo = h(subLo);
long long hHi = h(subHi);
if (hasBand[d]) {
const BandRMQ& band = bands[d];
if (hLo >= 0 && hHi >= 0) {
int mMin = band.rmqArgMin1Abs(subLo, subHi);
for (int m = mMin - 2; m <= mMin + 2; m++) {
if (m < subLo || m > subHi) continue;
best = min(best, obj(n, d, m));
}
} else if (hLo <= 0 && hHi <= 0) {
int mMin = band.rmqArgMin2Abs(subLo, subHi);
for (int m = mMin - 2; m <= mMin + 2; m++) {
if (m < subLo || m > subHi) continue;
best = min(best, obj(n, d, m));
}
} else {
int lo = subLo, hi = subHi;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (h(mid) >= 0) hi = mid; else lo = mid + 1;
}
int mQ = lo;
for (int m = mQ - 4; m <= mQ + 4; m++) {
if (m < subLo || m > subHi) continue;
best = min(best, obj(n, d, m));
}
int mMin1 = band.rmqArgMin1Abs(subLo, subHi);
int mMin2 = band.rmqArgMin2Abs(subLo, subHi);
for (int mm : {mMin1, mMin2}) {
for (int m = mm - 2; m <= mm + 2; m++) {
if (m < subLo || m > subHi) continue;
best = min(best, obj(n, d, m));
}
}
}
}
}
C[n] = best;
sum += best;
}
// ---- Validation checkpoints ----
{
auto exact = compute_exact_small(200);
for (int i = 1; i <= 200; ++i) {
assert(C[i] == exact[i]);
}
}
assert(C[1] == 0);
assert(C[2] == 1);
assert(C[3] == 2);
assert(C[8] == 12);
assert(C[100] == 400);
long long sum100 = 0;
for (int i = 1; i <= 100; ++i) sum100 += C[i];
assert(sum100 == 17575);
assert(sum == 260511850222LL);
cout << sum << "\n";
return 0;
}
Python
def solve():
N = 200000
INF = 1 << 62
def depth_int(m):
if m <= 0:
return -1
return m.bit_length() - 1
# Compute A(m)
A = [0] * (N + 1)
B = [0] * (N + 1)
suf_min_val = {}
suf_arg_val = {}
built = set([0])
def build_suf(d):
lo = 1 << (d - 1)
hi = (1 << d) - 1
length = hi - lo + 1
smv = [0] * length
sav = [0] * length
best = A[hi] - hi * d
arg = hi
smv[length - 1] = best
sav[length - 1] = arg
for i in range(length - 2, -1, -1):
q = lo + i
v = A[q] - q * d
if v < best:
best = v
arg = q
smv[i] = best
sav[i] = arg
suf_min_val[d] = smv
suf_arg_val[d] = sav
built.add(d)
for m in range(2, N + 1):
d = depth_int(m)
if d >= 1 and d not in built:
build_suf(d)
if d == 0:
A[m] = 0
continue
base = 1 << (d - 1)
qLo = max(base, m - (1 << d))
right_cost = m * d + suf_min_val[d][qLo - base]
left_cost = INF
p = m - base + 1
if p <= (1 << d):
left_cost = p + A[p - 1]
A[m] = min(left_cost, right_cost)
max_d = depth_int(N)
for d in range(1, max_d + 1):
if d not in built:
build_suf(d)
# Compute B(m)
def B_cand(m, q):
d = depth_int(m)
p = m - q
L = p - 1
best = p * (d - 1) + B[q]
Dl = depth_int(L)
if Dl == d - 1:
best = max(best, p + B[L])
elif Dl == d - 2:
best = max(best, p + A[L])
return best
for m in range(2, N + 1):
d = depth_int(m)
if d == 0:
B[m] = 0
continue
base = 1 << (d - 1)
p0 = m - base + 1
leftA = INF
if p0 <= (1 << d):
leftA = p0 + A[p0 - 1]
qLo = max(base, m - (1 << d))
rightBestA = m * d + suf_min_val[d][qLo - base]
if leftA == A[m]:
L = p0 - 1
R = m - p0
bestB = max(p0 + B[L], p0 * (d - 1) + A[R])
if rightBestA == A[m]:
q = suf_arg_val[d][qLo - base]
bestB = min(bestB, B_cand(m, q))
B[m] = bestB
else:
q = suf_arg_val[d][qLo - base]
B[m] = B_cand(m, q)
# Build sparse table RMQ per band
class BandRMQ:
def __init__(self, d, start, end):
self.d = d
self.start = start
self.end = end
self.length = end - start + 1
self.s1 = [A[start + i] - (start + i) * (d + 1) for i in range(self.length)]
self.s2 = [B[start + i] - (start + i) * d for i in range(self.length)]
lg = [0] * (self.length + 1)
for i in range(2, self.length + 1):
lg[i] = lg[i // 2] + 1
K = lg[self.length] + 1
st1 = [list(range(self.length))]
st2 = [list(range(self.length))]
for k in range(1, K):
sp = 1 << (k - 1)
lim = self.length - (1 << k) + 1
row1 = [0] * lim
row2 = [0] * lim
for i in range(lim):
i1, i2 = st1[k-1][i], st1[k-1][i + sp]
row1[i] = i1 if self.s1[i1] <= self.s1[i2] else i2
j1, j2 = st2[k-1][i], st2[k-1][i + sp]
row2[i] = j1 if self.s2[j1] <= self.s2[j2] else j2
st1.append(row1)
st2.append(row2)
self.st1, self.st2, self.lg = st1, st2, lg
def rmq1(self, lA, rA):
l, r = lA - self.start, rA - self.start
L = r - l + 1; k = self.lg[L]
i1, i2 = self.st1[k][l], self.st1[k][r - (1 << k) + 1]
return self.start + (i1 if self.s1[i1] <= self.s1[i2] else i2)
def rmq2(self, lA, rA):
l, r = lA - self.start, rA - self.start
L = r - l + 1; k = self.lg[L]
i1, i2 = self.st2[k][l], self.st2[k][r - (1 << k) + 1]
return self.start + (i1 if self.s2[i1] <= self.s2[i2] else i2)
bands = {}
for d in range(1, max_d + 1):
s = 1 << d
e = min((1 << (d + 1)) - 1, N)
if s <= e:
bands[d] = BandRMQ(d, s, e)
# Compute C(n)
C = [0] * (N + 1)
total_sum = 0
def obj(n, d, m):
k = n - m
L = k + C[k - 1]
g1 = k * (d + 1) + A[m]
g2 = k * d + B[m]
return max(L, max(g1, g2))
for n in range(2, N + 1):
best = INF
# d=0 band: m=1
k = n - 1
best = min(best, k + C[k - 1])
maxDn = depth_int(n - 1)
for d in range(1, maxDn + 1):
mLo = 1 << d
mHi = min((1 << (d + 1)) - 1, n - 1)
if mLo > mHi:
continue
def rightCost(m):
kk = n - m
return max(kk * d + A[m], kk * (d - 1) + B[m])
def P(m):
kk = n - m
return C[kk - 1] <= rightCost(m)
def h(m):
kk = n - m
return kk + A[m] - B[m]
if not P(mHi):
for m in [mHi, mHi - 1]:
if mLo <= m <= mHi:
best = min(best, obj(n, d, m))
continue
if P(mLo):
mP = mLo
else:
lo2, hi2 = mLo, mHi
while lo2 < hi2:
mid = (lo2 + hi2) >> 1
if P(mid):
hi2 = mid
else:
lo2 = mid + 1
mP = lo2
for m in [mP - 1, mP]:
if mLo <= m <= mHi:
best = min(best, obj(n, d, m))
subLo, subHi = mP, mHi
for m in [subLo, subHi, subHi - 1, subHi - 2]:
if subLo <= m <= subHi:
best = min(best, obj(n, d, m))
if d in bands:
hLo = h(subLo)
hHi = h(subHi)
band = bands[d]
if hLo >= 0 and hHi >= 0:
mMin = band.rmq1(subLo, subHi)
for m in range(max(subLo, mMin - 2), min(subHi, mMin + 2) + 1):
best = min(best, obj(n, d, m))
elif hLo <= 0 and hHi <= 0:
mMin = band.rmq2(subLo, subHi)
for m in range(max(subLo, mMin - 2), min(subHi, mMin + 2) + 1):
best = min(best, obj(n, d, m))
else:
lo2, hi2 = subLo, subHi
while lo2 < hi2:
mid = (lo2 + hi2) >> 1
if h(mid) >= 0:
hi2 = mid
else:
lo2 = mid + 1
mQ = lo2
for m in range(max(subLo, mQ - 4), min(subHi, mQ + 4) + 1):
best = min(best, obj(n, d, m))
mMin1 = band.rmq1(subLo, subHi)
mMin2 = band.rmq2(subLo, subHi)
for mm in [mMin1, mMin2]:
for m in range(max(subLo, mm - 2), min(subHi, mm + 2) + 1):
best = min(best, obj(n, d, m))
C[n] = best
total_sum += best
return str(total_sum)
if __name__ == '__main__':
print(solve())
Java
import java.util.*;
public class Euler328 {
static int depthInt(int m) {
if (m <= 0)
return -1;
return 31 - Integer.numberOfLeadingZeros(m);
}
static class BandRMQ {
int d;
int start;
int end;
int len;
long[] s1;
long[] s2;
int[] lg;
int[][] st1;
int[][] st2;
void build(int d_, int start_, int end_, long[] A, long[] B) {
d = d_;
start = start_;
end = end_;
len = end - start + 1;
s1 = new long[len];
s2 = new long[len];
for (int i = 0; i < len; i++) {
int m = start + i;
s1[i] = A[m] - 1L * m * (d + 1);
s2[i] = B[m] - 1L * m * d;
}
lg = new int[len + 1];
for (int i = 2; i <= len; i++)
lg[i] = lg[i / 2] + 1;
int K = lg[len] + 1;
st1 = new int[K][len];
st2 = new int[K][len];
for (int i = 0; i < len; i++) {
st1[0][i] = i;
st2[0][i] = i;
}
for (int k = 1; k < K; k++) {
int span = 1 << (k - 1);
int limit = len - (1 << k) + 1;
for (int i = 0; i < limit; i++) {
int i1 = st1[k - 1][i];
int i2 = st1[k - 1][i + span];
st1[k][i] = (s1[i1] <= s1[i2]) ? i1 : i2;
int j1 = st2[k - 1][i];
int j2 = st2[k - 1][i + span];
st2[k][i] = (s2[j1] <= s2[j2]) ? j1 : j2;
}
}
}
int rmqArgMin1Abs(int lAbs, int rAbs) {
int l = lAbs - start;
int r = rAbs - start;
int L = r - l + 1;
int k = lg[L];
int i1 = st1[k][l];
int i2 = st1[k][r - (1 << k) + 1];
int idx = (s1[i1] <= s1[i2]) ? i1 : i2;
return start + idx;
}
int rmqArgMin2Abs(int lAbs, int rAbs) {
int l = lAbs - start;
int r = rAbs - start;
int L = r - l + 1;
int k = lg[L];
int i1 = st2[k][l];
int i2 = st2[k][r - (1 << k) + 1];
int idx = (s2[i1] <= s2[i2]) ? i1 : i2;
return start + idx;
}
}
public static String solve() {
int N = 200000;
long INF = 1L << 62;
int maxD = depthInt(N);
long[] A = new long[N + 1];
long[] B = new long[N + 1];
long[][] sufMinVal = new long[maxD + 1][];
int[][] sufArgVal = new int[maxD + 1][];
boolean[] built = new boolean[maxD + 1];
built[0] = true;
for (int m = 2; m <= N; m++) {
int d = depthInt(m);
if (d >= 1 && !built[d]) {
int lo = 1 << (d - 1);
int hi = (1 << d) - 1;
int len = hi - lo + 1;
sufMinVal[d] = new long[len];
sufArgVal[d] = new int[len];
long best = A[hi] - 1L * hi * d;
int arg = hi;
sufMinVal[d][len - 1] = best;
sufArgVal[d][len - 1] = arg;
for (int i = len - 2; i >= 0; i--) {
int q = lo + i;
long v = A[q] - 1L * q * d;
if (v < best) {
best = v;
arg = q;
}
sufMinVal[d][i] = best;
sufArgVal[d][i] = arg;
}
built[d] = true;
}
if (d == 0) {
A[m] = 0;
continue;
}
int base = 1 << (d - 1);
int qLo = Math.max(base, m - (1 << d));
long rightCost = 1L * m * d + sufMinVal[d][qLo - base];
long leftCost = INF;
int p = m - base + 1;
if (p <= (1 << d)) {
leftCost = 1L * p + A[p - 1];
}
A[m] = Math.min(leftCost, rightCost);
}
for (int d = 1; d <= maxD; d++) {
if (!built[d]) {
int lo = 1 << (d - 1);
int hi = (1 << d) - 1;
int len = hi - lo + 1;
sufMinVal[d] = new long[len];
sufArgVal[d] = new int[len];
long best = A[hi] - 1L * hi * d;
int arg = hi;
sufMinVal[d][len - 1] = best;
sufArgVal[d][len - 1] = arg;
for (int i = len - 2; i >= 0; i--) {
int q = lo + i;
long v = A[q] - 1L * q * d;
if (v < best) {
best = v;
arg = q;
}
sufMinVal[d][i] = best;
sufArgVal[d][i] = arg;
}
built[d] = true;
}
}
for (int m = 2; m <= N; m++) {
int d = depthInt(m);
if (d == 0) {
B[m] = 0;
continue;
}
int base = 1 << (d - 1);
int p0 = m - base + 1;
long leftA = INF;
if (p0 <= (1 << d)) {
leftA = 1L * p0 + A[p0 - 1];
}
int qLo = Math.max(base, m - (1 << d));
long rightBestA = 1L * m * d + sufMinVal[d][qLo - base];
if (leftA == A[m]) {
int L = p0 - 1;
int R = m - p0;
long bestB = Math.max(1L * p0 + B[L], 1L * p0 * (d - 1) + A[R]);
if (rightBestA == A[m]) {
int q = sufArgVal[d][qLo - base];
long cand = 1L * (m - q) * (d - 1) + B[q];
int L2 = m - q - 1;
int Dl = depthInt(L2);
if (Dl == d - 1)
cand = Math.max(cand, 1L * (m - q) + B[L2]);
else if (Dl == d - 2)
cand = Math.max(cand, 1L * (m - q) + A[L2]);
bestB = Math.min(bestB, cand);
}
B[m] = bestB;
} else {
int q = sufArgVal[d][qLo - base];
long cand = 1L * (m - q) * (d - 1) + B[q];
int L2 = m - q - 1;
int Dl = depthInt(L2);
if (Dl == d - 1)
cand = Math.max(cand, 1L * (m - q) + B[L2]);
else if (Dl == d - 2)
cand = Math.max(cand, 1L * (m - q) + A[L2]);
B[m] = cand;
}
}
BandRMQ[] bands = new BandRMQ[maxD + 1];
boolean[] hasBand = new boolean[maxD + 1];
for (int d = 1; d <= maxD; d++) {
bands[d] = new BandRMQ();
int start = 1 << d;
int end = Math.min((1 << (d + 1)) - 1, N);
if (start <= end) {
bands[d].build(d, start, end, A, B);
hasBand[d] = true;
}
}
long[] C = new long[N + 1];
long sum = 0;
for (int n = 2; n <= N; n++) {
long best = INF;
int m1 = 1;
int k1 = n - m1;
long cand1 = 1L * k1 + C[k1 - 1];
best = Math.min(best, cand1);
int maxDn = depthInt(n - 1);
for (int d = 1; d <= maxDn; d++) {
int mLo = 1 << d;
int mHi = Math.min((1 << (d + 1)) - 1, n - 1);
if (mLo > mHi)
continue;
boolean pHi = C[n - mHi - 1] <= Math.max(1L * (n - mHi) * d + A[mHi],
1L * (n - mHi) * (d - 1) + B[mHi]);
if (!pHi) {
for (int m : new int[] { mHi, mHi - 1 }) {
if (m < mLo || m > mHi)
continue;
int k = n - m;
long cand = Math.max(1L * k + C[k - 1], Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m]));
best = Math.min(best, cand);
}
continue;
}
int mP;
boolean pLo = C[n - mLo - 1] <= Math.max(1L * (n - mLo) * d + A[mLo],
1L * (n - mLo) * (d - 1) + B[mLo]);
if (pLo) {
mP = mLo;
} else {
int lo = mLo, hi = mHi;
while (lo < hi) {
int mid = (lo + hi) >> 1;
boolean pMid = C[n - mid - 1] <= Math.max(1L * (n - mid) * d + A[mid],
1L * (n - mid) * (d - 1) + B[mid]);
if (pMid)
hi = mid;
else
lo = mid + 1;
}
mP = lo;
for (int m : new int[] { mP - 1, mP }) {
if (m < mLo || m > mHi)
continue;
int k = n - m;
long cand = Math.max(1L * k + C[k - 1], Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m]));
best = Math.min(best, cand);
}
}
int subLo = mP;
int subHi = mHi;
for (int m : new int[] { subLo, subHi, subHi - 1, subHi - 2 }) {
if (m < subLo || m > subHi)
continue;
int k = n - m;
long cand = Math.max(1L * k + C[k - 1], Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m]));
best = Math.min(best, cand);
}
long hLo = 1L * (n - subLo) + A[subLo] - B[subLo];
long hHi = 1L * (n - subHi) + A[subHi] - B[subHi];
if (hasBand[d]) {
BandRMQ band = bands[d];
if (hLo >= 0 && hHi >= 0) {
int mMin = band.rmqArgMin1Abs(subLo, subHi);
for (int m = mMin - 2; m <= mMin + 2; m++) {
if (m < subLo || m > subHi)
continue;
int k = n - m;
long cand = Math.max(1L * k + C[k - 1],
Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m]));
best = Math.min(best, cand);
}
} else if (hLo <= 0 && hHi <= 0) {
int mMin = band.rmqArgMin2Abs(subLo, subHi);
for (int m = mMin - 2; m <= mMin + 2; m++) {
if (m < subLo || m > subHi)
continue;
int k = n - m;
long cand = Math.max(1L * k + C[k - 1],
Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m]));
best = Math.min(best, cand);
}
} else {
int lo = subLo, hi = subHi;
while (lo < hi) {
int mid = (lo + hi) >> 1;
long hMid = 1L * (n - mid) + A[mid] - B[mid];
if (hMid >= 0)
hi = mid;
else
lo = mid + 1;
}
int mQ = lo;
for (int m = mQ - 4; m <= mQ + 4; m++) {
if (m < subLo || m > subHi)
continue;
int k = n - m;
long cand = Math.max(1L * k + C[k - 1],
Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m]));
best = Math.min(best, cand);
}
int mMin1 = band.rmqArgMin1Abs(subLo, subHi);
int mMin2 = band.rmqArgMin2Abs(subLo, subHi);
for (int mm : new int[] { mMin1, mMin2 }) {
for (int m = mm - 2; m <= mm + 2; m++) {
if (m < subLo || m > subHi)
continue;
int k = n - m;
long cand = Math.max(1L * k + C[k - 1],
Math.max(1L * k * (d + 1) + A[m], 1L * k * d + B[m]));
best = Math.min(best, cand);
}
}
}
}
}
C[n] = best;
sum += best;
}
return String.valueOf(sum);
}
public static void main(String[] args) {
System.out.println(solve());
}
}