codingp110's blog

Help required on a dp problem
By codingp110, history, 3 weeks ago, In English

Hi all! Please provide some hints for this problem: https://mirror.codeforces.com/gym/524325/problem/C. I am able to come up with a recursive solution for this problem but that is ofcourse giving TLE and I think memoization cannot be done seeing the bounds on the coordinates. I would be very grateful if you could point me to questions which would help build the intuition for solving this one.

Question Summary:

Given coordinates of Alice and Bob and N falling apples we need to calculate the minimum distance(Manhattan) to be covered by Alice and Bob in total to catch all apples. The apples must be caught sequentially that is apple at i+1th index cannot be caught before catching apple at index i. Assume Bob and Alice can cover distances instantaneously. The number of test cases can be at max 10 , apples at max 2000 and coordinates are non negative and bounded by 1e9.

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to access the question... Can you give another link that works because the link is forwarding me to this page only.

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

    The problem was from a gym could that be a reason that the link does not work? Added the question summary in the desc till I find a way to link the original problem.

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

      The thing you wrote is confusing and incomplete, please send a picture from the statement

      → Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Hint : Try to consider dp[n+1][n+1] array, where x index represent bob last position(means xth apple was captured by bob) and y index represent alice last position(means yth apple was captured by alice). 0 index means the original position of bob/alice.

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

    how are you familiar with dp, since newbie does not have to cover dp problems?

    → Reply