### ABalobanov's blog

By ABalobanov, history, 2 months ago, Hi to everyone! I decided to create a blog with some problem which was invented by me several years ago and only simple version of it was used in municipal stage of all-russian school olympiad in Kaliningrad. I wanted to use it somewhere but now I understand that it is not possible anymore because very very similar problem with similar ideas was used in codeforces round 858(it was f1-f2). I should have used it earlier somewhere and it is my second time that I lost my problem(first was div2 C from some old round). Now I just post it here so feel free to solve it and post your solutions. Later I can write my solution. Warning: if you haven't participated in round 858 and want to do it virtually or just solve problems from there then I advice you not to read it because you may get spoilers.

Problem Comments (7)
 » Auto comment: topic has been updated by ABalobanov (previous revision, new revision, compare).
 » For me the first part (figuring out how to solve the problem with $k = 2$) was slightly more difficult rather than generalizing it for bigger $k$'s.Here is the solution: Solution for k = 2Assume for simplicity that all the integers in the array are distinct. (If there are at least two same values, we can try to take these pairs and update the answer)Let's notice (key observation) that $a + b + gcd(a, b) \ge 2 \cdot max(a, b)$. Indeed, $gcd(a, b) = gcd(a, |b - a|) \le |b - a|$. Therefore the optimal solution always contains the maximum of the array. Otherwise we can replace the minimal chosen element with the global maximum. So you should find the maximum and test it again all other values. Looks like ${O}(n \cdot (\log n + \log C))$ due to sorting and $n$ calls of $gcd$. Solution for k = 1..nAssume for simplicity that all the integers in the array are distinct. (If there are $cnt_x$ values equal to $x$, than the solution is pretty much the same, despite the fact you need to update the answer for $k = 1..cnt_x$ with $(k + 1)\cdot x$).Let's apply somehow the key observation from the first part. One can reuse it in the following way. Let $a_1 < a_2 < \dots < a_k$ be some subset of the initial array $a$. Then $a_1 + \dots + a_k + gcd(a_1, \dots, a_k) \le b + a_2 + \dots + a_k$ where $b$ is any number greater than $a_2$. Therefore the optimal solution always contains the maximal $k - 1$ values of the array.Sort the array in decreasing order and proceed with the following problem: we have to find for each $k = 2..n$ a number $a_j$ ($k \le j \le n$) such that it maximizes $a_j + gcd(a_j, g)$, where $g := gcd(a_1, \dots, a_{k - 1})$.Here we come with another observation: for almost all $k$'s the $g$ is the same. Indeed, it can only decrease while $k$ increases and, provided that, it is divided by at least 2. So every time it decreases recalculate the sum of $a_j + gcd(a_j, g)$ and every time it stays the same, just take the biggest value on the suffix. Looks like ${O}(n \log n + n \log^2 C)$, hopefully it would pass :D
•  » » Congrats! My idea was the same. About complexity: I started to work on this problem and had testcases where $O(Nlog^2C)$ was too much. There is $N(log N+log C)$ solution
•  » » » 2 months ago, # ^ | ← Rev. 2 →   Hmm, probably one can Spoileravoid calculating $gcd(a_j, g)$ from scratch each time $g$ decreases. Reusing old values in the following manner $gcd(a_j, g_{new}) = gcd(gcd(a_j, g_{old}), g_{new})$ would lead to a better complexity.Denote all distinct values of $g$ as $g_0, g_1, \dots, g_{\log C}$.Let's analyse the complexity carefully: $gcd(a, b)$ works in $O\left(\log\left(\dfrac{min(a, b)}{gcd(a, b)}\right)\right)$, so for each $a_j$ the total time can be estimated like $O\left(\log\left(\dfrac{a + g_0}{gcd(a,g_0)}\right) + \sum\limits_{j = 1}^{\log C} \log\left(\dfrac{gcd(a, g_{j-1}))}{gcd(a, g_j)}\right)\right)$ which cancels out to $O(\log (a + g_0))$, as desired.Nice problem, by the way!
•  » » » » Thanks! Yes my idea of lowering the complexity is also the same.
•  » » » » How do you think was I right publishing it now or it could still be used as it have slightly different statement and maybe (only) one of observations.
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   Idk... 1806F2 - GCD Master (hard version) indeed seems to have the same ideas, so it's rather duplicate to use your problem anywhere.