"Hope"

What happened in the last one ? Lemme guess — too standard or AI generated crap

jiangly is the beeeeeeeeeeeeeeeeeeeeeest![contest:400]

I changed it to a Priority Queue implementation and it TLE'd on testcase 2 lol.

Binary search solution:64571484

The first intuition should be that you either iterate over $$$2^a$$$ or iterate over $$$b^2$$$. Iterating over $$$b^2$$$ takes too long since $$$b \le 10^9$$$, but iterating over $$$2^a$$$ is fast (only around 59 candidates). For each value of $$$2^a$$$, we need to find out how many values of $$$2^b$$$ are small enough to satisfy $$$2^a \cdot b^2 \le N$$$. We can just binary search over $$$b$$$, since for any $$$2^a \cdot b^2 \le N$$$, we also know that $$$2^a \cdot (b-1)^2 \le N$$$ (you can also just use sqrt instead of binary search). Also be careful not to overflow when doing calculations, you can replace potential overflowing statements likeif (x*y > N) withif (x > N/y).

After this, the only remaining issue is the fact that some numbers are over-counted (for example, 72 is counted as both $$$2^1 * 6^2$$$ and $$$2^3 * 3^2$$$). This is because in some cases, our $$$b^2$$$ value contains factors of 2, which could equivalently be moved to $$$2^a$$$ instead. We can just ignore all values of $$$b^2$$$ which contain factors of two, which are just the even values of $$$b$$$. If we have $$$x$$$ values of $$$b$$$ for which $$$2^a \cdot b^2 \le N$$$, then we have exactly $$$\lceil \frac{x}{2} \rceil$$$ odd values of $$$b$$$.

Even I got 4 cases wrong. same code almosthttps://atcoder.jp/contests/abc400/submissions/64549973

sqrt is not reliable. At least for me, binary search gets AC while sqrt gets WA.

Same happened with my code, I think it is some floating point issue, when you take square root, and then convert to integer it can sometimes get the value k — 1 instead of k, eg. sqrt = 14.99999999 then val = int64(14.9999999) = 14 instead of expected 15

So here is some technical stuffs if you want to know why:

• There is such a thing that is called "the maximum integer that can beprecisely represented" by a floating-point number. For double (8-bit floating-point number), it is 2^53 — 1 (Smaller than 10^18). Some languages (Like JS) call this the "Max safe integer".

• So you wouldneed to switch to using long double (10-bit floating point number on GNU C++), which can represent integersprecisely up to 2^64 — 1.

try using sqrtl

dont use inbuilt sqrt function,rather use binary search to compute it, i also faced WA 3 times for it

https://atcoder.jp/contests/abc400/submissions/64532982

So here is some technical stuffs if you want to know why:

• There is such a thing that is called "the maximum integer that can beprecisely represented" by a floating-point number. For double (8-bit floating-point number), it is 2^53 — 1 (Smaller than 10^18). Some languages (Like JS) call this the "Max safe integer".

• So you wouldneed to switch to using long double (10-bit floating point number on GNU C++), which can represent integersprecisely up to 2^64 — 1. Which is also why using sqrtl works.

But I would still suggest that you use binary search instead for this lol.

it`s for C， not B

I used dijkstra too

In fact, the length of edges are 0 or 1, so 0-1 bfs can solve it with $$$O(HW)$$$.

My Dijkstra solution TLE'd on 1 testcase :(

First consider a regular array rather than a cyclic one. Each time we introduce a new number $$$C[i]$$$, we can give it a segment width of 1 and we pay $$$1+X[C[i]]$$$. We could also instead extend this segment to a previous occurrence of $$$C[i]$$$: if this previous occurrence is at index $$$j$$$ then we simply pay $$$i-j$$$ (with no X cost). However, if we do this, then any segments from $$$j+1$$$ to $$$i-1$$$ cannot extend outside of this range, and same for any segments from $$$0$$$ to $$$j-1$$$. We can maintain $$$dp[l][r]$$$ as the min cost of the subarray $$$C[l:r]$$$. If we're introducing a new number at index $$$r$$$ (currently with a segment width of 1), and we want to extend this segment to a previous occurrence of $$$C[r]$$$ at index $$$m$$$, then for all $$$l$$$ we can have $$$dp[l][r] = \min(dp[l][r], dp[l][m] + (r-m) + dp[m+1][r-1])$$$: the cost up until the previous occurrence, the cost of extending the segment, and the cost of the subarray inside of the extended segment. As an alternative, by not extending, we simply have $$$dp[l][r] = dp[l][r-1] + 1 + X[C[r]]$$$.

To deal with the cyclic array, just set C = C+C, solve with the above method, and then select the best size-N window with $$$dp[i][i+N-1]$$$ in order to check all cyclic shifts.

Solution:64571967

Now I wrote one