Axial-Tilted's blog

Today problem E , SPOILER
By Axial-Tilted, history, 2 months ago, In English

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

  • Vote: I like it
  • +23
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by Axial-Tilted (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Axial-Tilted (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
  Vote: I like it -46 Vote: I do not like it

Why do you need it? It's AC, move forward

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Why are you making useless accounts and is afraid to use your main leave cf and move on

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :/

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 2   Vote: I like it +7 Vote: I do not like 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?

      → Reply
»
2 months ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

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!)

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Here's a good proof

→ Reply
»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

https://codeforces.me/blog/entry/134039?#comment-1200375

→ Reply
»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

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.

→ Reply
»
2 months ago, # |
  Vote: I like it -25 Vote: I do not like it

The biggest intuitive proof is

Spoiler
→ Reply