Side Trip - What should I use here?

General Questions
#1

I have been trying to solve this problem, but I don’t know how should I approach this problem. I think this is a graph problem, then again I am not sure what algorithm should I use here. Can someone give me a hint or point me in the right direction which algorithm should I use?

Problem Statement

One day in the year 3019, a high school student named Moreno is going to school as usual. The town he lives in can be represented as a straight line stretching from east to west. Moreno’s house is at coordinate 0, and his school is at S. There are N stores and M teleport stations between the house and the school. Counting from the westernmost point, the i th (1 ≤ i ≤ N) store is at coordinate ai, and the j th (1 ≤ j ≤ M) teleport station is at bj. He can move between any two teleport stations in zero seconds.

When he walks, it takes one second to walk one coordinate.

Moreno is leaving home at time 0, measured in seconds.

(Note that the unit of time is always ‘seconds’ in this problem.)

He has to get to school no later than the time T.

If he gets to school at time T + 1 or later, it will be treated as being late for school, and he will be kicked out of school.

However, he really likes taking side trips, so he wants to shop at as many stores as possible on the way to school.

He can only shop at a store if he is at the same coordinate as the store.

It takes one second to shop at each store.

Calculate the maximum number of stores P that Moreno can shop at without being late for school.

Also calculate the minimum time Q it will take for Moreno to get to school when he shops at P stores along the way.

Input Rules

The format of the standard input is as below:

N M S T

a1 a2 … aN

b1 b2 … bM

Restrictions:

  • 1 ≤ N ≤ 2000, Integer
  • 2 ≤ M ≤ 2000, Integer
  • 1 ≤ S ≤ 109, Integer
  • 1 ≤ T ≤ 109, Integer
  • 1 ≤ a1 < a2 < a3 < … < aN < S, Integer
  • 1 ≤ b1 < b2 < b3 < … < bM < S, Integer
  • b1 < a1 and aN < bM
  • The maximum number of buildings (houses, schools, stores, teleport stations) on the same coordinate is 1.
  • No inputs in which Moreno will be late for school no matter which way he moves are given.

Output Rules

The format of the standard output is as below:

P Q

  • P: The maximum number of stores Moreno can shop at without being late for school.
  • Q: The minimum time for Moreno to get to school when he shops at P stores along the way.

Input & Output samples

Sample 1

Sample Input 1

3 3 20 16

3 6 11

2 7 15

Sample Output 1

2 13

The best series of movements is as follows.

  • Walk to the first store, shop there, then walk back to the first teleport station. (time: 5)
  • Teleport to the second teleport station. (time: 5)
  • Walk to the second store, shop there, then walk back to the second teleport station. (time: 8)
  • Teleport to the third teleport station. (time: 8)
  • Walk to the school. (time: 13)

If he shops at the third store, neither of the other two stores can be visited.

Sample 2

Sample Input 2

2 2 10 14

4 6

2 8

Sample Output 2

2 12

It is optimal for him to walk straight to the school, shopping at all the stores as he passes by.

Sample 3

Sample Input 3

7 2 10 2

2 3 4 5 6 7 8

1 9

Sample Output 3

0 2

There are many stores, but unfortunately he has no time to shop.

#2

I agree that it’s a graph problem. I think you can just run a dijkstra on the problem.

#3

But using Dijkstra, I can find the shortest path from home to school. But then how do I maximize the number of visited stores, To maximize the number of stores means I might have to take a longer path, rather than the shortest. As you can see in the Sample test Case 1, the shortest path is of 7, but we choose to take a path of 13.
Then again there is the problem to reach the school in the minimum time possible while shopping at P stores. I don’t see how can I use Dijkstra here.

#4

First, split the line into segments between consecutive teleporters. Let C_i[j] be the minimum time it takes to visit j stores in the i-th segment. Since it’s optimal to visit either the whole segment or a prefix and then a suffix, we can compute each C_i[j] using a sliding window in \mathcal O(N^2) time. Notice how C_i[j] < C_i[j + 1].

Next, let dp[i][j] be the minimum time it takes to visit j stores in total from the first i segments. The following recurrence holds:

dp[i][j] = \min_{k \leq j}(dp[i - 1][k] + C_i[j - k])

You can then use your favourite DP optimization (monotone stack, CHT, D&C, etc.) to speed this up and run in \mathcal O(NM) time. I’m not sure whether there’s a simpler way, but there probably is.

1 Like
#5

Thank you for your solution it helped me a lot. It took me quite a lot of time to make sense of what you said, first I gave up on it, but then I tried again, and yes now it makes complete sense to me.
The solution you are talking about would run in O(M2N), but you have also mentioned some optimization techniques that I have never heard about.
Can you please give some good resources to learn any of those optimizations?

#6
#7

I don’t see how any of these optimizations would apply. Isn’t this just a knapsack problem?

#8

Hello, I used the partition DP here, but the complexity of that is O(N*M2). How do I optimize it? Any ideas?

#include<bits/stdc++.h>
using namespace std;
#define ar array
typedef long long ll;
const ll Mxn = 2e3+2, INF = 1e15;
ll n, m, s, t;
ll store[Mxn], tele[Mxn];
ll cost[Mxn][Mxn], dp[Mxn][Mxn];

void calcPreSuf(int st, int end, int i, vector<ll> &pre, vector<ll> &suf){
    pre.push_back(0),suf.push_back(0);
    for(int j=st;j<end;j++){
        pre.push_back(min(2*(store[j] - tele[i]), (store[j] - tele[i] + tele[i+1] - store[j])) + j-st+1);
    }
    for(int j=end-1;j>=st;j--){
        suf.push_back(min(2*(tele[i+1] - store[j]), (tele[i+1] - store[j] + store[j] - tele[i])) + end - j);
    }
}

int main(){
    cin >> n >> m >> s >> t;
    for(int i=0;i<n;i++) cin >> store[i];
    for(int i=0;i<m;i++) cin >> tele[i];

    for(int i=0;i<Mxn;i++){
        for(int j=0;j<Mxn;j++){
            if(i == 0)
                cost[i][j] = 0;
            else if(j == 0)
                cost[i][j] = 0;
            else
                cost[i][j] = INF;
            dp[i][j] = INF;
        }
    }
    int st=0,end=0;
    for(int i=0;i<m;i++){
        while(end < n and store[end] < tele[i+1])
            end++;
        vector<ll> pre,suf;
        calcPreSuf(st,end,i, pre, suf);

        for(int j=1;j<=end-st;j++){
            for(int k=0;k<=j;k++){
                cost[i+1][j] = min(cost[i+1][j], pre[k] + suf[j-k]);
            }
        }
        st = end;
    }

    for(int i=0;i<m;i++){
        for(int j=0;j<=n;j++){
            if(i == 0 and j == 0)
                dp[i][j] = 0;
            else if(i == 0)
                dp[i][j] = INF;
            else if(j == 0)
                dp[i][j] = 0;
            else{
                dp[i][j] = INF;
                for(int k=0;k<=j;k++){
                    dp[i][j] = min(dp[i][j], dp[i-1][k] + cost[i][j-k]);
                }
            }
        }
    }

    ll rt=tele[0] + s - tele[m-1],q = 0, p=0;
    for(int i=1;i<=n;i++){
        if(rt + dp[m-1][i] <= t){
            q = dp[m-1][i];
            p = i;
        }
    }
    cout << p << ' ' << q+rt << '\n';
}

I couldn’t figure out, how to apply any of the above optimizations here.

#9

if you make the lower bound on k larger then this code will be a lot faster.

#10

Can you clarify, how should I do that?

#11

You don’t need to consider costs equal to INF.