Given N poles, each pole consists of hi number of vertices. Vertices on each pole are numbered from 1 to hi, the task is to find the longest simple chain formed by N poles, given the start and end point connections where the poles are connected in one graph in the following way:
- The first pole is ignored
- An edge connects the 1st vertex of the ith pole with the aith vertex of (i-1)-th pole.
- An edge connects the last vertex of the ith pole with the bith vertex of the (i-1)-th pole
Examples:
Input: N = 4
H = {3, 4, 3, 3} //Height of each pole {number of vertices on each pole}
A = {-1, 1, 2, 2} //1st vertex connection points for each pole
B = {-1, 1, 2, 3} //End vertex connection points for each pole
Output: 7
Explanation: The following image is the structure of connections formed:
Example 1
In this given test case the longest simple pole formed is shown the below image, outlined in red (showing the longest simple chain length = 7). We can’t increase it with the first pole, since in such a case it would not be simple — the vertex 2 on the second pole will break simplicity.
Example 1 solution explanation
Input: N = 2
H = {5, 6} //Height of each pole
A = {-1, 5} //1st vertex connection points for each pole
B = {-1, 1} //End vertex connection points for each pole
Output: 11
Approach: Implement the idea below to solve the problem:
Suppose, we’ve built the graph and chosen any simple cycle.
Due to the nature of the graph, any simple cycle right part is part of one of the poles. So, let’s for each pole calculate the longest simple path with its right part on this pole and denote it as leni.
- Obviously, len1 = 0. Now, let’s look at pole i. If we go along the cycle in both ways, we will step to vertices ai and bi of the previous pole. If ai=bi then we closed cycle and it’s the only possible cycle, so leni = hi + 1.
- Otherwise, we can either go from ai and bi and meet each other closing the cycle with part of the (i−1)th pole between aith and bith vertices — this part has |ai − bi| edges and our cycle will have length hi + 1 + |ai − bi|.
- But if we decide to go in different ways, then we will meet the first and the last vertices ofthe (i−1)th pole. After that, we’ll go to the ai − 1th and the (bi−1)th vertices of (i−2)th pole andwill make almost the same choice.
- But, instead of recurrently solving the same problem, we can note that, in fact, we took a cycle that ends at the (i−1)th pole, erased the part between vertices ai and bi, and merged it with our ith pole part, so the length of this merged cycle will be equal to hi + 1 + leni−1 − |ai−bi|. Since we maximize leni we just choose, what part: |ai−bi| or leni−1 − |ai−bi| is longer and take it.
As a result, we can iterate from left to right, calculate all leni and print the maximum among them.
Follow the steps mentioned below to implement the idea:
- initialize the chain length lstLen = 0
- loop over each pole, skipping the first pole
- for each pole, calculate the curLen = H[i] + 1 + abs(A[i] – B[i])
- if (A[i] != B[i])
- calculate new length newLen = H[i] + 1 + lstLen – abs(A[i] – B[i])
- update curLen = max(curLen, newLen)
- update global ans = max(ans, curLen)
- assign the last length to the new curLen value. (lstLen = curLen)
- Last, return ans (longest Chain Length)
Below is the Implementation of the above approach.
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to find out the longest chainint findLongestSimpleChain(int N, vector<int> H, vector<int> A, vector<int> B){ int ans = 0; int lstLen = 0; for (int i = 1; i < N; i++) { // Calculating the current cycle // length using the formula discussed // in illustration of approach int curLen = H[i] + 1 + abs(A[i] - B[i]); // If the first and last vertex // connections are not same then // this is not a new chain if (A[i] != B[i]) { // Finding new chain length int newLen = H[i] + 1 + lstLen - abs(A[i] - B[i]); // Keeping the maximum // in curLen curLen = max(curLen, newLen); } // Keeping the global maximum // simple chain length // in ans variable ans = max(ans, curLen); lstLen = curLen; } return ans;}// Driver codeint main(){ // N denotes the total number // of poles given int N = 4; vector<int> H(N), A(N), B(N); // H is storing total number of // vertices on each pole H = { 3, 4, 3, 3 }; // 1st vertex connection points // for each pole A = { -1, 1, 2, 2 }; B = { -1, 2, 2, 3 }; // End vertex connection points // for each pole cout << findLongestSimpleChain(N, H, A, B) << "\n"; // Second test Case N = 2; H = { 5, 6 }; A = { -1, 5 }; B = { -1, 1 }; // Function Call cout << findLongestSimpleChain(N, H, A, B) << "\n"; return 0;}; |
Java
// Java code for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find out the longest chain static int findLongestSimpleChain(int N, List<Integer> H, List<Integer> A, List<Integer> B) { int ans = 0; int lstLen = 0; for (int i = 1; i < N; i++) { // Calculating the current cycle length using // the formula discussed in illustration of // approach int curLen = H.get(i) + 1 + Math.abs(A.get(i) - B.get(i)); // If the first and last vertex connections are // not same then this is not a new chain if (A.get(i) != B.get(i)) { // Finding new chain length int newLen = H.get(i) + 1 + lstLen - Math.abs(A.get(i) - B.get(i)); // Keeping the maximum in curLen curLen = Math.max(curLen, newLen); } // Keeping the global maximum simple chain // length in ans variable ans = Math.max(ans, curLen); lstLen = curLen; } return ans; } public static void main(String[] args) { // N denotes the total number // of poles given int N = 4; List<Integer> H = new ArrayList<Integer>(); List<Integer> A = new ArrayList<Integer>(); List<Integer> B = new ArrayList<Integer>(); // H is storing total number of // vertices on each pole H.add(3); H.add(4); H.add(3); H.add(3); // 1st vertex connection points // for each pole A.add(-1); A.add(1); A.add(2); A.add(2); B.add(-1); B.add(2); B.add(2); B.add(3); // End vertex connection points // for each pole System.out.println( findLongestSimpleChain(N, H, A, B)); // Second test Case N = 2; H.clear(); A.clear(); B.clear(); H.add(5); H.add(6); A.add(-1); A.add(5); B.add(-1); B.add(1); // Function Call System.out.println( findLongestSimpleChain(N, H, A, B)); }}// This code is contributed by sankar. |
Python3
# Python program for the above approachfrom typing import List# Function to find out the longest chaindef findLongestSimpleChain(N: int, H: List[int], A: List[int], B: List[int]) -> int: ans = 0 lstLen = 0 for i in range(1, N): # Calculating the current cycle # length using the formula discussed # in illustration of approach curLen = H[i] + 1 + abs(A[i] - B[i]) # If the first and last vertex # connections are not same then # this is not a new chain if A[i] != B[i]: # Finding new chain length newLen = H[i] + 1 + lstLen - abs(A[i] - B[i]) # Keeping the maximum # in curLen curLen = max(curLen, newLen) # Keeping the global maximum # simple chain length # in ans variable ans = max(ans, curLen) lstLen = curLen return ans# Driver codeif __name__ == '__main__': # N denotes the total number # of poles given N = 4 H = [3, 4, 3, 3] # 1st vertex connection points # for each pole A = [-1, 1, 2, 2] B = [-1, 2, 2, 3] # End vertex connection points # for each pole print(findLongestSimpleChain(N, H, A, B)) # Second test Case N = 2 H = [5, 6] A = [-1, 5] B = [-1, 1] # Function Call print(findLongestSimpleChain(N, H, A, B))# This code is contributed by rishabmalhdjio |
Javascript
// JavaScript code for the above approach:// Function to find out the longest chainfunction findLongestSimpleChain(N, H, A, B){ let ans = 0; let lstLen = 0; for (let i = 1; i < N; i++) { // Calculating the current cycle // length using the formula discussed // in illustration of approach let curLen = H[i] + 1 + Math.abs(A[i] - B[i]); // If the first and last vertex // connections are not same then // this is not a new chain if (A[i] != B[i]) { // Finding new chain length let newLen = H[i] + 1 + lstLen - Math.abs(A[i] - B[i]); // Keeping the maximum // in curLen curLen = Math.max(curLen, newLen); } // Keeping the global maximum // simple chain length // in ans variable ans = Math.max(ans, curLen); lstLen = curLen; } return ans;}// Driver code// N denotes the total number// of poles givenlet N = 4;let H = new Array(N), A = new Array(N), B = new Array(N);// H is storing total number of// vertices on each poleH = [ 3, 4, 3, 3 ];// 1st vertex connection points// for each poleA = [ -1, 1, 2, 2 ];B = [ -1, 2, 2, 3 ];// End vertex connection points// for each poleconsole.log(findLongestSimpleChain(N, H, A, B));// Second test CaseN = 2;H = [ 5, 6 ];A = [ -1, 5 ];B = [ -1, 1 ];// Function Callconsole.log(findLongestSimpleChain(N, H, A, B)); |
C#
using System;using System.Collections.Generic;using System.Linq;class Gfg { // Function to find out the longest chain public static int findLongestSimpleChain(int N, List<int> H, List<int> A, List<int> B) { int ans = 0; int lstLen = 0; for (int i = 1; i < N; i++) { // Calculating the current cycle // length using the formula discussed // in illustration of approach int curLen = H[i] + 1 + Math.Abs(A[i] - B[i]); // If the first and last vertex // connections are not same then // this is not a new chain if (A[i] != B[i]) { // Finding new chain length int newLen = H[i] + 1 + lstLen - Math.Abs(A[i] - B[i]); // Keeping the maximum // in curLen curLen = Math.Max(curLen, newLen); } // Keeping the global maximum // simple chain length // in ans variable ans = Math.Max(ans, curLen); lstLen = curLen; } return ans; } static void Main(string[] args) { // N denotes the total number // of poles given int N = 4; List<int> H = new List<int>() { 3, 4, 3, 3 }; // 1st vertex connection points // for each pole List<int> A = new List<int>() { -1, 1, 2, 2 }; List<int> B = new List<int>() { -1, 2, 2, 3 }; // End vertex connection points // for each pole Console.WriteLine(findLongestSimpleChain(N, H, A, B)); // Second test Case N = 2; H = new List<int>() { 5, 6 }; A = new List<int>() { -1, 5 }; B = new List<int>() { -1, 1 }; // Function Call Console.WriteLine(findLongestSimpleChain(N, H, A, B)); }} |
Output
7 11
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
Share your thoughts in the comments
