Problem name: Network Stability and Security
Topic: Tree, Array
Tags: Tree, DFS, Array, Sliding Window
Language used: C++
Difficulty Level: Hard
Problem Statement:
In a corporate network, there are 'N' servers connected by 'N-1' unique cables, forming
a tree-like structure. Additionally, each server processes a series of tasks represented
by a list of integers. The IT team is tasked with two main objectives:
Ensure all cables in the network are secured. Each server can apply a security patch to
secure the cables leading to the root server. The goal is to determine the minimum
number of security patches needed to secure all cables. ( So if 1 is connected to 2 and
is also connected to 3, and both are having fault then by fixing just 1 of them both can
be fixed)
Identify the longest consecutive sequence of task durations within a server's task list
and find the index of task durations that matches to a specific target value.
Note:
If no such index exists, return -1 for that task in a square bracket. Also, if no
consecutive sequence is present in the task list then return 1 to it.
If there are more than 2 indexes present, then the index with the smallest index
values should be picked.
Also, number of cables should always be equal to or greater than 2, if its below
this value, print zero as output
Input Format:
The first line consists of N, the number of servers.
The second line of input has N-1 lines contain three integers u, v, and s, where u
and v are the endpoints of a cable, and s indicates the security status of the
cable (1 if secured, 0 if not).
After N-1, lines, the following N lines each contain a space-separated list of
integers representing the task durations for each server.
The last line contains a single integer, the target value used to find the index of a
particular task duration.
Output Format:
Print the minimum number of patches needed to secure all cables.
For each server, print two values:
o The length of the longest consecutive sequence of task durations. If
consecutive sequence is not present then print 1.
o A number representing the index which matches with the target value. If
no such index exists, return -1 in a square bracket along with its
sequence.
Constraints:
2 <= N<= 2*10^5
1<= u, v<= N
0<=s<=1
Task durations are integers and each list can be empty or contain up to 10^5
integers. (1 <= Task Duration <= 105)
The target value is an integer. (0 < Target value <= 105)
Sample Input 1:
4
120
231
240
216943
12345
-1 4 2 7 1
12375
9
Sample Output 1:
1
4 [3]
5 [-1]
2 [-1]
5 [-1]
Explanation for Sample case 1:
Network Security:
The cables that are not secured are {1,2} and {2,4}.
By applying the patch from server 4, it will secure the cables {4,2} and {2,1},
making all cables secure.
Minimum patches needed: 1
Task Durations and Target Value:
Server 1:
o Longest consecutive sequence: [1, 2, 3, 4], length = 4.
o Subarray matching to 9: Indices [3].
Server 2:
o Longest consecutive sequence: [1, 2, 3, 4, 5], length = 5.
o Subarray matching to 9: none hence [-1]
Server 3:
o Longest consecutive sequence: [1, 2], length = 2
o Subarray matching to 9: none hence [-1]
Server 4:
o Longest consecutive sequence: [1, 2, 3, 4, 5], length = 5.
o Subarray matching to 9: none hence [-1]
Sample Input 2:
2
121
1 2 3 14 19
4 5 6 18 20
5
Sample Output 2:
0
3 [-1]
3 [1]
Explanation for Sample case 2:
Here we can see that the network is already secured hence we will get output as 0.
For task duration:
Server 1:
o Longest consecutive sequence: [1, 2, 3], length = 3.
o Subarray matching to 5: none hence [-1].
Server 2:
o Longest consecutive sequence: [4, 5, 6], length = 3.
o Subarray matching to 5: at index 1 hence [1]
Network Security:
There are 2 servers and 1 cable between them:
1 2 1: There is a cable between server 1 and server 2, and it is already secured
(1).
Since the only cable in the network is already secured, no patches are needed.
Minimum patches needed: 0
Task Durations and Target Value:
Server 1:
o Task durations: [1, 2, 3, 14, 19]
o Longest consecutive sequence: [1, 2, 3], length = 3.
o Subarray summing to 5: Indices [1, 2] (subarray [2, 3]).
Server 2:
o Task durations: [4, 5, 6, 18, 20]
o Longest consecutive sequence: [4, 5, 6], length = 3.
o Subarray summing to 5: Indices [1] has already 5 in it so it will print that
index.
Code:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
vector<int> tree[MAXN + 1];
int secured[MAXN + 1];
bool visited[MAXN + 1];
vector<vector<int>> tasks;
int N, targetValue;
// Function to perform DFS and calculate the minimum patches
int dfs(int node) {
visited[node] = true;
int patches = 0;
for (int neighbor : tree[node]) {
if (!visited[neighbor]) {
patches += dfs(neighbor);
}
}
if (!secured[node] && patches == 0) {
patches = 1;
}
return patches;
}
// Function to find the longest consecutive sequence
int longestConsecutive(vector<int>& nums) {
if ([Link]()) return 0;
set<int> numSet([Link](), [Link]());
int longestStreak = 0;
for (int num : numSet) {
if () {
int currentNum = num;
int currentStreak = 1;
while ([Link](currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
// Function to find the index of the target value
int findTargetIndex(vector<int>& nums, int target) {
for (int i = 0; i < [Link](); ++i) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
int main() {
cin >> N;
if (N < 2) {
cout << 0 << endl;
return 0;
}
for (int i = 1; i < N; ++i) {
int u, v, s;
cin >> u >> v >> s;
tree[u].push_back(v);
tree[v].push_back(u);
secured[u] = s;
secured[v] = s;
}
[Link](N + 1);
[Link](); // Ignore newline after the last integer
for (int i = 1; i <= N; ++i) {
string line;
getline(cin, line);
stringstream ss(line);
int task;
while (ss >> task) {
tasks[i].push_back(task);
}
}
cin >> targetValue;
fill(visited, visited + N + 1, false);
int patches = dfs(1);
cout << patches << endl;
for (int i = 1; i <= N; ++i) {
int longestSeq = longestConsecutive(tasks[i]);
int targetIdx = findTargetIndex(tasks[i], targetValue);
if (targetIdx == -1) {
cout << longestSeq << " [-1]" << endl;
} else {
cout << longestSeq << " [" << targetIdx << "]" << endl;
}
}
return 0;
}
One Compiler Link:
Network Stability and Security