halyavin's blog

By halyavin, history, 7 years ago, In English

The problem D in the latest Open Cup involves function f(n) which is defined as the minimum sum of sequence b1, ..., bk such that any sequence a1, ..., al with sum less than or equal to n can be dominated by some subsequence of b. One sequence dominates the other, if they have the same length any every element of the first sequence greater than or equal to corresponding element of the second sequence. It turns out that f(n) = n + f(k) + f(n − 1 − k) where k = [(n − 1) / 2]. But why? If this equation still keeps you up at night, you can finally sleep well now. I have found a wonderful proof of this statement which fits the bounds of this site.

Two sides of the proof

Let us construct the b sequence first.

For brevity, we will say that sequence b covers sequence a, if some subsequence of b dominates a.

Theorem 1. Let B1 be a sequence that covers all sequences with sum less than or equal to k. Let B2 be a sequence that covers all sequences with sum less than or equal to l. Let n = k + l + 1. Then sequence B1, n, B2 covers all sequences with sum less than or equal to n.

Proof. Let a1, ..., as be a sequence with sum less than or equal to n. Let t be the largest index such that a1 + ... + atk. Then the first t elements of sequence a can be dominated by some subsequence of B1. If t = s we don't need to go any further. Otherwise, the element at + 1 can be dominated by n and the rest of the sequence can be dominated by a subsequence of B2 since its sum is less than of equal to n − (a1 + ... + at + 1) ≤ nk − 1 = l where we used that the sum of first t + 1 elements of a is strictly greater than k by definition of t.

From Theorem 1 follows that f(n) ≤ mink(n + f(k) + f(n − 1 − k)).

Simple enough, but how to prove the lower bound?

First of all, any covering sequence must cover sequence with single element a1 = n and so must have element greater than or equal to n.

Theorem 2. Let B = B1, m, B2 be an arbitrary split of a sequence that covers all sequences with sum less than or equal to n. Let k be the largest number such that all sequences with sum less than or equal to k are covered by B1. Let l be the largest number such that all sequences with sum less than of equal to l are covered by B2. Then k + ln − 1.

Proof. Assume k + ln − 2. By definition of k there is sequence A1 with sum k + 1 which is not covered by B1. By definition of l there is sequence A2 with sum l + 1 which is not covered by B2. Let us consider sequence A1, A2. It has sum k + 1 + l + 1 ≤ n. Since A1 is not covered by B1, the latest element of A1 must be covered by m or element to the right of it. By the same logic, the first element of A2 must be covered by m or element to the left of it. But the latest element of A1 must be covered by element of B to the left of element covering the first element of A2. We arrive at the contradiction and so k + ln − 1.

If we split the sequence B at element greater than or equal to n, from Theorem 2 follows f(n) ≥ n + f(k) + f(l) where k + ln − 1. Since f(n) is non-decreasing we can set l = n − 1 − k and get f(n) ≥ mink(n + f(k) + f(n − 1 − k)).

Combining results from both theorems, we have f(n) = mink(n + f(k) + f(n − 1 − k)). Q.E.D.

Piece of convex cake

But, sir, you have got the wrong formula. The only way they can be the same, if minimum over k is always happens to be in the middle. Like in the case of convex functions. Well, let us prove f(n) is convex then. Stay back, I am going to use induction.

Theorem 3.

  1. For all n ≥ 1. f(n) = n + f(k) + f(n − 1 − k) where k = [(n − 1) / 2].
  2. For all n ≥ 2. f(n) − f(n − 1) ≥ f(n − 1) − f(n − 2).

Proof. We have f(0) = 0, f(1) = 1, f(2) = 3 which prove the theorem for n ≤ 2. We have the basis of induction, now let us prove the induction step. Assume the theorem is proved for all nm. Let us prove it for n = m + 1.

The first statement is the consequence of the second for nm. If k + 1 ≤ m − (k + 1), we have f(k) + f(mk) = f(k) + f(m − (k + 1)) + (f(mk) − f(m − (k + 1))) ≥ f(k) + f(m − (k + 1)) + (f(k + 1) − f(k)) = f(k + 1) + f(m − (k + 1)). So if we increase k starting from 1, the sum f(k) + f(mk) decreases or stays the same until k = [m/2].

