priyesh001's blog

Possible Incorrect tags on problems
By priyesh001, history, 6 years ago, In English

I have been learning DP from basic since last couple of days and I thought of solving all DP tagged problems from basic by filtering into the problem set by tag and complexity. I tried this filter (https://mirror.codeforces.com/problemset?tags=dp,1-1000) and found few problems which I didn't find related to DP. Are these incorrectly tagged as DP problem or is there something which I'm missing in these problems?

If these are incorrectly tagged as DP then would request to correctly tag the problems as it helps newbie's like me to filter problems and practice concepts.

Any help would be much appreciated.

Thanks.

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

»
6 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Either they are tagged wrongly (note that anyone who has a specified minimum rating can add a tag to a problem), or they really do have a DP solution. Or maybe a solution that doesn't seem DP to you, seems DP to someone else. For example, I consider BFS a DP approach, so I wouldn't say someone is wrong for tagging a BFS problem as DP.

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

    Interesting. How do you categorise BFS into DP ? Is it coz of the visited nodes that we store to avoid infinite re-calculation ?

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

      Let's say we want to run a BFS to find the distance from 1 to every other vertex. At first, we set dist[1] = 0, which is basically the base case of our DP. Then, what we're really doing is we set dist[u] = min(dist[u], dist[v]+1) for every edge uv. It's essentially solving a problem (what is dist[u]?) By solving a subproblem (what is dist[v]?). It really is a DP approach, isn't it?

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

        I think you are mixing up BFS and DP. They are two different paradigm for two different purpose. BFS just gives us a way to traverse a graph/tree whereas DP tells us to store the information which will be required again and again.

        Your example uses both BFS and DP. You will be using BFS to just traverse the graph in breadth first manner. Whereas storing the previously calculated distance to avoid re calculation (in other words again traversing the already traversed path) is DP. So according to me this question can be tagged with both BFS and DP. Not just BFS or Not just DP. Please correct me if wrong.

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

          DP is defined as breaking a problem into some subproblems and then combining the results of the subproblems to solve the main problem. Based on this definition, what I described could be considered as DP.

          You said what I described is not only BFS and BFS is just traversing the vertices in some order. The thing is, you can't do that traversal unless you implicitly calculate the distance from 1 to every other node. So what I described is not different from the normal BFS.

          → Reply