Question: Hilabs, Recently Asked Questions in IITs, November 2022 | Maximum Balls | Special Edge

Entering edit mode

Question 1

Maximum Balls

Bob is a maths teacher of a class of N students. The examination results wore out and marks obtained by the students by array marks. Bob is happy with the performance and decides to gift every student in his class an equal number of balls. As Bob likes mathematics a lot. he decided to pick a number which is a factor of marks of all N students in his class and decided to gift that number of balls to every student.

As Bob wants to distribute the maximum number of balls, he can change the marks of at most 1 student in his class to any positive number of his choice, so that he can gift the maximum numbers of ball to the students.

Task

Determine the maximum number of balls Bob can give to every student after changing the marks of at most one student to any positive number of his choice.

Example

Assumptions

N = 3
Marks = [12,3,11]

Approach

The maximum possible number of balls each student can have is 3.
Here to distribute the maximum number of balls to every student. Bob can change the marks of the 3rd student to 39.
So the answer to this sample example becomes 3.

Function Description

Complete the max ball function provided in the editor. This function takes the following 2 parameters and returns an integer that represents the answer to the task as described in the problem statement.

N represents the number of students in the class.
Marks: Represents the marks of N students.

Input Format

Note:This is the input format that you must use to provide custom input (available above the Compile and Test button)

The first line contains the function parameter N.
The second line contains N space-separated integers denoting the input values of the function parameter marks.

Output Format

Print an integer representing the maximum number for the given task.

Constraints

2 <= N <= 10^5

1 <= mark <= 10^2

Code snippets (also called starter code/boiler plate code)

Click here to Practice

hilabs 1.1 hilabs 1.2 hilabs 1.3 hilabs 1.4

Maximum bells

Bob is a maths teacher of e class of students. The examination

rosuits were out and marks obtained by the students are represented

by array marks. Bob is happy with the performance of the dass so he

decided to gift every student in his class an equel number of bels. As

Bob likes mathematics a lot, he decided to pick a number which is a

factor of marks of all Nstudents in his class and decided to gift that

number of balls to every student.

As Bob wants to distribute the maximum number of bells, he can

change the marks of at most 1 student in his class te any positive

number of his choice. so that he can gift the maximum number of bails

to the students.

Task

Determine the maximum number of balls Bob can give to every

student after changing the marks of at most 1 student to any positiv

number of his choice

Example

Assumptions

N = 3

marks = [12 , 3 , 11]

Approach

The maximum possible number of bails each student can have is

• Here to distribute the maximum number of bails to every student.

Bob can change the marks of the 3 student to 39.

•So the answer to this sample example becomes 3

Function description

Complete the max. bets function provided in the editor. This function

takes the following 2 parameters and returns an integer that

represents the answer to the task as described in the problem

statement.

• A Represents the number of students in the class

• marks: Represents the marks of N students

input format

Note: This is the input format that you must use to provide custom

input (available above the Compile and Test button)

The first line contains the function parameter N

The second line contains N space separated integers denoting

the input values of the function parameter marks

Print an Integer representing the maximum number of given task

Constraints

2 ≤ N ≤ 10^5

I ≤ marks, ≤ 10^9

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C. CP, Java and Python,

Sample Input Sample Output

3 3

12 3 11

Example
For the given sample input

Given N = 3
marks = [12 , 3 ,11]

Question 2

Special Edge

Click here to Practice

hilabs 2.1 hilabs 2.2 hilabs 2.3 hilabs 2.4 hilabs 2.5 hilabs 2.6

Special edge
You are given a connected undrected graph having Nodes numbered from to Nand M edges between its nodes. It is guaranteed that the input graph is connected and consists of no self. loops and no multipie edges between two vertices. Loges are given in a 2D array vector Edg
An edge is specter if it is removed then the number of connected
components in the graph increases. Edges marked ted are special in the above figure.

Task

Determine the number of unordered pairs of modes luv such that each
and every Simple path (path with no edges repeated) between node u
and node v consists of exactly 1 special edge.
Notes:
Assume 1-based indexing
A connected undrected graph is a network of nodes connected by bicirectional edges such that we can move between any two nodes using some bidirectional edges
A simple path between 2 vertices contains distinct vertices only
Unordered pair means that (a,b) and (b,a) are considered to be the same

