Please read the new rule regarding the restriction on the use of AI tools. ×

yeeeet's blog

Constructive Algorithms question that I have no idea how to solve
By yeeeet, history, 4 years ago, In English

After getting destroyed by the problem mentioned in this blog

I decided to get revenge on the problemsetter(dvdg6566) by setting a problem related to his that he couldn't solve :). After thinking a while I came up with this problem. Given two integers N and I, construct a sequence of non-negative integers with length N with inequality I where inequality is defined as

$$$I = \sum\limits_{i=1}^N \bigg( \sum\limits_{j=i}^N rangemax(i,j) \bigg)$$$

But after thinking a while again, I realized I couldn't solve it either. I could only construct a solution for $$$I>=(2*(n-1)*(n-2))$$$ but for smaller I, I have no idea how to do it. Any help would be appreciated thanks!.

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

»
4 years ago, # |
← Rev. 3   Vote: I like it +67 Vote: I do not like it

Zane you are a simp

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

    Could you shed more light on how the transition would look?

    I'm unable to wrap my head around the fact that the position of maxvalue in the length sized array isn't necessary.

    Thank you!

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

      Transition:

      Option 1: We don't take the max value. then $$$dp(i,j,k) = dp(i,j,k-1)$$$.

      Option 2: We take the max value. Iterating all possible positions, we can find the remaining $$$I$$$ to be spread over left and right side. Try breaking in all ways.

      Hence transition is $$$O(N^3)$$$.

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

    If the blog gets more upvotes than your comment I will go solve the original problem

    → Reply