I’m working on a problem (Its from ICPC Finals 2023 actually called Bridging the gap ) involving a group of walkers who need to cross a bridge at night. Here are the details:

1. The bridge can only hold a limited number of walkers at a time.
2. The group has only one torch, which they need to use when crossing.
3. Each walker has a specific time they take to cross the bridge, and when a group crosses together, they have to move at the pace of the slowest walker.

Objective: Find the shortest time it takes for all walkers to cross the bridge.

Example:

Let’s say the bridge can hold 2 walkers at a time, and there are 4 walkers with crossing times of 1 minute, 2 minutes, 5 minutes, and 10 minutes.

The optimal strategy to get everyone across in the shortest time (17 minutes) could be:

1. The two fastest walkers (1 min, 2 min) cross together in 2 minutes.
2. The fastest walker (1 min) returns with the torch in 1 minute.
3. The two slowest walkers (5 min, 10 min) cross together in 10 minutes.
4. The second-fastest walker (2 min) returns with the torch in 2 minutes.
5. Finally, the two fastest walkers (1 min, 2 min) cross together again in 2 minutes.

Input:

The first line of input contains two integers, n and c:

• n (2 ≤ n ≤ 10^4) is the number of walkers.
• c (2 ≤ c ≤ 10^4) is the maximum number of walkers the bridge can hold at a time.

Sample Input (Of the previous example):
4 2
1 2 10 5
Answer: 17

Question: So, I get that this is a DP problem, but I’m having trouble pinpointing exactly which part is DP and how to structure it as a DP problem, where smaller subproblems are solved optimally as part of the bigger problem. I talked to someone who authors ICPC problems, and here’s what they said:

Basically, you can treat the forward and return trips separately, and just keep track of your debt/surplus of “banked” backwards trips. At the end you’ll need this value to be -1 (because you don’t need the last backward trip).

There are two types of trip: one where you send k slow people and c-k fast people, banking c-k-1 return trips (and there’d be no point sending fewer than c people). There’s another – which I think the video forgot about – where you just send the k fastest people to bank k-1 more return trips, which might be nice and cheap, but makes no progress on the slow people. So, my first DP (calculating cc) is to just calculate the cost of banking return trips with the fast trips only. The second DP calculates the cost of sending the slow people in groups while spending or banking some return trips. If you combine them together you’ll get the best combination of both types of trip, which sends everyone over while ending with a deficit of exactly -1.”*

But honestly, I’m still struggling to see the subproblems that make up the bigger problem clearly. Any tips to help me visualize it better?

I actually tried reading his code but still had hard time understanding it even tho its a short one. I need to understand and actually see the structure of the DP problem.

His solution to this problem is available on an opensource github repo: https://github.com/SnapDragon64/ACMFinalsSolutions/blob/master/finals2023/bridgingthegapDK.cc