| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
Since the editorial hasn't dropped yet for today's problem E plz share your best proofs on why starting from the minimum value is optimal , couldn't prove it for a long time , iam really interested In hearing Your proofs
edit : I can't sleep without hearing an intuitive proof and it doesn't look like the editorial is dropping soon
Auto comment: topic has been updated by Axial-Tilted (previous revision, new revision, compare).
Auto comment: topic has been updated by Axial-Tilted (previous revision, new revision, compare).
Why do you need it? It's AC, move forward
Why are you making useless accounts and is afraid to use your main leave cf and move on
i'm not an expert, but i was thinking search two coprimes, in there will be the start of the new array, because gcd(a, b)=1 with a and b are coprimes.
In case there are not coprimes, probably using dp for search for a pair with the minimun gdc, and put there at the start, but i have to process more this part :/
Greedily choosing the number that makes me the smallest is always good meaning that at the beginning the smallest number will always have smallest prefix sum than any other number , how to prove it
idk man, i'm not how to be formal but i will try.
knowing that we want to minimize the sum of the array gcd(a1) + gcd(a1, a2) + gcd(a1, a2, a3) ..., we can select a pair that minimize gcd(a1, a2), because we can ensure that a result can be
min(a1, a2) + gcd(a1, a2)*(n-1) >= ans, that can you give us an approximation of the answer, so we need continue searching minimizin the gcd...
Note1: gdc(gdc(a1, a2), x) <= gdc(a1, a2), so we can assume if we have the first gcd(a1, a2) minimizes, no matter what nummber add next, will satisfy the previous property
Note2: if you find a coprime pair, the answer will be min(a1, a2) + (n-1), because no matter what will be the next number, the gcd(a1, 1) = 1.
-------------------------- I means, this can be a route?
Ok here's my take:
For n = 3, let a[1] < a[2] < a[3]. We will prove that sorting them is optimal.
Define f(p[]) = the value of the expression in the statement when we order them using the permutation p[].
Let p[] be the optimal permutation. We will show that it has to have p[1] = 1. In other words, having the smallest number first is the best.
If p[1] > p[2], f(p[]) > f(p[] with p[1] and p[2] swapped) for obvious reasons by comparing the sums term by term, there only being a difference in the first term. As such, p[1] < p[2] from now on.
If p[1] != 1, we must have p[3] = 1, so p[] = {2, 3, 1}. Then, a[2] >= a[1] + (a[1], a[2]), so, using that inequality, we get f(p[]) < f({1, 2, 3}) by writing it all out.
As such, for n = 3, leaving the smallest first is optimal.
For n = 4, we assume the same things, and we already know that p[1] is in {1, 2} because the minimum among the first three has to be in the first position. So, if p[1] = 2, we must have p[4] = 1. We will prove f(p[]) > f({1, 2, p[2], p[3]}):
By writing it out and removing the last, equal terms, we get a[2] + (a[2], a[p[2]]) + (a[2], a[p[2]], a[p[3]]) > a[1] + (a[1], a[2]), (a[1], a[2], a[p[2]]), which is true for the same reasons as n = 3's equation!
For the rest of the n, the proof is similar inductively. It all boils down to the following lemma:
"If a < b, then b >= a + (a, b)"
As such, for any length of the sequence n, the minimum number has to be placed first.
PS: I left a lot of things unproven. Try to prove them yourself (or ask ChatGPT idc). (This was definitely not because I was too lazy!)
I came up with something alitte bit similar let's take any two numbers X , Y , X < Y and prove that taking X will atleast improve the answer by 1
Let g denote the gcd(X,Y) and let's write X as p*g and Y as q*g since p < q then (p+1)*g <= Y meaning if we take X then Y we have a prefix already <= Y and ending with g which allows for better upcoming options with already less prefix sum
proof that having g will open up for better options than Y , lets take any number and call it C lets also denote g1 , g2 as gcd(g , C) and gcd(Y , C) respectively since g is a subset of Y interms of the prime divisors then g1 will never have an extra prime divisor over g2 as everything that exists in g already exists in Y
Here's a good proof
https://codeforces.me/blog/entry/134039?#comment-1200375
It just follows from picking the value that produces the smallest gcd with the previous elements. Gcd(0,x) = x so we pick smallest x.
The biggest intuitive proof is
Proof by AC.