helloworld1102's blog

How to solve 1485A - Add and Divide using DP ?

By helloworld1102, history, 3 years ago, In English

Hello all, this is my first ever blog on codeforces . If i make some mistakes, please forgive me .

Actually i am thinking on the 1485A - Add and Divide and its tutorial is using greedy approach.

But i have read that all optimisation problems can be solved using DP through its optimal substructure and overlapping property .

I am thinking this problem for quite a long time using DP .

So, please tell me how we will define the state for DP and transitions in DP for this problem as they are the most creative part for me .

So how you actually think to make it all easier ? (to differentiate between DP and greedy ) and when to use which technique ?

And , please tell how you decide which problem to solve using greedy and which using DP as both are working on optimisation problems . ------------------

So how you actually differentiate so fast in contest ?

Your answers and clarifications will be very helpful to me .

Thank you all.

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

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

But i have read that all optimisation problems can be solved using DP through its optimal substructure and overlapping property .

Sure, if there are overlapping subproblems. But on this problem there aren't any (at least not any reasonable ones that help solve with given bounds)...

Also, you differentiate by if there are many overlapping subproblems.

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

    There are at most $$$1 + 2 \sqrt{a}$$$ distinct values that $$$a$$$ can be reduced to, which is a form of overlapping that, combined with fore-knowledge that $$$b$$$ is not increased more than $$$1 + \log_2 a$$$ times in any optimal solution, creates a state-space that's getting close to small enough. If you're willing to consider Dijkstra's algorithm (or BFS) a form of DP that can be terminated early, that probably fits within the time limit by virtue of just not exploring all that much of the (too-large) state space before exiting.

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

      Very sorry, I didn't get it ? What are you trying to tell as I am thinking this problem in defining the states and its transitions. Because i have seen in topcoder tutorials,exactly goes through this approach to solve through DP.

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

        I'm implicitly taking the "natural" choice that a state consists of an ordered pair $$$(a, b)$$$ of the two numbers in the problem, after applying some number of operations. The transitions then correspond to the two types of operations.

        My comment is based on the observation that the identity $$$\lfloor \frac{\lfloor \frac{a}{x} \rfloor}{y} \rfloor = \lfloor \frac{a}{x \cdot y} \rfloor$$$ for positive integers implies that the set of reachable values of $$$a$$$ is not terribly large, which somewhat undermines SuperJ6's claim that there are "not any reasonable [overlapping subproblems]" applicable to this problem. I do not mean to suggest the DP approaches to the problem are at all pragmatic.

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

So how you actually differentiate so fast in contest ?

It's a Div 2A, it won't be DP.

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

"(to differentiate between DP and greedy ) and when to use which technique ?"

Usually you should use DP when you perceive that you need to make a brute force to solve the problem and this brute force will cause TLE for you, when this happens, you can try to think about DP.

→ Reply