Example
Assumption

N = 4
M = 4
Edg = [(1,2),(2,3),(3,4),(2,4)]

Approach

The paths between the two nodes (1,2)(1,3)(1,4) consists of exactly one Special edge which is the edge [1,2]
Hence answer is 3

Function Description
Complete the function special_sol provided in the editor . This function takes the following 3 parameters and returns the required answer :

N represents the number of nodes in graph
M represents the number of edges in graph

Edg Represents a list of edges between two nodes in a graph

Input format

The first line contains T denoting the number of test cases . T also specifies the number of times you have to run the special_sol function on a different set of inputs
For each test case
- The first line contains a single integer N denoting the numbe rof nodes in the graph
- The second line contains a songle integer M denoting the number of edges on the graph
- Next M lines contains integers ui and vi denoting that there is an edge between vertex ui and vertex vi

Output format

For each test case in a new line , priint an integer denoting the number of unordered pairs (u,v) such that exactly 1 special edge

Constraints

1 ≤ T ≤ 10

1 ≤ N,M ≤ 2 x 10⁵

1 ≤ u_i,v_i≤ N

u_i≠ v_i

Sample Output

This question has code snippets for C CPP Java and Python

ADD COMMENT • link

Entering edit mode

Solution to Question 1 - Maximum Balls

Analysis

In the question it is mentioned that we can change the marks of a single student to any positive integer, and then find the maximum number which is a factor of all the marks. So the maximum number which divides all the marks will be the GCD (Greatest Common Divisor) of all the marks.

Now, since we can change a single number, assume we change the marks of student i (1-based indexing). Then, we can change it to the GCD of the remaining N-1 numbers. This is because the final GCD will be less or equal to the GCD of the remaining N-1 numbers. To make it equal (maximum possible), we keep it as the GCD of the N-1 numbers since gcd(a, a) = a.

So for each index i from 1 to N, if we assume that we'll be changing this number, we need to find the GCD of the remaining numbers. This can be broken down into GCD(gcd of students 1 to i-1, gcd of students i+1 to N). So we can create two arrays, a prefix array and a suffix array which store the GCDs of prefixes and suffixes respectively. Then we simply calculate the final GCD and take maximum over all indices i.

Implementation

ll n;
cin &gt; &gt; n;
vector &lt; ll &gt; a(n, 0);
for(ll i=0;i &lt; n;i++)
    cin &gt; &gt; a[i];
vector &lt; ll &gt; prefix(n, 0), suffix(n, 0);
prefix[0] = a[0];
for(ll i=1;i &lt; n;i++)
    prefix[i] = __gcd(prefix[i-1], a[i]);
suffix[n-1] = a[n-1];
for(ll i=n-2;i &gt; = 0;i--)
    suffix[i] = __gcd(suffix[i+1], a[i]);
ll ans = 1;
for(ll i=0;i &lt; n;i++)
{
    ll val;
    if(i==0)
    {
        val = suffix[i+1];
        ans = max(ans, val);
    }
    else if(i==n-1)
    {
        val = prefix[i-1];
        ans = max(ans, val);
    }
    else
    {
        val = __gcd(prefix[i-1], suffix[i+1]);
        ans = max(ans, val);
    }
}

ADD COMMENT • link 2.1 years ago Yash Sahijwani 940

Entering edit mode

Solution to Question 2 - Special Edge

Analysis

In the question it is mentioned that a special edge in a graph is an edge, which when removed, results in the graph getting disconnected or in other words, there exist 2 nodes u and v in the graph, such that there was a path between them in the original graph, but removing this special edge resulted in the fact that there is no longer a path between nodes u and v. These edges in a graph are known as bridges. You can read more about this here.

So, we want to calculate the total number of pairs of nodes (u, v), such that there is only a single bridge in the path between u and v. So, we first need to find the bridges in the graph. This can be done using the concept of intime with DFS (Depth First Search) Traversal. Say there is an edge (u, v), where u is the parent of v, then if there is a back edge from v or any other descendants of v to u or any of its ancestors, then the edge (u, v) is not a bridge. You can read more about finding bridges here.

