neal's blog

Educational Round 83 problem E (Array Shrinking): O(n log n) solution
By neal, 5 years ago, In English

I believe I have an $$$O(n \log n)$$$ solution to 1312E - Array Shrinking. Here's the code: 72938462

The main idea is to find all segments of the array that can be reduced to a single number. We do that via this DP:

reduce(start, x) = the end of the range starting at start that can be reduced to the single value x, or -1 if no such range exists. You can then solve this DP with the recurrence reduce(start, x + 1) = reduce(reduce(start, x), x).

The key claim is that there can be at most $$$n \log n$$$ such segments, no matter what the $$$a_i$$$ are. In fact, the maximum possible number of such segments seems to be exactly the number of segments when all of the $$$a_i$$$ are equal. This version of the code adds an assertion to test this claim: 72938781. It passes every small random test case I've given it.

Unfortunately I don't have a proof of this claim yet, but it feels like there should be a nice proof. Can anyone come up with something? One approach could be to prove a slightly stronger claim, that there are at most $$$n \log n$$$ segments where $$$\displaystyle \sum{2^{a_i}}$$$ is a power of two.

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

Comments Comments (12)
| Write comment?
»
5 years ago, # |
  Vote: I like it +213 Vote: I do not like it

This problem looks similar to problem WEAPONS from SnackDown 2017 Onsite Finals. Its editorial indeed proves that the number of reducible segments is $$$O(n \log n)$$$.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -172 Vote: I do not like it

    Have a good day my idol <3

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it -69 Vote: I do not like it

      Why I get so many downvotes, I just want to wish him a good day ;-;

      I have insprirational feeling when seeing GrandMaster Rating Graph. And I want to be a good coder one day like those the guys (maybe Master is enough). So cant I call him or any GM else as my idol ? My definition for idol is just like that, I dont mean anything. Sorry if I mind you guys T_T

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Dude can you stop commenting so much? No one gives a fuck about your feelings

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Do not make an idol for yourself, whether in the shape of anything in the heavens above or on the earth below or in the waters under the earth.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 4   Vote: I like it +13 Vote: I do not like it

          Oh I am so sorry, I think the better word I should say is something like Admire someone. I dont good at English but now I think idol is not what I should say, sorry.

          Is idol meaning something bad ? If it is I dont really want to say so. I just admire him and thinking about those the people who are high-ranker must have been worked so hard, so I say Wish a good day.

          How can I say it, like proud and want to slowly improve myself to get closer to the one who are better than me a far distance, like feel admire and have motivation not giving up on the Competitive Programming way <3

          What should I better say for the same meaning. Thank you.

          Sorry everyone, it is my fault for bad English knowledge. Have great days coders <3

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Smh, your english is fine. Don't have an idol, work hard to be good yourself so you don't have to look up to someone else.

            → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    The argument in that editorial can be slightly modified to verify the conjecture that the maximum number of reducible segments is achieved when all of the $$$ a_i $$$ are equal.

    Let $$$ h(n) $$$ denote the number of reducible segments in an array of length $$$ n $$$ with all $$$ a_i $$$ equal to one another and let $$$ f(n) $$$ denote the maximum possible number of reducible segments in an array of length $$$ n $$$. Then, the block compression argument from the linked editorial shows that for $$$ n > 0 $$$,

    $$$ f(n) \leq \max_{1 \leq k \leq n} f(n + \lfloor \frac{k}{2} \rfloor - k) + h(k) - h(\lfloor \frac{k}{2} \rfloor), $$$

    where $$$ h(k) $$$ is the number of (removed) internal good intervals in a to-be-compressed block of length $$$k$$$, and $$$ h(\lfloor \frac{k}{2} \rfloor) $$$ is the number of (added) internal good intervals in the now-compressed block. Using the fact that $$$ h(n) - h(n-1) = 1 + \lfloor \log_2 n \rfloor $$$ is a nondecreasing sequence, it follows that for $$$ k \leq n $$$,

    $$$ \begin{array}{rl} h(k) - h(\lfloor \frac{k}{2} \rfloor) & = \sum_{i=1}^{k - \lfloor \frac{k}{2} \rfloor} h(\lfloor \frac{k}{2} \rfloor + i) - h(\lfloor \frac{k}{2} \rfloor + i - 1) \\ & \leq \sum_{i=1}^{k - \lfloor \frac{k}{2} \rfloor} h(n - k + \lfloor \frac{k}{2} \rfloor + i) - h(n - k + \lfloor \frac{k}{2} \rfloor + i - 1) \\ & = h(n - k + k) - h(n + \lfloor \frac{k}{2} \rfloor - k) \\ & = h(n) - h(n + \lfloor \frac{k}{2} \rfloor - k). \end{array} $$$

    Substituting this into the inequality for $$$ f $$$ above allows one to easily prove by induction that $$$ f(n) \leq h(n) $$$, which is to say that no array has more reducible segments than one of the same size with all $$$ a_i $$$ equal to one another.

    → Reply
»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Maybe this is what ur looking for?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I saw this link in the comments for the round. That's a slightly different problem, so the $$$O(n \log n)$$$ solutions from there don't apply to this one.

    The $$$a_i$$$ in that problem are only up to 40, so the first solution uses the assumption that the eventual numbers won't exceed $$$40 + \log n$$$ (they use a constant of 70). In this problem, the $$$a_i$$$ can be bigger than $$$n$$$, so that idea doesn't apply. For any single start point you can have way more than $$$\log n$$$ possible segments:

    1 1 2 3 4 5 6 ...

    The other difference with the USACO problem is the goal is to maximize the single largest number at the end. This leads to the greedy idea described in the second solution in your link, but that idea doesn't apply when trying to minimize the length.

    Gennady's link above is correct. I suspect there's another proof using the $$$\displaystyle \sum{2^{a_i}}$$$ idea.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone share the code of Fusing Weapons which tourist have mentioned.Thanks in Advance!

→ Reply