Given a graph with N nodes and M edges with array A[] and integer C, the task is to find the maximum score. If visiting node i gives A[i] points for all i from 1 to N. It is necessary to start the traversal from node 1 and end the traversal on node 1. The cost of traversal is C * T2 where T is the distance traveled.
Examples:
Input: A[] = {0, 10, 20}, edges[][2] = { {1, 2}, {2, 3}, {3, 1} }, C = 1
Output: 24
Explanation:
- The optimal traversal is 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1
- T = Total Distance travelled = 6
- The cost is 10 (1 -> 2) + 20 (2 -> 3) + 0 (3 -> 1) + 10 (1 -> 2) + 20 (2 -> 3) + 0 (3 -> 1) – C * T2 = 60 – C * T2 = 60 – 1 * 62 = 24
example 1 :
Input: A[] = {0, 10, 20}, edges[][2] = { {1, 2}, {2, 3}, {3, 1} }, C= 100
Output: 0
Explanation: It’s optimal not to traverse at all.
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem
- dp[i][j] = the maximum score on traversing node i’th time ending on node j.
- recurrence relation: dp[curTime][u] = max(dp[curTime][u], dp[curTime – 1][i] + A[u]);
Follow the steps below to solve the problem:
- Declare a 2d array dp[maxTime][N] with all values initialized to -1 indicating no node is visited yet.
- Base case dp[0][0] = 0, if we do not travel at all we get 0 coins.
- Initialize the answer variable to keep track of the max score.
- Iterate on all and for each day iterate on all nodes.
- At the end of each day keep track of the maximum value possible.
- Finally, return the answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate maximum coins// during tripsvoid maximumCoins(int A[], int N, int edg[][2], int M, int C){ // Adjecency list vector<vector<int> > adj(N); for (int i = 0; i < M; i++) { // Travel from edg[i][0] // to edg[i][1] adj[--edg[i][0]].push_back(--edg[i][1]); } // dp table initialized with -1 // indicating not visited vector<vector<int> > dp(1001, vector<int>(N, -1)); // Base case dp[0][0] = 0; int ans = 0; // Simulating time from 0 to 1000 for (int curTime = 0; curTime < 1000; curTime++) { // At each unit time iterate // on each node for (int i = 0; i < N; i++) { // If dp[d][i] == -1 then the // node can't be visited if (dp[curTime][i] != -1) { for (int u : adj[i]) { // dp[curTime + 1][u] // is max(current coins // earned, previous // node's earnings + // current node's // earnings) dp[curTime + 1][u] = max(dp[curTime + 1][u], dp[curTime][i] + A[u]); } } } ans = max(ans, (dp[curTime][0] - (C * curTime * curTime))); } cout << ans << "\n";}// Driver Codeint main(){ // Input 1 int A[] = { 0, 10, 20 }, edges[][2] = { { 1, 2 }, { 2, 3 }, { 3, 1 } }, C = 1; int N = sizeof(A) / sizeof(A[0]); int M = 3; // Function Call maximumCoins(A, N, edges, M, C); // Input 2 int A1[] = { 0, 10, 20 }, edges1[][2] = { { 1, 2 }, { 2, 3 }, { 3, 1 } }, C1 = 10; int N1 = sizeof(A1) / sizeof(A1[0]); int M1 = 3; // Function Call maximumCoins(A1, N1, edges1, M1, C1); return 0;} |
Java
import java.util.*;public class Main { // Function to calculate maximum coins during trips public static void maximumCoins(int[] A, int N, int[][] edg, int M, int C) { // Adjacency list ArrayList<ArrayList<Integer> > adj = new ArrayList<ArrayList<Integer> >(); for (int i = 0; i < N; i++) { adj.add(new ArrayList<Integer>()); } for (int i = 0; i < M; i++) { // Travel from edg[i][0] to edg[i][1] adj.get(edg[i][0] - 1).add(edg[i][1] - 1); } // dp table initialized with -1 indicating not // visited int[][] dp = new int[1001][N]; for (int i = 0; i < 1001; i++) { Arrays.fill(dp[i], -1); } // Base case dp[0][0] = 0; int ans = 0; // Simulating time from 0 to 1000 for (int curTime = 0; curTime < 1000; curTime++) { // At each unit time iterate on each node for (int i = 0; i < N; i++) { // If dp[d][i] == -1 then the node can't be // visited if (dp[curTime][i] != -1) { for (int u : adj.get(i)) { // dp[curTime + 1][u] is max(current // coins earned, previous node's // earnings + current node's // earnings) dp[curTime + 1][u] = Math.max( dp[curTime + 1][u], dp[curTime][i] + A[u]); } } } ans = Math.max( ans, (dp[curTime][0] - (C * curTime * curTime))); } System.out.println(ans); } // Driver Code public static void main(String[] args) { // Input 1 int[] A = { 0, 10, 20 }; int[][] edges = { { 1, 2 }, { 2, 3 }, { 3, 1 } }; int C = 1; int N = A.length; int M = 3; // Function Call maximumCoins(A, N, edges, M, C); // Input 2 int[] A1 = { 0, 10, 20 }; int[][] edges1 = { { 1, 2 }, { 2, 3 }, { 3, 1 } }; int C1 = 10; int N1 = A1.length; int M1 = 3; // Function Call maximumCoins(A1, N1, edges1, M1, C1); }}// This code is contributed by Prajwal Kandekar |
Python3
# Python code to implement the approach# Function to calculate maximum coins# during tripsdef maximumCoins(A, N, edg, M, C): # Adjacency list adj = [[] for i in range(N)] for i in range(M): # Travel from edg[i][0] # to edg[i][1] adj[edg[i][0]-1].append(edg[i][1]-1) # dp table initialized with -1 # indicating not visited dp = [[-1 for i in range(N)] for j in range(1001)] # Base case dp[0][0] = 0 ans = 0 # Simulating time from 0 to 1000 for curTime in range(1000): # At each unit time iterate # on each node for i in range(N): # If dp[d][i] == -1 then the # node can't be visited if dp[curTime][i] != -1: for u in adj[i]: # dp[curTime + 1][u] # is max(current coins # earned, previous # node's earnings + # current node's # earnings) dp[curTime + 1][u] = max(dp[curTime + 1] [u], dp[curTime][i] + A[u]) ans = max(ans, (dp[curTime][0] - (C * curTime * curTime))) print(ans)# Driver Codeif __name__ == '__main__': # Input 1 A = [0, 10, 20] edges = [[1, 2], [2, 3], [3, 1]] C = 1 N = len(A) M = 3 # Function Call maximumCoins(A, N, edges, M, C) # Input 2 A1 = [0, 10, 20] edges1 = [[1, 2], [2, 3], [3, 1]] C1 = 10 N1 = len(A1) M1 = 3 # Function Call maximumCoins(A1, N1, edges1, M1, C1) |
C#
using System;using System.Collections.Generic;class Program { // Function to calculate maximum coins during trips public static void maximumCoins(int[] A, int N, int[][] edg, int M, int C) { // Adjacency list List<List<int> > adj = new List<List<int> >(); for (int i = 0; i < N; i++) { adj.Add(new List<int>()); } for (int i = 0; i < M; i++) { // Travel from edg[i][0] to edg[i][1] adj[edg[i][0] - 1].Add(edg[i][1] - 1); } // dp table initialized with -1 indicating not // visited int[][] dp = new int[1001][]; for (int i = 0; i < 1001; i++) { dp[i] = new int[N]; for (int j = 0; j < N; j++) { dp[i][j] = -1; } } // Base case dp[0][0] = 0; int ans = 0; // Simulating time from 0 to 1000 for (int curTime = 0; curTime < 1000; curTime++) { // At each unit time iterate on each node for (int i = 0; i < N; i++) { // If dp[d][i] == -1 then the node can't be // visited if (dp[curTime][i] != -1) { foreach(int u in adj[i]) { // dp[curTime + 1][u] is max(current // coins earned, previous node's // earnings + current node's // earnings) dp[curTime + 1][u] = Math.Max( dp[curTime + 1][u], dp[curTime][i] + A[u]); } } } ans = Math.Max( ans, (dp[curTime][0] - (C * curTime * curTime))); } Console.WriteLine(ans); } // Driver Code public static void Main(string[] args) { // Input 1 int[] A = { 0, 10, 20 }; int[][] edges = { new int[] { 1, 2 }, new int[] { 2, 3 }, new int[] { 3, 1 } }; int C = 1; int N = A.Length; int M = 3; // Function Call maximumCoins(A, N, edges, M, C); // Input 2 int[] A1 = { 0, 10, 20 }; int[][] edges1 = { new int[] { 1, 2 }, new int[] { 2, 3 }, new int[] { 3, 1 } }; int C1 = 10; int N1 = A1.Length; int M1 = 3; // Function Call maximumCoins(A1, N1, edges1, M1, C1); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Function to calculate maximum coins during tripsfunction maximumCoins(A, N, edg, M, C) { // Adjacency listlet adj = [];for (let i = 0; i < N; i++) { adj.push([]);}for (let i = 0; i < M; i++) { // Travel from edg[i][0] to edg[i][1] adj[edg[i][0] - 1].push(edg[i][1] - 1);}// dp table initialized with -1 indicating not visitedlet dp = [];for (let i = 0; i < 1001; i++) { let temp = []; for (let j = 0; j < N; j++) { temp.push(-1); } dp.push(temp);}// Base casedp[0][0] = 0;let ans = 0;// Simulating time from 0 to 1000for (let curTime = 0; curTime < 1000; curTime++) { // At each unit time iterate on each node for (let i = 0; i < N; i++) { // If dp[d][i] == -1 then the node can't be visited if (dp[curTime][i] != -1) { for (let j = 0; j < adj[i].length; j++) { let u = adj[i][j]; // dp[curTime + 1][u] is max(current coins earned, previous // node's earnings + current node's earnings) dp[curTime + 1][u] = Math.max(dp[curTime + 1][u], dp[curTime][i] + A[u]); } } } ans = Math.max(ans, (dp[curTime][0] - (C * curTime * curTime)));}console.log(ans);}// Driver Codelet A = [0, 10, 20];let edges = [[1, 2], [2, 3], [3, 1]];let C = 1;let N = A.length;let M = 3;// Function CallmaximumCoins(A, N, edges, M, C);let A1 = [0, 10, 20];let edges1 = [[1, 2], [2, 3], [3, 1]];let C1 = 10;let N1 = A1.length;let M1 = 3;// Function CallmaximumCoins(A1, N1, edges1, M1, C1); |
Output
24 0
Time Complexity: O((N + M) * D)
Auxiliary Space: O(N * D) where D is the maximum number of nodes visited.
Efficient approach : Space optimization
In previous approach the dp[i][j] is depend upon the current and previous row of 2D matrix. So to optimize space we use two vectors dp1 and dp2 that keep track of current and previous row of DP.
Implementation Steps:
- Initialize 2 vectors dp1 and dp2 with -1 of size N to keep track of only previous and current row of Dp matrix.
- Initialize dp1 with the base case. and a variable ans to update the dp2 with current value.
- Now iterative over subproblems and get the current computation.
- Now compute the current value by the help of dp1 vector and store that value in dp2.
- After every iteration store values of dp2 vector in dp1 vector for further iteration.
- At last print the ans.
C++
#include <bits/stdc++.h>using namespace std;// Function to calculate maximum coins// during tripsvoid maximumCoins(int A[], int N, int edg[][2], int M, int C) { vector<vector<int>> adj(N); for (int i = 0; i < M; i++) { adj[--edg[i][0]].push_back(--edg[i][1]); } vector<int> dp1(N, -1); // Current time step DP vector<int> dp2(N, -1); // Next time step DP // Base case dp1[0] = 0; int ans = 0; // iterate over subproblems for (int curTime = 0; curTime < 1000; curTime++) { for (int i = 0; i < N; i++) { if (dp1[i] != -1) { for (int u : adj[i]) { dp2[u] = max(dp2[u], dp1[i] + A[u]); } } } ans = max(ans, (dp1[0] - (C * curTime * curTime))); // Swap dp1 and dp2 for the next time step swap(dp1, dp2); fill(dp2.begin(), dp2.end(), -1); // Reset dp2 to -1 } cout << ans << "\n";}int main() { // Input 1 int A[] = { 0, 10, 20 }, edges[][2] = { { 1, 2 }, { 2, 3 }, { 3, 1 } }, C = 1; int N = sizeof(A) / sizeof(A[0]); int M = 3; // Function Call maximumCoins(A, N, edges, M, C); // Input 2 int A1[] = { 0, 10, 20 }, edges1[][2] = { { 1, 2 }, { 2, 3 }, { 3, 1 } }, C1 = 10; int N1 = sizeof(A1) / sizeof(A1[0]); int M1 = 3; // Function Call maximumCoins(A1, N1, edges1, M1, C1); return 0;} |
Python3
def maximumCoins(A, N, edg, M, C): adj = [[] for _ in range(N)] for i in range(M): adj[edg[i][0] - 1].append(edg[i][1] - 1) dp1 = [-1] * N # Current time step DP dp2 = [-1] * N # Next time step DP # Base case dp1[0] = 0 ans = 0 # Iterate over subproblems for curTime in range(1000): for i in range(N): if dp1[i] != -1: for u in adj[i]: dp2[u] = max(dp2[u], dp1[i] + A[u]) ans = max(ans, (dp1[0] - (C * curTime * curTime))) # Swap dp1 and dp2 for the next time step dp1, dp2 = dp2, [-1] * N print(ans)# Driver code# Input 1A = [0, 10, 20]edges = [[1, 2], [2, 3], [3, 1]]C = 1N = len(A)M = 3# Function CallmaximumCoins(A, N, edges, M, C)# Input 2A1 = [0, 10, 20]edges1 = [[1, 2], [2, 3], [3, 1]]C1 = 10N1 = len(A1)M1 = 3# Function CallmaximumCoins(A1, N1, edges1, M1, C1) |
Output
24
0
Time Complexity: O(1000 * N * M), where N is the number of nodes, and M is the number of edges in the graph.
Auxiliary Space: O(N + M)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
