Find the longest simple chain formed by N poles

Given N poles, each pole consists of h_i number of vertices. Vertices on each pole are numbered from 1 to h_i, 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 i^th pole with the a_i^th vertex of (i-1)-th pole.
• An edge connects the last vertex of the i^th pole with the b_i^th 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 ai^th and bi^th 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 − 1^th 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 i^th 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 Lenght)

Below is the Implementation of the above approach.

Time Complexity: O(N)
Auxiliary Space: O(1)

Given N poles, each pole consists of h_i number of vertices. Vertices on each pole are numbered from 1 to h_i, 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 i^th pole with the a_i^th vertex of (i-1)-th pole.
• An edge connects the last vertex of the i^th pole with the b_i^th 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 ai^th and bi^th 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 − 1^th 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 i^th 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 Lenght)

Below is the Implementation of the above approach.

Time Complexity: O(N)
Auxiliary Space: O(1)