Someone please help me with this question???
Hi @keshav_jindal, I hope it’s not from an ongoing contest. To solve the problem I made some observations.
- Imagine all integers as vertices of a graph, now from every vertex we have 3 edges. Towards 2 \cdot x, x - 1, and x + 1.
- These edges have their respective weights so the graph will be a weighted directed graph (it contains cycles as x - 1 is a back-edge.)
- We will never exceed 4 \cdot n in the optimal path from 1 to n. (why? because if the optimal path were to go somewhere at 4 \cdot n + k (k <n) and continuously decrease, the cost will be z \cdot (3 \cdot n + k); obviously we can to better by not going till there.)
Algorithm
Run Dijkstra’s with source as 1 and find the shortest path.
I’m not sure if this runs within time limit but the overall idea should be in the right direction.
Try implementing yourself before looking at the code.
The code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, x, y, z;
cin >> n >> x >> y >> z;
vector<bool> vis(4*n, false);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push({0, 1});
while (!pq.empty()) {
pair<ll, ll> j = pq.top();
pq.pop();
if (vis[j.second]) continue;
vis[j.second] = true;
if (j.second == n) {
cout << j.first << nl;
return;
};
if (j.second > 1) pq.push({j.first + z, j.second - 1});
if (j.second * 2 < 4 * n) pq.push({j.first + x, j.second * 2});
if (j.second + 1 < 4 * n) pq.push({j.first + y, j.second + 1});
}
cout << -1 << nl;
return;
}
2 Likes
Thank you very much @bennyjoseph . Your post helped a lot. I have understood your solution and have coded it. Just one doubt, why the no. of nodes should be 4n, why it cant be 2n ?
I couldn’t prove 2 \cdot n will work for sure, but was able to convince myself that 4 \cdot n will work so I did that.
Maybe you can do a 3 or 4 line proof of why 2 \cdot n works
I think this is in the Coding Blocks course and there is also a video in that course about the DP solution to this problem.
Anyways let dp[n] be the min cost to create n cells.
Hence dp[n] = min(dp[n/2] + x, dp[(n + 2) / 2] + x + 2 * z , dp[(n - 2 ) / 2] + x + 2 * y) FOR EVEN N
and dp[n] = min(dp[(n + 1) / 2] + x + z, dp[(n - 1 ) / 2] + x + y) FOR ODD N
The idea to come up with the transition is to think in reverse order (i.e how did we get n cells from < n cells)
1 Like
yeah, this ques is from a cb course on dynamic programming. The dp approach didnt looked convincing earlier. But now after i have dryrun multiple times this ques from a different approach, the dp solution is also understable. Thanks @ak2006 for also writing it in such a good and precise way.