Now, once we have all bridges, we remove them from the graph. This will give us multiple disconnected components. Say the count of such disconnected components is x, then the number of bridges can be at max x-1. This is because if we consider the disconnected components to be nodes, these nodes will form a tree when we add the bridges. If the form a graph with a cycle, this means that those edges we added are not bridges, since even after removing one of them, the nodes will remain connected. So at max, the number of bridges will be x-1.

Now, each bridge will connect one connected component to the other. So we can iterate over all bridges, and see which connected components are connected by this bridge. Then the total number of pairs of nodes (u, v) which have only this bridge in their path will be total[a] * total[b], where total is the number of nodes in the connected component.

Implementation

void dfs(ll root, ll parent, ll time, vector&lt; vector&lt; ll &gt; &gt;  &amp;adj, vector &lt; bool &gt; &amp;visited, vector &lt; ll &gt; &amp;intime, vector &lt; ll &gt; &amp;low, vector &lt; pair &lt; ll,ll &gt; &gt; &amp;bridges)
{
visited[root] = true;
intime[root] = time;
low[root] = time;
for(auto u:adj[root])
{
    if(u==parent)
        continue;
    if(visited[u])
        low[root] = min(low[root], low[u]);
    else
    {
        dfs(u, root, time+1, adj, visited, intime, low, bridges);
        low[root] = min(low[root], low[u]);
        if(low[u]&gt;intime[root])
            bridges.pb({root, u});
    }
}    
return;
}

void dfs_traversal(ll root, vector &lt; vector &lt; ll &gt; &gt; &amp;adj, ll number, vector &lt; ll &gt; &amp;numbers)
{
numbers[root] = number;
for(auto u:adj[root])
{
    if(numbers[u]!=0)
        continue;
    dfs_traversal(u, adj, number, numbers);
}
return;
}

void solve()
{         
   ll n,m;
  cin &gt; &gt; n &gt; &gt; m;
  vector &lt; vector &lt; ll &gt; &gt; adj(n+1);
  for(ll i=0;i &lt; m;i++)
   {
    ll u,v;
    cin&gt;&gt;u&gt;&gt;v;
    adj[u].pb(v);
    adj[v].pb(u);
  }
 vector &lt; bool &gt; visited(n+1, false);
 vector &lt; ll &gt; intime(n+1, 0);
 vector &lt; ll &gt; low(n+1, 0);
 vector &lt; pair &lt; ll,ll &gt; &gt; bridges;
 dfs(1, 0, 1, adj, visited, intime, low, bridges);
 set &lt; pair &lt; ll,ll &gt; &gt; bridges_deletion;
for(ll i=0;i &lt; (ll)bridges.size();i++)
{
    bridges_deletion.insert({bridges[i].first, bridges[i].second});
    bridges_deletion.insert({bridges[i].second, bridges[i].first});
}
vector &lt; vector &lt; ll &gt; &gt; adj_updated(n+1);
for(ll i=1;i &lt; = n;i++)
{
    for(ll j=0;j &lt; (ll)adj[i].size();j++)
    {
        ll u = i;
        ll v = adj[i][j];
        if(bridges_deletion.find(make_pair(u, v))!=bridges_deletion.end())
            continue;
        adj_updated[u].pb(v);
    }
}
vector &lt; ll &gt; component_number(n+1, 0);
ll comp_number = 1;
for(ll i=1;i &lt; = n;i++)
{
    if(component_number[i]==0)
        dfs_traversal(i, adj_updated, comp_number, component_number);
    comp_number++;
}
vector &lt; vector &lt; ll &gt; &gt; components(comp_number);
for(ll i=1;i &lt;  = n;i++)
    components[component_number[i]].pb(i);
vector &lt; ll &gt; total(n+1, 0);
for(ll i=1;i &lt; comp_number;i++)
{
    for(ll j=0;j &lt; (ll)components[i].size();j++)
    {
        ll node = components[i][j];
        total[node] = components[i].size();
    }
}
ll ans = 0;
for(ll i=0;i &lt; (ll)bridges.size();i++)
{
    ans += total[bridges[i].first] * total[bridges[i].second];
}
cout &lt; &lt; ans &lt; &lt; '\n';
return;

}

ADD COMMENT • link 2.1 years ago Yash Sahijwani 940