Problem 1 Here there be Dragons(IOI Training Camp, 2012) [DP]

Problem 3

Here there be Dragons(IOI Training Camp, 2012)

Since We can’t go with a greedy strategy there can be various counter examples. So we will use dynamic programming.

Now we don’t know which dragon to visit first, second, .. so on.

Because every change order will produce different ans. And we want the minimum one.

So we will compute values for each dragon if we finish the dragon j as ith ( i from 1 to k ) dragon killed but try to do it efficiently [not recompute already computed things].

So our dp consists of two states i, j

Let dp[i][j] = minimum distance : if jth dragon is the ith dragon killed. 

1 <= i <= k

So we know the value for dp[1][j] for all the dragon j. Mean we know the value for each dragon j if it is 1st dragon to killed.

It is nothing but we have to go from (0, 0) to (x[j], y[j])

So

for(each dragon j) {
    dp[1][j] = x[j] + y[j];
}

Now we iteratively fill the dp array for i = 2 to k.

The important point is the movement allowed: down, left and right. So no up motion is allowed and this restricts

that if we visit dragon j as ith dragon then we can’t visit any dragon which is up in the row from dragon j.

In Fact, if we analyze we can find that we need not find dp[1][j] for all the dragons and in general any dp[i][j] for all the dragon j because see you can’t make every dragon be the first dragon. Like suppose if you have to kill more than 1 and if you start from the last dragon as the first dragon to kill then you can never kill any other because you can’t take any up move.

so we can change dp[1][ j ] filling :

d: Total dragon, k = total to kill.

for( int i = 1 ; i <= d - k + 1 ;++i){
    dp[1][i] = x[i] + y[i];
}

Because if you visit d-k+2 th dragon as the 1st then you are left with k-2 dragon available and we have to still kill k-1 so not possible. So no need to compute unnecessarily.

For i = 2 to k

1.   for(int i = 2 ; i <= k ; ++i) {
2.      for(int j = i ; j <= d ; ++j) {
3.           int val = inf;
4.           for(int p = j - 1; p >= 1; --p) {
5.                  if(dp[i - 1][p] and temp > dist[p][j] + dp[i - 1][p])
6.                       val = dist[p][j] + dp[i - 1][p];
7.          }
8.          dp[i][j] = val;
9.        }
10.  }

See line 2. For each dragon j if it is the ith one to visit then we have to look at the dragon which is already visited and up in a row (line 4 loop is iterating backwards from j ) If we current dragon is the ith one then we have to search for the one which is the i-1th. So we can know the transaction in the dp.

To know the answers for dp[i][j] we need to look at all the dragons who are killed as the i-1 dragon.

To find the minimum. That’s what line 4 to 7 is doing and we fill the temp_ans to dp[i][j].

And finally what is the answer? We must have to kill k dragon

So we iterate from dragon no. k to the last dragon if it is the last dragon to kill i.e kth. dp[k][i] i from k to d.

int ans = inf;

for(int i = k; i <= d; ++i)
    ans = min(ans, dp[k][i]);

cout << ans << "\n";

Complexity: 

Time complexity: O( k * d * d )
Space Complexity : O(k*d)

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long int
#define vi vector<int>
#define vpi vector<pair<int,int> >
#define all(v) (v).begin(), (v).end()
#define pb push_back
const int inf=INT_MAX;

int u, v;
int dp[350][350],dist[350][350];


int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
  
    int r,c,k,d;
    cin >> r >> c >> k >> d;
 
    vector<pair<int, int> > a;
    a.push_back({0, 0});
    for(int i = 0; i < d; ++i){
        cin >> u >> v;
        a.push_back({u, v});
    }
    
    sort(a.begin(), a.end());

    for(int i = 1;i <= d; ++i)
        for(int j = 1;j <= d; ++j)
            if(!dist[i][j])
                dist[i][j] = dist[j][i] = abs(a[i].first - a[j].first)+ abs(a[i].second - a[j].second);
                    
        
    for(int i = 1;i <= d - k + 1; ++i)
        dp[1][i] = a[i].first + a[i].second;
      
 
    for(int i = 2; i <= k; ++i){
        for(int j = i; j <= d; ++j){
            int temp = inf;
            for(int p = j - 1; p >= 1; --p){
                    if(dp[i - 1][p] && temp > dist[p][j] + dp[i - 1][p])
                        temp = dist[p][j] + dp[i - 1][p];
            }
            dp[i][j] = temp;
        }
    }
    
    int ans = inf;
    for(int i = k; i <= d; ++i)
        ans = min(ans, dp[k][i]);
    
    cout << ans <<"\n";
    return 0;
} 

---