I found this question in NITK techfest but I couldn’t find a good approach to go ahead on it.
Can somebody help?
link to the question
Dragon Warrior
Recurrence
Try solve the problem using a recursive logic. First of all, since before the first step Po can move to any of the possible locations, we should find the top score you can earn if we move to location (x,y) before the first move. We should try each location (x,y) as a candidate.
After the first move, Po can earn some calories depending on the location of first item. Then he can choose to move to a new point (x’,y’) which shares column or row (x,y). After this move, we are in a similar sub-problem to the initial one, you are located at position (x’,y’) and want to know the maximum calories you can make with the last K−1 events. (Where K is the number of events).
The recurrence relation goes as follows: f(x,y,i) finds the maximum calories gained if Po is located at position (x,y) before event i.
If i=K, all items have been found and Po cannot earn any more calories. The result is 0. This is the base case.
Else Po can earn some calories m equal to the Manhattan distance between (x,y) and the event’s location. Finally he can move to a new point (x’,y’) and then the remaining events will happen and he might move again later. We can try to iterate through all reachable points (x’,y’) that share the column or row with (x,y) and pick the maximum f(x’,y’,i+1).
The complexity of this approach is large. Imagine T was the largest dimension. There are O(T2) values for (x,y) , which means there are O(KT2) possible states for the function. In each state, we need an O(T) loop to pick the new row or the new column. In total we have an O(KT3) complexity. Note that T can be very large: T’=1000000.
In order to make the solution more efficient, we just need to notice that it is never necessary to move to a point (x,y) such that x or y don’t match at least one of the events’ coordinates. This means that there are only O(k) options we need to try for x and y in each step and there are O(k2) different values. This changes the complexity to O(k4).
1 Like
Brother, as medhz12 has already explained it, here is my implementation for the mentioned problem :
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
int MOD = 1000000007;
int main() {
int A, Z, Q, K; cin >> A >> Z >> Q >> K;
vector<int> X(K), Y(K);
for (int k = 0; k < K; k++) cin >> X[k] >> Y[k];
vector<int> v = X, w = Y;
sort(v.begin(), v.end());
sort(w.begin(), w.end());
v.erase(unique(v.begin(), v.end()), v.end());
w.erase(unique(w.begin(), w.end()), w.end());
int n = v.size(), m = w.size();
vector< vector<ll> > dp(n, vector<ll>(m));
for (int k = 0; k < K; k++) {
vector< vector<ll> > _dp(n, vector<ll>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
for (int _i = 0; _i < n; _i++) {
int q = A + Z - abs(X[k] - v[_i]) - abs(Y[k] - w[j]);
_dp[_i][j] = max(_dp[_i][j], dp[i][j] + q);
}
for (int _j = 0; _j < m; _j++) {
int q = A + Z - abs(X[k] - v[i]) - abs(Y[k] - w[_j]);
_dp[i][_j] = max(_dp[i][_j], dp[i][j] + q);
}
}
dp = _dp;
}
ll ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
ans = max(ans, dp[i][j]);
cout << (ans >= Q ? 1 : 0) << endl;
}
5 Likes
Superb explanation by Medhini G Narasimhan…since you authored the question.
1 Like