Question: Hilabs, Recently Asked Questions in IITs, November 2022
0
Entering edit mode

# Question 2

## Special Edge

2
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);
}
}
``````
2
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;
{
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;
{
if(numbers[u]!=0)
continue;
}
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;
}
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++)
{
{
ll u = i;
if(bridges_deletion.find(make_pair(u, v))!=bridges_deletion.end())
continue;
}
}
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)
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;
``````

}