In order to prove the second statement, we need to consider two cases.

First case, m = 2t, t ≥ 1. The first difference is equal to f(m + 1) − f(m) = (m + 1 + 2f(t)) − (m + f(t) + f(t − 1)) = 1 + f(t) − f(t − 1). The second difference is equal to f(m) − f(m − 1) = (m + f(t) + f(t − 1)) − (m − 1 + 2f(t − 1)) = 1 + f(t) − f(t − 1). The differences coincide which proves the second statement.

Second case. m = 2t + 1, t ≥ 1. The first difference is equal to f(m + 1) − f(m) = (m + 1 + f(t + 1) + f(t)) − (m + 2f(t)) = 1 + f(t + 1) − f(t). The second difference is equal to f(m) − f(m − 1) = (m + 2f(t)) − (m − 1 + f(t) + f(t − 1)) = 1 + f(t) − f(t − 1). The first difference is greater than or equal to the second due to induction assumption for t + 1 ≤ m which we can apply since t + 1 ≥ 2.

This completes the proof of the theorem and allows us to remove min from the formula.

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

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Nice! Good to know it exists :D. I actually even read it ;p. By the way I am even more interested in proof of B that was harder to believe.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I still don't have a proof, this is some random thoughts.

    Consider a standard s-t maxflow problem. Write it as a LP problem and take its dual. It turns out that the dual is the following:

    Assign labels to the vertices. label(s) = 1, label(t) = 0, and for other vertices the labels are some real values. The cost of this labeling is defined as the sum of (label(se) - label(te)) * capacitye over all edges e (here se, te are the endpoints of e). What is the minimum possible cost of the labeling?

    Then, we can prove that the cost becomes the smallest when the labels are 0/1 valued, and it leads to the proof of maxflow-mincut theorem.

    Now let's return to the original problem. The dual is quite similar:

    Assign two labels to the vertices, for vertex v define W(v) and O(v). W(Ws) = O(Os) = 1, W(Wt) = O(Ot) = 0 must be satisfied. The cost is the sum of max(|O(e1) - O(e2)|, |W(e1) - W(e2)|) * capacitye over all edges e (here e1, e2 are the endpoints of e).

    Now, here's the unproved part: believe that the cost becomes the smallest when the labels are 0/1 valued. If we assume this, it can be restated as:

    Choose a subset of edges. This subset is called a cut if it cuts Ws and Wt, and at the same time it cuts Os and Ot. What is the cut of minimum cost?

    Then it's easy to see that the solution with two flows is correct.

»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

One friend of mine find in OEIS (I think) that this sequence coincide with worst case comparison needed to sort an array of n integers (using an algorithm based on comparisons, of course ;)

Is it any way to extend your ideas to prove this?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I don't think so, as the problem of optimal comparison sorting is yet unsolved even for small n. The smallest n for which the answer is unknown is 16.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      mareksom is writing master thesis whose main goal is to determine whether optimal number of comparisons for 16 elements is 45 or 46 :D. Under guidance of Marcin Peczarski that is mentioned many times in references :P.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        What a coincidence: I was thinking about solving the very same problem in my master thesis :) Though I haven't yet selected a topic. And Marcin's paper was in fact the one which inspired me and instigated to think over some refinements for their approach.

        Does Marek already have an answer?

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +35 Vote: I do not like it

          No, I still don't know the answer. And probably it will take me at least a year to find it. I am concentrated on parallelization of existing algorithms to make them work efficiently on a supercomputer. It's really hard to come up with real improvements to the core algorithm, because Marcin Peczarski has already done a great job optimizing it.

          It's cool that there is some other student interested in this topic : )

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I didn't know that, I checked the sequence in OEIS and you were right. It states for maximal number of comparisons for sorting n elements by binary insertion.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    By the way, it reminded me more peculiar coincidence.

    When we went to a programming camp last week we found a shop that sells spicy noodles. Nine different spiciness were available there: 1, 3, 5, 8, 11, 15, 20, 25, 30.

    OEIS 49706