Relics Collection - Editorial

About the Problem

Setter(s) Aswin
Tester(s) Vichitr Gandas
Difficulty Easy Medium
Topics DP
Practice Link
Contest Link

Solution Idea

There are multiple approaches to solve it. DP comes in the mind first. We wrote two dp solutions. First is O(n*n*k) and another is O(n*k*k) . We intended to pass only second one.

Approach 1: O(n*n*k) DP

Maintain current index, previous index and skips left. Each each step you will two choices: either move to next index with travelling the distance between current & next relic or you can use a skip. When we have reached idx > n, ans = 0 because we have either skipped all the left over relics or already collected all. And dp transitions will be as following -
dp(idx, prev, skips) = min(dp(idx+1, idx, skips)+dist(idx, idx+1), dp(idx+1, prev, skips-1))
dp(idx, prev, skips) = 0 for idx > n .

Approach 2: O(n*k*k) DP

The above solution can be improved. We need to care about only previous k relics because we can’t skip more than k . So we need to maintain only index and skips. At each state, we will loop over skips & recur. Here dp transitions will be as following -
dp(idx, skips) = \min_{\forall i \in [0, skips]} (dp(idx+i+1, skips-i)+dist(idx, idx+i+1)) .
dp(idx, skips) = 0 for idx + skips \ge n .

Complexity Analysis

Time Complexity: \mathcal{O}(n *k * k) for second dp solution.
Space Complexity: \mathcal{O}(n*k) for storing the dp of size n*k.

Codes

Setter's Code
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
typedef long long int ll;
using namespace std;
ll dp[100005][105];
ll inline dist(ll x1,ll y1,ll x2,ll y2)
{
    return (abs(x2-x1)+abs(y2-y1));
}
int main()
{
    int t; cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        for(int i=0;i<=n;++i)
            for(int j=0;j<=k;++j)
                dp[i][j]=LLONG_MAX;
        dp[0][0]=0;
        vector<ll> x(n+1),y(n+1);
        x[0]=0;
        y[0]=0;
        for(int i=1;i<=n;++i)
            cin>>x[i]>>y[i];
        
        for(int i=1;i<=n;++i)
        {
            for(int j=0;j<=k;++j)
            {
                for(int l=0;l<=j;++l)
                {
                    int skip=j-l;
                    int ind= i-l-1;
                    if(ind>=0 && skip>=0)
                        if(dp[ind][skip]!=LLONG_MAX)
                        {
                            // cerr<<dp[i][j] <<" "<<dp[ind][skip] + dist(x[i],y[i],x[ind],y[ind])<<endl;
                            dp[i][j] = min(dp[i][j], dp[ind][skip] + dist(x[i],y[i],x[ind],y[ind]));
                        }
                }
            }
        }
        ll ans=LLONG_MAX;
        for(int i=n;i>=(n-k);--i)
            ans = min(ans,dp[i][k-(n-i)]);
        cout<<ans<<endl;
    }
    return 0;
}
Tester's Code
/***************************************************

@author: vichitr
Compiled On: 7th Mar 2021

*****************************************************/
#include<bits/stdc++.h>
#define MAX 9223372036854775807
#define endl "\n"
#define ll long long
#define pb push_back
#define pf pop_front
#define mp make_pair
#define ip pair<int, int>
#define F first
#define S second

#define loop(i,n) for(int i=0;i<n;i++)
#define loops(i,s,n) for(int i=s;i<=n;i++)
#define fast ios::sync_with_stdio(0); cin.tie(NULL); 
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ip, null_type, less_equal<ip>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).

int n, dp[1005][51];
int x[1005], y[1005];
int dp1[1001][1001][51];

int dist(int a, int b){
    return abs(x[a] - x[b]) + abs(y[a] - y[b]);
}

int solve(int idx, int skips){
    if(idx > n)
        return 0;
    int &ans = dp[idx][skips];
    if(ans != -1)
        return ans;
    if(idx + skips >= n)
        return 0;
    ans = dist(idx, idx + 1) + solve(idx + 1, skips);
    for(int i = 1; i <= skips; i++){
        ans = min(ans, dist(idx, idx + i + 1) + solve(idx + i + 1, skips - i));
    }
    return ans;
}

int solve(int idx, int prev, int k){
    if(idx > n)
        return 0;
    int &ans = dp1[idx][prev][k];
    if(ans != -1)
        return ans;
    ans = dist(idx, prev) + solve(idx + 1, idx, k);
    if(k > 0)
        ans = min(ans, solve(idx + 1, prev, k - 1));
    return ans;
}

int solve_iterative(int k){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
            dp[i][j] = 0;
    for(int i=1;i<=n;i++){
        for(int p=0;p<=k;p++){
            dp[i][p] = INT_MAX;
            for(int j=1;j<=p+1;j++){
                int skips = p-(j-1);
                if(skips >= 0)
                    dp[i][p] = min(dp[i][p], dist(i-j,i)+dp[i-j][skips]);
            }
        }
    }
    int ans = INT_MAX;
    for(int i=n;i>=(n-k);--i)
        ans = min(ans,dp[i][k-(n-i)]);
    return ans;
}

void solve(){
    int k; cin >> n >> k;
  	assert(1 <= n  and n <= 1e3);
  	assert(0 <= k  and k <= min(n, 50));
  	
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
	  	assert(0 <= x[i] and x[i] <= 1e6);
  		assert(0 <= y[i] and y[i] <= 1e6);
	}
    //memset(dp1, -1, sizeof dp1);
  	//cout<<solve(1, 0, k)<<'\n';
  	memset(dp, -1, sizeof dp);
    cout << solve(0, k) << '\n';
  	//cout<<solve_iterative(k)<<'\n';
}

signed main()
{
    fast;
    int t=1;
    cin >> t;
  	assert(t <= 5);
    for(int i = 1; i <= t; i++)
    {
        // cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}

If you have used any other approach, share your approach in comments!
If you have any doubts, ask them in comments!

4 Likes