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
A hidden integer is chosen from \(\{1,2,\dots,n\}\). Asking \(k\) costs \(k\), and the answer is one of three: the hidden number is higher, it is lower, or "yes, that's it". The cost is paid for every question, the successful one included. A strategy is optimal when it minimises the total cost of the questions asked in the worst case, and \(C(n)\) is that worst-case cost. The statement gives \(C(1)=0\), \(C(2)=1\), \(C(3)=2\), \(C(8)=12\), \(C(100)=400\), \(\sum_{n=1}^{100}C(n)=17575\), and a binary search on \(n=8\) costing \(4+6+7=17\). We must evaluate [1]
$$S(N)=\sum_{n=1}^{N}C(n),\qquad N=200\,000.$$
The whole solution in one sentence: the cost of a block of consecutive candidates depends only on its length and on how far it has been shifted upwards, so the programs model that dependence by two straight lines and use the model to shortlist about a hundred first questions for each \(n\) instead of visiting all \(O(N^2)\) blocks, then check the outcome against an exact calculation on small inputs. The values \(C(n)\) form the sequence A276128. [2]
Mathematical Approach
1. A strategy, and what one strategy costs
The candidates that remain always form a block of consecutive integers, so a strategy says, for every block that can arise, which number to ask next; nothing is asked once a block holds one candidate, since that candidate is already known. For a hidden value \(v\) write \(\ell_v\) for the number of questions its play uses and \(w_v\) for their total cost. The strategy costs \(\max_v w_v\).
Take the statement's optimal strategy for \(n=8\): ask \(5\); if told "lower" ask \(3\), and if told "lower" again ask \(1\); if told "higher" at the start ask \(7\). Playing it out gives \(w_1=w_2=9\) with three questions, \(w_3=w_4=8\) and \(w_6=w_7=w_8=12\) with two, \(w_5=5\) with one. The largest is \(12\), so the strategy costs \(12=C(8)\), while the statement's binary search asks \(4\), \(6\), \(7\) and costs \(17\).
2. The interval recurrence, and why it is too slow
Let \(F(l,r)\) be the optimal worst-case cost for the block \(\{l,l+1,\dots,r\}\), with \(F(l,r)=0\) when the block holds at most one candidate. Asking \(k\) costs \(k\) and leaves either \(\{l,\dots,k-1\}\) or \(\{k+1,\dots,r\}\), so
$$F(l,r)=\min_{l\le k\le r}\bigl(k+M_k\bigr),$$
$$M_k=\max\bigl(F(l,k-1),F(k+1,r)\bigr),$$
and \(C(n)=F(1,n)\). This is the shape of the classical optimal binary search tree recurrence, with a maximum in place of the weighted sum. [3] Taking blocks in increasing order of length makes both subproblems available when needed. There are \(\Theta(N^2)\) blocks, at most \(N\) choices of \(k\) for each, and a constant fraction of them have length proportional to \(N\): the work is \(\Theta(N^3)\) and the storage \(\Theta(N^2)\), both prohibitive at \(N=200\,000\).
3. Only the length and the shift matter
Shift a block upwards by \(s\): its candidates become \(s+1,\dots,s+m\) and every question grows by \(s\), so a play of \(\ell\) questions costing \(w\) now costs \(w+s\ell\). The whole cost table is therefore a function of two numbers only,
$$\Phi(m,s)=F(s+1,s+m),$$
with \(F(l,r)=\Phi(r-l+1,\,l-1)\) and \(C(n)=\Phi(n,0)\). Group the plays of one strategy by length: let \(W_t\) be the largest \(w_v\) among the \(v\) with \(\ell_v=t\). That strategy costs, at shift \(s\),
$$\max_t\bigl(W_t+st\bigr),$$
a maximum of straight lines in \(s\), hence a convex, piecewise linear function whose steepest slope is the largest number of questions the strategy can need. [6] For the \(n=8\) strategy above, \(W_1=5\), \(W_2=12\) and \(W_3=9\).
4. How many questions cannot be avoided
Let \(M(t)\) be the largest block settled with at most \(t\) questions. Without a question only one candidate can be known, so \(M(0)=1\); one question splits the block into the asked value and two smaller blocks, so
$$M(t)=2M(t-1)+1=2^{t+1}-1.$$
Now let \(2^d\le m\le 2^{d+1}-1\), that is \(d=\lfloor\log_2 m\rfloor\). Height \(d-1\) reaches only \(2^d-1\) candidates, fewer than \(m\), while height \(d\) reaches \(2^{d+1}-1\ge m\), a capacity attained by splitting into two blocks of at most \(2^d-1\) candidates each. The least possible number of questions is therefore exactly \(d\). Ordinary binary search needs one more, \(\lfloor\log_2 m\rfloor+1\) comparisons, [4] because it also compares the single candidate left over; here we stop when one candidate remains and ask nothing.
5. The two lines \(A(m)\) and \(B(m)\)
Write \(d=\lfloor\log_2 m\rfloor\). When the shift \(s\) is large the steepest line dominates, so the best strategies have the least height \(d\), and among them the best has the cheapest deepest plays. Define
$$A(m)=\min_T W_d(T),$$
the minimum of \(W_d\) over the strategies \(T\) of height \(d\). The program pairs \(A(m)\) with a second number \(B(m)\) built by the rules of Section 6 — an auxiliary intercept, not in general the \(W_{d-1}\) of a strategy attaining \(A(m)\): every height-three strategy on \(12\) candidates with \(W_3=25\) has \(W_2=14\), yet the code stores \(B(12)=16\), and for \(m=2\) and \(m=3\) no play uses \(d-1=0\) questions at all. With \(A(0)=A(1)=B(0)=B(1)=0\) and a singleton handled separately, the model for \(m\ge2\) is
$$\hat{\Phi}(m,s)=\max\bigl(ds+A(m),\,(d-1)s+B(m)\bigr).$$
For \(m=8\) the strategy of Section 1 realises both: \(A(8)=5+3+1=9\) and \(B(8)=5+7=12\), so \(\hat{\Phi}(8,s)=\max(3s+9,2s+12)\). At \(s=0\) this is \(12=C(8)\), and for \(s=0,1,\dots,6\) it gives \(12,14,16,18,21,24,27\) — the exact values of \(\Phi(8,s)\). A direct check confirms that \(\Phi(m,s)-ds\) settles at \(A(m)\) for every \(m\le 256\), so the steep line is the asymptote.
6. How \(A(m)\) and \(B(m)\) are built
All lengths with the same \(d\) form one band,
$$2^d\le m\le 2^{d+1}-1,$$
and the recurrence inside a band only looks at the band below. Let the first question of a height-\(d\) strategy for \(\{1,\dots,m\}\) be \(k\), leaving a low block of length \(k-1\) and a high block of length \(m-k\). A deepest play runs through whichever block still needs \(d-1\) questions, so two cases cover everything.
- The deepest play goes high. Put \(q=m-k\). The high block needs \(d-1\) questions exactly when \(2^{d-1}\le q\le 2^d-1\), and it is shifted by \(k\), so that play costs \(k+k(d-1)+A(q)=kd+A(q)\). The low block, of length \(m-q-1\), must also fit into \(d-1\) questions, forcing \(q\ge m-2^d\). Minimising over the admissible \(q\),
$$a_2=\min_q\bigl((m-q)d+A(q)\bigr),$$
$$\max(2^{d-1},\,m-2^d)\le q\le 2^d-1.$$
- The deepest play goes low. Then the high block is too short to reach depth \(d\), so \(m-k\le 2^{d-1}-1\). The low block is unshifted, so its deepest play costs \(k+A(k-1)\). Inside one band \(A\) is non-decreasing — restrict a height-\(d\) strategy to a shorter prefix of the same band and drop the questions whose answers are now predetermined; the height stays \(d\) and no deepest play grows — so the cheapest admissible choice is the smallest,
$$a_1=p+A(p-1),\qquad p=m-2^{d-1}+1,$$
available only while \(p\le 2^d\), the lower half of the band. Then \(A(m)=\min(a_1,a_2)\). Nothing is lost by letting \(a_2\) ignore a deepest play through the low block: after the root a deepest high play has \(d-1\) questions, all at least \(k+1\), costing at least \(k+(d-1)(k+1)\), while a low play has at most \(d-1\) questions, all at most \(k-1\), costing at most \(k+(d-1)(k-1)\).
\(B(m)\) comes from the same two cases. A play of length \(d-1\) spends \(d-2\) questions inside one block, and the \(d-2\) level of a block of length \(X\) is \(A(X)\) when \(\lfloor\log_2 X\rfloor=d-2\) and \(B(X)\) when it is \(d-1\); a shorter block cannot reach that depth. Low-deep, with \(L=p-1\) and \(R=2^{d-1}-1\), gives \(\max(p+B(L),\,p(d-1)+A(R))\) — note \(\lfloor\log_2 R\rfloor=d-2\), so \(A(R)\) appears, not \(B(R)\). High-deep, with \(p=m-q\) and \(L=p-1\), the high block contributes \(p(d-1)+B(q)\) and the low block adds \(p+B(L)\) or \(p+A(L)\) by the same rule. Only cases attaining \(A(m)\) are kept, the smaller value when both do; ties in \(A(q)-qd\) go to the largest \(q\). For \(m=16\), low-deep has \(p=9\), \(L=8\), \(R=7\) and \(\max(9+12,\,27+10)=37=B(16)\). The first entries are \(A(2)=B(2)=1\), \(A(3)=B(3)=2\), \(A(4)=4\), \(B(4)=3\), \(A(8)=9\), \(B(8)=12\), \(A(12)=25\), \(B(12)=16\): \(B\) may exceed \(A\) or fall below it.
7. Why the two lines bound the truth
The pair \(A(m)\), \(B(m)\) belongs to one explicit strategy \(T^{*}(m)\), the one these rules select. Reconstructing it confirms three facts for every \(2\le m\le200\,000\): its \(W_d\) equals \(A(m)\); either \(B(m)\le A(m)\), making the second line redundant, or its \(W_{d-1}\) equals \(B(m)\); and every remaining level \(W_t\) with \(t\le d-2\) is at most \(\max(A(m),B(m))\). Those levels carry smaller slopes too, so none can overtake the two kept lines at any \(s\ge0\), and \(\hat{\Phi}(m,s)\) is exactly the cost of \(T^{*}(m)\) at every shift. Since the optimum is at most the cost of any one strategy,
$$\Phi(m,s)\le\hat{\Phi}(m,s)$$
over every length the program uses. Equality cannot always hold: \(\Phi(m,\cdot)\) is a minimum of convex functions and need not be convex. At \(m=12\) the differences of \(\Phi(12,s)\) run \(3,3,3,4,4,4,4,3,3,\dots\) — the slope rises and falls again — so no two lines reproduce it, and \(\Phi(12,0)=21\) while \(\hat{\Phi}(12,0)=25\). The gap closes for large shifts: over all \(m\le 256\), \(s\le 2500\) the largest excess is \(320\), at \(m=240\), \(s=207\).
8. The objective for one first question
Write \(\widetilde{C}(n)\) for the value the program stores, \(\widetilde{C}(0)=\widetilde{C}(1)=0\), keeping \(C(n)\) for the optimum. Fix \(n\) and a first question \(k\): the high block has length \(m=n-k\) and shift \(k\), and the low block \(\{1,\dots,k-1\}\) is charged \(\widetilde{C}(k-1)\). For \(m\ge2\), with \(d=\lfloor\log_2 m\rfloor\),
$$G(n,m)=\max(L,g_1,g_2),\qquad k=n-m,$$
$$L=k+\widetilde{C}(k-1),$$
$$g_1=k(d+1)+A(m),\quad g_2=kd+B(m),$$
and the program sets \(\widetilde{C}(n)\) to the smallest \(G(n,m)\) among the suffix lengths it actually tries. The case \(m=1\) is always one of them, and there the high block is a singleton, so \(G=L\).
Two worked examples. For \(n=8\) the best suffix length is \(m=3\), so \(k=5\), \(d=1\): \(L=5+C(4)=9\), \(g_1=5\cdot2+A(3)=12\), \(g_2=5\cdot1+B(3)=7\), \(G=12=C(8)\) — the high block \(\{6,7,8\}\) with its single question \(7\) is the bottleneck, as in the statement. For \(n=100\) the best is \(m=15\), so \(k=85\), \(d=3\): \(L=85+C(84)=85+315=400\), \(g_1=85\cdot4+34=374\), \(g_2=85\cdot3+22=277\), \(G=400=C(100)\). Here the low block is the bottleneck, and the model is exact on the high block too: \(\hat{\Phi}(15,85)=\max(289,192)\) equals \(\Phi(15,85)\).
9. Which suffix lengths the code tries
Each band \(2^d\le m\le\min(2^{d+1}-1,n-1)\) is scanned separately, since \(d\) is constant there. Three monotone facts, audited over complete bands at \(N=200\,000\), shape the scan.
- \(\widetilde{C}\) is non-decreasing, so \(L=(n-m)+\widetilde{C}(n-m-1)\) is non-increasing in \(m\).
- The test \(\widetilde{C}(k-1)\le\hat{\Phi}(m,k)\), saying the low block is not the bottleneck, once true stays true as \(m\) grows, and one binary search finds the first such \(m\). Below it \(G=L\), so only the last position before the switch can win.
- Above the switch \(G=\max(g_1,g_2)\), and \(g_1\ge g_2\) exactly when \(h(m)=k+A(m)-B(m)\ge0\); this sign switches once too, and a second binary search locates it.
Over the remaining range each line minimises independently of \(n\), because
$$g_1=n(d+1)+\bigl(A(m)-m(d+1)\bigr),$$
$$g_2=nd+\bigl(B(m)-md\bigr).$$
The bracketed quantities depend on \(m\) alone, so the best \(m\) of each family is a range minimum of a fixed array. A sparse table answers that in \(O(1)\) after \(O(b\log b)\) preprocessing, \(b\) being the band length, because a minimum tolerates the overlap of the two covering blocks of length \(2^i\). [5]
The program evaluates \(G\) at the band ends, around each located switch (radius four at the sign switch, two at a range minimiser) and at the range minimisers. Two details limit what this proves: both sparse tables are queried over the whole remaining range, not the two sign ranges separately, and the neighbourhoods have fixed size. The shortlist therefore need not contain its own band's minimum. At \(n=79\) the band \(32\le m\le63\) has minimum \(322\) at \(m=47\), while the sampled positions \(32\) to \(44\) and \(61\) to \(63\) give only \(325\); another band supplies the correct \(C(79)=290\).
10. Why the computed value can only be too large
Each candidate charges the low block \(\widetilde{C}(k-1)\) and the high block \(\hat{\Phi}(m,k)\), the cost of a real strategy by Section 7. So whenever \(\widetilde{C}(k-1)\ge C(k-1)\), the value \(G(n,m)\) is at least the true cost of that first question, and a minimum over any subset of such candidates is still at least \(C(n)\). Induction on \(n\) gives
$$\widetilde{C}(n)\ge C(n),\qquad n\le200\,000.$$
The method therefore proves an upper bound. Equality is separate: the C++ program checks it for \(n\le200\) and the wider comparison below for \(n\le4000\), while the counterexample above rules out band-wise exact minimisation as a lemma.
How the Code Works
All three programs are iterative and run the same four stages. [7]
depth_int (depthInt in Java) returns \(\lfloor\log_2 m\rfloor\) from the leading bit — 31 - __builtin_clz, Integer.numberOfLeadingZeros, m.bit_length() - 1 — and \(-1\) for \(m\le0\), marking an empty block. The first loop then fills A. Just before a band is needed, buildSuf(d) tabulates in sufMinVal and sufArgVal the suffix minima of \(A(q)-qd\) over the band below and the \(q\) attaining each; the comparison is strict, so the largest such \(q\) is kept. One lookup at qLo = max(base, m - (1 << d)) gives \(a_2\) as rightCost, leftCost is \(a_1\) guarded by p <= (1 << d), and A[m] is their minimum; a catch-up loop builds any band the first loop skipped. The second loop fills B from the same two cases: B_cand_for_q handles the high-deep case with its low-block term selected by \(\lfloor\log_2 L\rfloor\), the low-deep case is written out directly with A[R] for its short high block, and the two are combined exactly when leftA and rightBestA both equal A[m].
BandRMQ::build stores the arrays of Section 9 as s1[i] = A[m] - m*(d+1) and s2[i] = B[m] - m*d, a table lg of binary logarithms, and the sparse tables st1, st2 of argument minima; rmqArgMin1Abs and rmqArgMin2Abs compare the two stored blocks covering a query.
The main loop over \(n\) takes \(m=1\) first, then runs over \(d=1,\dots,\lfloor\log_2(n-1)\rfloor\). The lambdas rightCost, P and h are \(\hat{\Phi}(m,n-m)\), the low-block test and the sign test of Section 9, and obj is \(G(n,m)\). If P fails at the top of the band, \(G=L\) throughout and only the top two positions are tried; otherwise the switch is located, by binary search unless P already holds at the band start, the band ends are tried, and the signs of h at the two ends select one sparse table, the other, or a second binary search followed by both. C[n] is the smallest value found, and sum accumulates it.
Only the C++ source carries self-checks, written with assert and so active only while NDEBUG is undefined: compute_exact_small(200) evaluates the recurrence of Section 2 over all blocks with \(r\le200\) and the following loop compares all two hundred values, then further assertions check \(C(1)\), \(C(2)\), \(C(3)\), \(C(8)\), \(C(100)\), the sum to \(100\) and the final total. Java and Python compute the same total without any checks. Java has no lambdas here, writing out the bodies of obj, B_cand_for_q and the suffix-minimum builder at each use. Python keeps BandRMQ as a class over lists, stores only the valid positions of each higher sparse-table row, and rebuilds rightCost, P and h inside the band loop, which costs real time; its integers are unbounded, while C++ and Java rely on 64-bit long long and long. [8]
Complexity and Verification
Filling A and B costs \(O(N)\): each length does constant work, and the suffix-minimum arrays, one per band, have total length below \(N\). A band of \(b\) entries carries \(\lfloor\log_2 b\rfloor+1\) sparse-table levels, so preprocessing and storage total \(O(N\log N)\); at \(N=200\,000\) there are \(17\) bands, the last truncated to \(68\,929\) entries and \(17\) levels. With four-byte indices and eight-byte costs the primitive arrays come to about \(36.6\) MB — \(30.2\) for the bands, \(1.6\) for the suffix minima, \(4.8\) for \(A\), \(B\), \(C\) — beside container overhead and Python's object representation. The main loop visits up to \(17\) bands per \(n\), spending \(O(\log N)\) binary-search steps and \(O(1)\) range queries on each, so the total is \(O(N\log^2 N)\). Counted at \(N=200\,000\): \(19\,130\,171\) calls to obj, about \(95.65\) per \(n\), besides \(199\,999\) singleton evaluations, with \(9\,175\,320\) binary-search steps and \(1\,474\,849\) range queries.
Integer width is never in doubt, and the bound need not presuppose that the program is optimal. The singleton candidate is always evaluated, so \(\widetilde{C}(n)\le n-1+\widetilde{C}(n-2)\); from \(\widetilde{C}(0)=\widetilde{C}(1)=0\), induction gives \(\widetilde{C}(n)\le\lfloor n^2/4\rfloor\), hence
$$\sum_{n=1}^{N}\widetilde{C}(n)\le\frac{N(N+1)(2N+1)}{24},$$
about \(6.7\cdot10^{14}\) at the requested limit, far inside the signed 64-bit range; the recurrences likewise keep \(0\le A(m),B(m)\le m\lfloor\log_2 m\rfloor\). The optimum itself obeys the sharper \(C(n)\le n\lfloor\log_2 n\rfloor\), from a strategy of least height. Compiled with -O2 on one desktop machine, C++ finishes in about \(0.06\) s with a \(41\) MB peak, Java in \(0.2\) s and Python in \(8.6\) s; all three print the same total.
The following was checked independently for this article.
- An exact evaluation of the interval recurrence agrees with the fast method for every \(n\le4000\), twenty times the C++ program's own range. An ascending scan over \(k\) may stop just after the first \(k\) with \(F(l,k-1)\ge F(k+1,r)\), since restricting a strategy to fewer candidates cannot raise its cost: \(F(l,k-1)\) is non-decreasing and \(F(k+1,r)\) non-increasing, so past that point \(k+F(l,k-1)\) only grows.
- Those exact values agree with the table of A276128 for \(n=1\) to \(1000\). [2]
- The statement's checkpoints are reproduced: \(C(8)=12\), \(C(100)=400\), \(\sum_{n\le100}C(n)=17575\). Further exact values are \(C(1000)=6753\), \(C(4000)=34444\), \(\sum_{n\le1000}C(n)=3120345\) and \(\sum_{n\le4000}C(n)=63753906\).
- The three facts about \(T^{*}(m)\) in Section 7 hold for every \(2\le m\le200\,000\), certifying \(\Phi\le\hat{\Phi}\) at every shift; \(\Phi(m,s)-ds\) settles at \(A(m)\) for every \(m\le256\), where the largest excess of \(\hat{\Phi}\) on the grid \(s\le2500\) is \(320\).
- \(A\) is non-decreasing inside every band, the three monotone facts of Section 9 hold over complete bands at \(N=200\,000\), and \(\widetilde{C}\) is non-decreasing.
What is still missing is a proof that at every step some globally optimal first question survives the shortlist and that the model is tight there; agreement on smaller inputs does not supply it, and Section 9 rules out band-wise exact minimisation as the lemma. The upper bound \(\widetilde{C}\ge C\) is proved; equality is verified only for \(n\le4000\).
Footnotes and References
The references below supply the background facts used above. The shift identity, the construction of the two arrays and the bounds are derived here; the audits and exact comparisons are finite checks and do not close the gap just described.
- Project Euler 328 — Lowest-cost Search. The official statement charges each question its own value, answers "lower", "higher" or "yes, that's it", and asks for the sum of the optimal worst-case costs over all n up to 200000. It supplies the checkpoints quoted in the summary above — C(1) = 0 through C(100) = 400, the sum to 100 as 17575, and the n = 8 comparison between 17 and 12 — which test an implementation without disclosing the requested total.
- OEIS A276128. The sequence is the minimum cost of determining a number among 1 to n when each guess costs its own value and the answer says low, high or correct — the C(n) of this article. Its terms begin 0, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 21, 24, 27, 30, 34, and its Maple program uses the interval recurrence of Section 2. The table of n and a(n) for n = 1 to 1000 is the independent source the exact values here were checked against.
- Wikipedia — Optimal binary search tree. The article gives the interval recurrence over all choices of root, states that its plain implementation takes O(n³) time, and records Knuth's reduction to O(n²) by monotonicity of the optimal root. It covers the weighted-sum cost only, not the worst-case variant used here.
- Wikipedia — Binary search. The article states that binary search makes ⌊log₂(n) + 1⌋ iterations of the comparison loop in the worst case, the count Section 4 compares with ⌊log₂(m)⌋.
- cp-algorithms — Sparse Table. The page states that preprocessing costs O(N log N) and a range minimum query is then answered in O(1) by combining the two blocks of length 2^i covering the range, i = ⌊log₂(length)⌋; the overlap is harmless because a minimum is unchanged when an element is counted twice. This is what
BandRMQimplements. - Wikipedia — Convex function. The article states that every real-valued affine function is convex and that the pointwise supremum of convex functions is convex, which Section 3 applies to one strategy's cost. Section 7 uses the other direction: a minimum of convex functions need not be convex.
- C++ — Euler328.cpp. The linked immutable C++ revision contains
depth_int,buildSuf,B_cand_for_q,BandRMQ, the band scan withrightCost,P,handobj, andcompute_exact_smallwith the assertions comparing the two methods. It is the implementation record for this article; the wider comparisons above are additional validation, not checks packaged there. - Python — numeric types documents integers of unlimited precision, so the Python port cannot overflow. The Java Language Specification, §4.2.1 fixes the range of
longat −2⁶³ to 2⁶³ − 1, ample by the bound above.
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());
}
}