atrophy98's blog

Looking to get better at Iterative DP problems.
By atrophy98, history, 4 years ago, In English

I am good at solving DP problems when the recurrence is apparent and the order of evaluating states follows from the recursion. However, I get stumped when the problem requires a weird order of evaluating states.

For example: 1367F2 - Летающая сортировка (сложная версия). Here the DP states are the values in the array while the order in which we evaluate them is based on the indices. I am looking to get better at these kinds of problems. I am open to suggestions / a list of practice problems.

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Brute force + memoization for the win! The big-O-constant can be slightly optimized down the road by mechanical manipulations if the order of computation becomes apparent after the implementation and the TL is tight.

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

    Yeah, this is exactly what I have been doing so far. But for example in the above problem, I couldn't come up with a recursive brute force + memoization that does better than $$$O(n^2)$$$ (which is what I did for F1).

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

      I'm not sure about that exact problem, but you can try converting your recursive approach:

      1. Take states from your recursive approach. Should be $$$O(n)$$$ states in that problem, if I understand correctly.
      2. Understand the order in which states are computed.
      3. Mechanically convert your recursion to a for loop which computes answers for all states one-by-one. The state calculation code is not changed at all, except for replacing f(x) with f_memo[x].
      4. Now try optimizing the state calculation code.

      What is your recursive approach for the problem?

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

        Yeah, ideally I should have come up with an $$$O(n)$$$ state recursion. But because of the weird order that the states need to be evaluated, I couldn't come up with one. (My function was $$$f(i,c)$$$ is the longest subsequence using elements from $$$0$$$ to $$$i$$$ with element $$$c$$$ being the element chosen last. Which has $$$O(n^2)$$$ states.)

        Again this is just an example. Usually the steps you mentioned work and that is what I have been doing so far. I am looking for problems where they don't easily apply.

        Thanks for your reply!

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

          Ah, yes, you have to change the recursive approach here. I don't know any generic way, just a set of vague ideas from past problems. One popular is to "trade states for complex transition".

          In that case, getting rid of $$$i$$$ works and keeping the rest of the state works. You will get $$$O(n)$$$ states, but each one will take $$$O(n)$$$ to calculate. Same $$$O(n^2)$$$, but much easier to apply memoization, and $$$O(n)$$$ transition is more prone to optimization than $$$O(1)$$$ transition.

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

I am also in the exact same situation. I can catch up with the recursive approach in dp problems easily, but I get slow when I try the iterative approach. But I think I have managed to get some improvement by trying to convert my recursive implementation into an iterative one. I am still not pro, but after doing this several times, I was able to think the iterative approach and solved some problems using that too.

→ Reply