Help required on a dp problem

Revision en4, by codingp110, 2024-05-23 20:14:58

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.

Tags dp problem, need help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English codingp110 2024-05-23 20:14:58 73
en3 English codingp110 2024-05-23 19:11:43 3 Tiny change: 'on Summary\nGiven co' -> 'on Summary:\n\nGiven co'
en2 English codingp110 2024-05-23 19:11:03 485
en1 English codingp110 2024-05-23 17:23:07 419 Initial revision (published)