杂题集二
Dual the binary search model¶
Dual to utilize the 1-degree relationship
The greedy strategy is very trivial. Without efforts we can transform this to the restriction
The purpose is to maximize
Since this is determined by three variables, and the restriction seems 2 degrees. Binary search the \(f\) seems not that simple yet.
After refering the tutorial:
We can perceive \(n\) as $$ \left\lfloor\frac{nk+k'}{k}\right\rfloor $$
Or in other words, equivalently, we can rewrite $$ a:=kn+k' = \text{times of the 1st operation} $$ $$ b:=n+m=\text{times of the 2nd operation} $$
Then \(n\) can be represented by the floor operation $$ n=\lfloor a/k\rfloor $$ The purpose $$ f(a,b) = a\cdot x + b\cdot y $$ The restriction
$$ k\frac{n(n+1)}{2}+a\cdot (b-n)\ge z $$ ( And some trivial restrictions, like \(b-n\ge 0\). )
Here, maybe we can change our points of view. Fix the value of \(f\), to find whether we can make sure for all \(a,b\) the restriction can't holds true. The boundary +1 is the final answer.
Then the always holds wrong restriction tells us
So $$ a\cdot b\le 2z $$
minimize prefix gcd sum¶
Note \(G_{n} := \gcd(a_1, \cdots, a_n)\). There's no doubt that \(G_{n}|G_{n-1}\), etc. This information doesn't help too much yet now, but give a tip in the final analysis.
Consider the case of \(N = 3\). The key is to quickly find which one is the minimum:
So when \(N\) increases, does this strategy still work well? The basic idea above, is to mimic the fixed example with \(a_1 > a\). Since the final item \(G_N\) can be omitted for its value stablility, we can mimic the previous \(N-1\) items of the fixed example, and add the \(a\) to the front. We combine the \(a_1+\gcd(a_1,a_2)\) to v.s. \(a_1'\) to get a \(\le\), then \(G_{k+1}=\gcd(a, G'_k)\) v.s. \(G'_{k}\) to get series of \(\le\).
Just try \(N=4\). Well, the inference is similar, but this time we should assume the OTHERWISE case to be \(a_1=a'>a,a_2=a''\), then we want to construct a case, whose overall contribution is even not as large as this two contribution \(a'+\gcd(a',a'')\). $$ a+\gcd(a,a')+\gcd(a,a',a'')\le a + a'-a+\gcd(a',a'') $$ But one thing suspicious is: \(a''\) can be equal to \(a\) (Not only the value but also the object is the same one). If we visit \(a\) in the the fixed example, we need a bit of modification on the previous mimicry, skip it to minic the next one item in the fixed example. The difference is, the initial version skip the information of \(a_N\), but here we pick it up and skip in advance.
OK, the \(N \ge 5\) just borrow the above strategy. We find the \(a_1\) right now. What is the best strategy subsequently?
Actually, note that \(G_n\) can be written as
So we can update the number series to apply a recursion solution. Yet now we have an \(O(N^2)\) algorithm. Can this be faster?
Tip1: \(G_{n}|G_{n-1}\) can serve as the property to analyze the time for \(G\)-change case, like potential energy. Tip2: If \(G\) is not gonna change, what can we learn?
division segmentation¶
It's easy to find in \(y-x\le D\), \(x,y\) always have a factor \(S\). So we can transform this problem into
the origin state: $$ S' = \frac{S}{S} = 1 $$ the operation: $$ x':=\frac{x}{S} \overset{\times \lambda}\mapsto \frac{y}{S}=:y' $$ the restriction: $$ y'-x'=\frac{y}{S} - \frac{x}{S} \le \lfloor\frac{D}{S}\rfloor =:D' $$ the upper boundary: $$ N':=\frac{N}{S} $$
The following statement has rewritten the notations, by ignoring the prime notation mentioned above. (This transformation somehow give up the possibility of designing the algorithm based on the characteristic of S.)
- We can say, once we take a multiple operation, it's always good to take a prime, If \(p_1\cdot p_2\) in once is ok, \(\implies\) \(p_1\) first, \(p_2\) second is also ok.
- and in the order of the decreasing. If \(\cdots p_i\cdots p_j\cdots\) is ok at the same time \(p_j = \max_{k=1}^{j-1} p_j\), \(\implies\) move the \(p_{j}\) to the leftmost is also ok. I may explain this more specificly, the method we take is - For \(k\) greater than \(j\), this move doesn't matter to them, because they can't feel any of the information has changed at all. For otherwise, considering \(y:=\prod_{k=1}^{j}p_{k}\), \(\cdots p_i\cdots p_j\cdots\) is ok means $$ y(1-\frac{1}{p_{j}})\le D $$ Since \(p_{j}\) is the largest, \((1-\frac{1}{p_{j}})\) is the largest compared to other \(p_{k}\), at the same time, \(y\) is the largest compared to other prefix products. Hence this restriction always holds, no matter how we swap the front ones for which we may just make left two items decreasing, stiil less than \(D'\).
The preparation has done.
If \(p>\sqrt{N}\), the operation can just be do once. So just find the largest one and all-in. But if a non-prime is larger than this, it's no longer necessary to assure it's a prime. So just choose \(\min\{D+1,N\}\).
Otherwise, all p should satisfy that \(p<\sqrt{N}\).
The above steps are from myself independently. The next is from the official tutorial.
THE CRITICAL OBESERVATION: \(1\cdot D \cdot 2\) is almost the final answer.
When will it have the counter case? That is \(2D>N\). For the even \(N\), it's similar. For the otherwise \(N\), as \(D\) is sufficiently large, the restriction seems very weak. The \(\{1,2,\cdots,D+1\}\) is naturally available. what can we do is just choose exactly one from them, and multiply not more than once.
The following analysis is very easy. The specific technique is number-theory-based segmentation, because it's like
$$ \min{\lfloor\frac{N}{p}\rfloor,\lfloor\frac{D}{p-1}\rfloor}\cdot p $$ The possible value of the left factor is very limited, and can be segmented for the same value.
numbers of the states analysis¶
mark contribution to the adjacent ones
The operation seems very ugly, so we guess the states are very limited.
Equivalently, the operation is to choose a prime \(p\) in \((2L, L+R]\) for the first operation or \([L+R, 2R)\) for the second. This seems devide the interval \((2L,2R)\) into two parts. So it's possible to analyze the number of statements is less than \(2R-2L + O(1)\), or something like this, here \(L,R\) are the given ones by problem statement.
In details, \([l,r]\) may split into
$$ [l,\min_{p\ge l+r} p/2 ] ,[\max_{p\le l+r} p/2, r ] $$ The common sub-interval they may have, can only be like \([\max_{p\le l+r} p/2, \min_{p\ge l+r} p/2]\), we can mark this kind of contribution to the adjacent prime between \([2L,2R]\).
Hence the key problem is to mark the prime between \([2L,2R]\). We can enumerate the value \(\le \sqrt{2R}\), besides, check whether they are the factor of elements between the interval. The time $$ 2\sum_{k\le \sqrt{2R}} \frac{R-L}{k} = O(N\log(N)), \text{here } N:=\max{R-L,\sqrt{2R}} $$ is acceptable. The precise calculation should consider \(k\) can only choose prime, so it may like \(O(N\log(\log (N)))\).