adaptatron's blog

[Tutorial] : Smart people do worse on this problem
By adaptatron, 12 days ago, In English

You are given an array consisting of $$$n$$$ positive integers. You are standing at the first index, and you want to reach the last index. You can make as many forward jumps as you want. If you jump from index $$$i$$$ to $$$j$$$ your profit is $$$(j - i) \cdot a[i]$$$. What is the maximum total sum of profits that you can achieve?

I created a blog on this topic discussing how the DP optimization for this problem is easier than you think or harder than you think.

https://cfstep.com/training/tutorials/dp/the-hardest-easy-dp-problem/

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

»
12 days ago, # |
  Vote: I like it +4 Vote: I do not like it

I solved it in an instant without dp.
here, consider the sum of j-i = n-1 and its some kind of length, a common trick is, we assign i~j-1 value of ai, and we maximum the sum of those values. to do this, we find the prefix maximum of every i(that is the biggest one that it can reaches i, certainly no midterm transfer) and sum it up(certainly, without the last).

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

I realised quickly (and proved) that it's optimal to move to the next larger value. I believe it's just a greedy problem.

→ Reply
»
12 days ago, # |
  Vote: I like it -11 Vote: I do not like it

how can you comment for smart people while you yourself are a newbie.

→ Reply
»
12 days ago, # |
  Vote: I like it +81 Vote: I do not like it

Obvious CHT

→ Reply
  • »
    »
    12 days ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    good to know I wasn't the only one whose first thought was bashing CHT lol

    → Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

lmao this is barely 1000 rated greedy problem

→ Reply
»
12 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Isn't this just adding the maximum a[i] in every prefix in O(n)? You can think of always doing the jumps 1 by 1, instead of thinking where exactly you will end up at jumping from position i.

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

    Just use CHT, why use brain when you can easily do it the hard way.

    → Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I remember this from the leetcode contest {link}. It is $$$1750$$$-rated on lc, so maybe it would be $$$1100$$$ or so on cf.

Imo, calling it a $$$dp$$$ problem is like saying finding the $$$min$$$ of an array is $$$dp$$$ with transitions $$$dp_i = min(a_i, dp_{i + 1})$$$

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

    Yes, it's not a DP problem per se and can be solved via Greedy (and that's what I mention at the end of the blog in the spoiler section). Of course, I couldn't mention Greedy keyword in the title. The point was to narrow the reader's vision so that they get too involved in the DP keywords that they fail to see the obvious greedy solution (just like the recent Veritasium video where they reword the problem in a way that people become biased).

    Maybe the Codeforces crowd is different, but from the LeetCode comments section and from the approximately 30 people that I've asked this problem to, most of them fail to see the greedy once you show them the $$$O(n^2)$$$ DP solution. But if you tell them it was a LeetCode medium problem and it doesn't require DP at all, they immediately come up with the greedy solution.

    → Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Formula screams CHT but I believe the answer is just a simple greedy?

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how this can be solved using CHT?

→ Reply