Connecting Nodes in a Graph with Sum-based Edge Conditions
Given a graph with N nodes (1 ot N) and an array A[] of size N, such that a[i] denotes the value of (i+1)th node. Initially, there are no edges in the graph. To add an edge between nodes i and j, the following condition should be satisfied: S ≥ i * j * c, where S is the sum of the value of all nodes currently in the same connected component of either i or j and c is a constant. The task is to determine whether the graph can be connected.
Examples:
Input: n = 4, c = 10, a = {0, 20, 15, 10}
Output: Yes
Explanation:
- Add edge(1, 2) as 20+0 >= 1 * 2 * 10
- Add edge(1, 3) as 20 + 15 >= 1 * 3 * 10
- Add edge(1, 4) as 35 + 10 >= 1 * 4 * 10
Input: n = 3, c = 1, a = {0, 0, 2}
Output: No
Explanation: We cannot any edge, so the graph cannot be connected.
Approach: The problem can be solved using the following approach:
The problem can be solved by maintaining a running sum of the node values and updating it as edges are added. Since the condition to satisfy is S >= i * j * c, so we need to maximize the sum and minimize the product (i * j * c). In order to minimize the product, we can always add an edge between node 1 and node i. Now, the condition will be reduced to: S >= j * c. Now, Check if it’s possible to add edges such that all nodes are connected, then the graph can be connected. Otherwise, it can’t be.
Steps to solve the problem:
- Calculate the sum s[i] of the values of the nodes up to node i using the formula s[i] = s[i-1] + a[i].
- Check for each node i if it can be connected to the previous nodes based on the given condition that the sum of the values of the nodes up to p + value of node i should be greater than or equal to i*c.
- If the condition is satisfied, then p is updated to i. The variable p is used to keep track of the farthest node that can be reached from the current node.
- Finally, Checks if p is equal to n. If p is equal to n, it means that all nodes can be connected and “Yes” is printed. Otherwise, “No” is printed.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 7; // Declare variables for the number of nodes, the constant // c, the farthest node p, the array of node values a, and // the array of sums s long long n, c, i, p, s[N]; int main() { // Read the number of nodes and the constant c n = 4, c = 10; vector< long long > a = { 0, 20, 15, 10 }; int p = 1; // Loop over each node for (i = 1; i <= n; ++i) { // Calculate the sum of the values up to the current // node s[i] = s[i - 1] + a[i - 1]; // If the sum of the values up to p + // the value of the current node is greater than or // equal to i*c, update p to i if (s[p] + a[i - 1] >= i * c) p = i; } // If p is equal to n, print "Yes". Otherwise, print // "No" cout << (p == n ? "Yes" : "No" ) << endl; } |
Java
import java.util.*; public class Main { public static void main(String[] args) { // Declare variables long n, c, i, p; long [] s; // Read the number of nodes and the constant c n = 4 ; c = 10 ; List<Long> a = Arrays.asList(0L, 20L, 15L, 10L); p = 1 ; // Initialize the sums array s = new long [( int )n + 1 ]; // Loop over each node for (i = 1 ; i <= n; ++i) { // Calculate the sum of the values up to the // current node s[( int )i] = s[( int )(i - 1 )] + a.get(( int )(i - 1 )); // If the sum of the values up to p + // the value of the current node is greater than // or equal to i*c, update p to i if (s[( int )p] + a.get(( int )(i - 1 )) >= i * c) p = i; } // If p is equal to n, print "Yes". Otherwise, print // "No" System.out.println(p == n ? "Yes" : "No" ); } } |
Python3
# Declare variables for the number of nodes, the constant # c, the farthest node p, the array of node values a, and # the array of sums s N = 2 * 10 * * 5 + 7 # Read the number of nodes and the constant c n, c = 4 , 10 a = [ 0 , 20 , 15 , 10 ] s = [ 0 ] * N p = 1 # Loop over each node for i in range ( 1 , n + 1 ): # Calculate the sum of the values up to the current node s[i] = s[i - 1 ] + a[i - 1 ] # If the sum of the values up to p + # the value of the current node is greater than or # equal to i*c, update p to i if s[p] + a[i - 1 ] > = i * c: p = i # If p is equal to n, print "Yes". Otherwise, print "No" print ( "Yes" if p = = n else "No" ) # This code is contributed by shivamgupta0987654321 |
C#
// C# Implementation using System; using System.Collections.Generic; public class Program { public static void Main( string [] args) { // Declare variables long n, c, i, p; long [] s; // Read the number of nodes and the constant c n = 4; c = 10; List< long > a = new List< long > { 0, 20, 15, 10 }; p = 1; // Initialize the sums array s = new long [n + 1]; // Loop over each node for (i = 1; i <= n; ++i) { // Calculate the sum of the values up to the // current node s[i] = s[i - 1] + a[( int )(i - 1)]; // If the sum of the values up to p + // the value of the current node is greater than // or equal to i*c, update p to i if (s[p] + a[( int )(i - 1)] >= i * c) p = i; } // If p is equal to n, print "Yes". Otherwise, print // "No" Console.WriteLine(p == n ? "Yes" : "No" ); } } // This code is contributed by Tapesh(tapeshdu420) |
Javascript
const N = 2e5 + 7; // Declare variables for the number of nodes, the constant c, // the farthest node p, the array of node values a, and // the array of sums s let n, c, i, p; let s = new Array(N).fill(0); // Read the number of nodes and the constant c n = 4; c = 10; let a = [0, 20, 15, 10]; p = 1; // Loop over each node for (i = 1; i <= n; ++i) { // Calculate the sum of the values up to the current node s[i] = s[i - 1] + a[i - 1]; // If the sum of the values up to p + the value of the current node // is greater than or equal to i * c, update p to i if (s[p] + a[i - 1] >= i * c) p = i; } // If p is equal to n, print "Yes". Otherwise, print "No" console.log(p === n ? "Yes" : "No" ); |
Yes
Time complexity: O(N), where N is the number of nodes in the graph.
Auxiliary space: O(N).