Join Us
Loading Similar Posts
Entering edit mode
Avg CTC: 18lpa
Job Roles: Software Engineer, Developers and Test leads
Application link: Fresher SE role
Question 1
Stone Cold Mafia
Click here to Practice
Submit Problem to OJ
Stone Cold is an American actor, producer, television host, and most importantly a famous professional wrestler. He has invented a new game which he named on himself - Stone Cold Mafia. In the game, you need to arrange his trophies on a tray. The size of tray is N and different types of trophies are K.
You want to place these trophies on the tray next to each other such that no trophy of the same type is sitting adjacent. Also, there is a special trophy X which means trophies of type X are allowed to place adjacent to each other.
Find the number of such possible arrangements mod 109 +7
Input format
- First line of input: Contains T, where T is number of test cases.
- For every test case: The first line contains N. K. and x, where N is the size of tray. K is the type of trophies available, and X is the special trophy that is allowed to place adjacent.
Note: X can be greater than K.
Output
For every test case print the number of arrangements mod 10^9 +7
Constraints
- 1 <= N <= 10^5
- 1 <= X,K <= 5
Sample Input
2
3 2 1
5 4 3
Sample Output
5
469
Question 2
Click here to Practice
Submit Problem to OJ
Connecting the special nodes
You are given a graph of N nodes. The graph consists of connected components.The definition of a connected component being a group of nodes in which any two nodes have a path to eachother, direct or indirect. Some of the connected components contain a special node and each component contains at most one special node. You are required to maximize the number of edges in the given graph such that it follows these constraints:
- No self-loop or multiple edges should be present
- No connected components with more than one special node should be present
- Each node in the graph should belong to a component with exactly one special node
If you add an edge between two nodes that belong to the same component in the graph, then the total cost involved is 0. Whereas, if you connect two nodes that belong to different components, then the cost is equal to the product of the sizes of both the components.
Your task is to maximize the number of new edges in the graph that can be added. Also calculate the minimum cost that will be involved in performing this required task.
Input format
- First line: Three integers N, M, and K representing the number of nodes, number of edges, and number of special nodes in the graph respectively
- Next M lines: Two integers u and v representing an undirected edge from the node u to node v
- Next line: An empty line
- Next line: K space-separated integers each representing the special nodes in a connected component
Output Format
Print the maximum number of new edges that can be added to the graph and the minimum cost of doing so.
Constraints
1 <= N <= 10^5
1 <= M <= 2*10^5
- K is the total number of connected components present in the graph.
- It is guaranteed that for any connected component at most one special node exists.
- The given graph does not contain any self-loops or multiple edges.
Sample Input
12 7 2
1 2
1 3
4 5
4 6
5 7
9 10
11 12
1 4
Sample Output
32 28
Question 3
Click here to Practice
Submit Problem to OJ
Shopping with Wife
Sam is visting a shopping mall. If this mall is mapped to a 2D plane - each coordinate point inside this mall (including the borders) would represent a shop. The bottom-left and top-right coordinates of this mall are (x1,y1) and (x2,y2) respectively.
Sam's wife is standing at a point (xC,yC) either inside or outside the mall.
Sam, being a careful husband, wants to always be within a distance of R from his wife. What are the total number of shops that Sam can visit.
Input format
- The first line contains four integers x1, y1, x2, y2 (x1 < x2 and (y1 < y2)
- The second line contains three integers xC, yC, R.
Output format
Print one number denoting the number of shops that Sam can visit considering above restrictions
Constraints
-100000 <= x1, y1, x2, y2 <= 100000
-100000 < (xC,yC) < 100000
0 <= R <= 100000
Entering edit mode
Solution for Question 1 - Stone Cold Mafia
Analysis
In the question, it is mentioned that we have K different types of trophies, and we want to place N trophies on the tray such that no two trophies of the same type are adjacent to each other. Also, we are given that the trophies of type X can sit adjacent to each other. We also assume that we have an infinite amount of trophies of each type since it is not mentioned in the question explicitly if there is any upper limit on the number of trophies of each type.
So, we can approach this problem using Dynamic Programming. In Dynamic Programming, we need to define an appropriate state for the problem and then its transitions. Hence, for this problem we can define the state as (index at which next trophy has to be placed, type of trophy placed at the last index). Let us denote this as dp[i][type]. Hence, dp[i][type] means that we are at the index i, and we need to place a trophy here. At index i-1, the trophy that has been placed is of type type, then the number of ways in which we can arrange trophies.
Hence, our answer will be dp[1][0], i.e. the number of ways we can arrange trophies, given that we are starting at index 1, and the type of trophy before this is 0 (i.e. no trophy has been placed before this).
Now our transition for the state will be defined as:
if (type!=x)
dp[i][type] = dp[i+1][1] + dp[i+1][2] + ... + dp[i+1][k] - dp[i+1][type] i.e. we can take all different types of trophies at position i, except the trophy which has the same type as the previous trophy.
else if(type==x)
dp[i][type] = dp[i+1][1] + dp[i+1][2] + ... + d[i+1][k], since we can take all types of trophies.
Implementation
vector < vector < ll > > dp(n+2, vector < ll >(k+1, 0));
for(ll i=0;i < = k;i++)
dp[n+1][i] = 1;
ll prev_sum = 0;
for(ll i=1;i < = k;i++)
prev_sum += dp[n+1][i];
//prev sum holds dp[i+1][1] + dp[i+1][2] + ... + dp[i+1][k]
for(ll i=n;i > = 1;i--)
{
ll curr_sum = 0;
//curr sum will hold dp[i][1] + dp[i][2] + ... + dp[i+1][k]
for(ll j=0;j < = k;j++)
{
if(j==0 || j==x)
{
//we can choose any trophy so we add prev_sum
dp[i][j] = (dp[i][j]%mod + prev_sum%mod)%mod;
if(j==x)
curr_sum = (curr_sum%mod + prev_sum%mod)%mod;
}
else
{
//we can choose any trophy except that of type j
dp[i][j] = (dp[i][j]%mod + prev_sum%mod)%mod;
dp[i][j] = (dp[i][j]%mod - dp[i+1][j]%mod)%mod;
if(dp[i][j] < 0)
dp[i][j]+=mod;
curr_sum = (curr_sum%mod + prev_sum%mod)%mod;
curr_sum = (curr_sum%mod - dp[i+1][j]%mod)%mod;
if(curr_sum < 0)
curr_sum+=mod;
}
}
prev_sum = curr_sum;
}
ll ans = dp[1][0];
Entering edit mode
Question 2
Prerequisites
Graph Theory/DFS
Redefine Statement/Overview
Might be the question seems not clear to understand so we are just redefining it for a better understanding of the question.
Jenny is the mayor of a city named Delhi. The city is a bit special. It can be represented as an undirected graph having more than one connected component.
Each of the connected components may have its own single source of water supply. One major rule in Delhi imposed by Jenny is that water from different components must never be mixed together. Being a really generous mayor, Jenny wants to install more pipes in each component so as to facilitate the smooth circulation of water.
She wants to increase connections in each component by installing as many pipes as possible without breaking the rule. However, the connection of pipes is not easy and comes with a cost as well.
Jenny can connect cities within the same components without any cost, only connecting cities within two different components requires a price that is the product of the respective sizes of their components. (See sample for better explanation).
Jenny gives you the layout of Delhi Now she wants to know how many extra pipes she has to add and the minimum total cost of doing so.
Explanation/Approach
The given graph consists of 5 connected components.
(1,2,3), (4,5,6,7), (8), (9,10), (11,12).
- Here Drop symbol shows the supply of water and blue arrows shows the graph that we get as input and the black arrow shows the connection that we made in the connected component with 0 costs (as they are within the same component) while the red arrow shows the edges that require some cost while connected component.
- The number of edges that will be required to connect two connected components will be the product of the sizes of components that need to be connected.
- While the total number of maximum edges that are required here is the total number of new edges that we make inside connected components + external edges that are used to connect two different connected components.
1 is the water supply point in
(1,2,3)and 4 is the water supply point in(4,5,6,7).There is no water supply point in (8),
(9,10), and(11,12).
For (1,2,3):-
- We can add 1 edge from 2 to 3, cost = 0 (same component).
For (4,5,6,7):-
We will add 3 edges from 6 to 5, 6 to 7 and 4 to 7. Now we can't add more edges to this component, cost = 0 (same component).
For the remaining nodes (without water supply points):-
We will first connect
(8)and with(11,12)cost 2 and 2 edges.Then
(8,11,12)and(9,10)with cost 6 and 6 edges. (product of their sizes).Now we have all the non-water supply points completely connected.
We can now connect all 5 non-water supply points to the component (4,5,6,7) with cost 20 and 20 edges.
Hence total cost is 28 and the maximum number of edges that can be added is 32.
- The approach is quite greedy in that we will be finding the number of connected components and the size of each connected component using DFS or BFS.
- After that count the number of edges that are required to be added within the connected component that requires 0 costs.
- Moving ahead we will be greedily cnt the number of edges that are required to connect two different connected components.
Pseudo Code
vector<int> graph[200001];
bool visit[200001];
int sz = 0;
int eg = 0;
int deg[200001];
vector<pair<int,int> > watered;
vector<pair<int,int> > dry;
void dfs(int node)
{
sz++;
visit[node] = 1;
eg += deg[node];
for(int i: graph[node])
{
if(visit[i] == 0)
{
visit[i] = 1;
dfs(i);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
int n , m , k;
cin >> n >> m >> k;
for(int i = 0; i < m; i++)
{
cin >> u[i] >> v[i];
graph[u[i]].push_back(v[i]);
graph[v[i]].push_back(u[i]);
++deg[u[i]];
++deg[v[i]];
}
for(int i = 0; i < k; i++)
cin >> w[i];
LL ans1 = 0 , ans2 = 0;
LL maxsz = 0;
for(int i = 0; i < k; i++)
{
sz = 0;
eg = 0;
if(visit[w[i]] == 1)
continue;
dfs(w[i]);
maxsz = max(maxsz , (LL)sz);
eg /= 2;
watered.push_back(make_pair(sz , eg));
ans1 += (sz * (sz - 1)) / 2 - eg;
}
for(int i = 1; i <= n; i++)
{
if(visit[i] == 0)
{
sz = 0;
eg = 0;
dfs(i);
eg /= 2;
dry.push_back(make_pair(sz , eg));
ans1 += (sz * (sz - 1)) / 2 - eg;
}
}
sort(watered.begin() , watered.end());
LL pre = 0 , cur = 0;
for(int i = 0; i < dry.size(); i++)
{
ans2 = ans2 + pre * dry[i].first;
ans1 += pre * dry[i].first;
pre += dry[i].first;
}
ans2 += pre * maxsz;
ans1 += pre * maxsz;
cout << ans1 << " " << ans2;
}
Entering edit mode
Question 3
Overview
- Given the bottom left and top right coordinates the mall and each point in the mall represents a shop.
- Also Sam's wife coordinate is given which can be inside or outside the mall.
- What is the total number of shops Sam can visit such that he always remains within a distance of R from his wife?
Solution
- Let us assume that at any point in time Sam's coordinate is (x, y), and Sam's wife's coordinate is fixed at (xc, yc).
- Then according to equation of circle we get (x-xc)^2+(y-yc)^2 <= R^2.
- Now we need to find how many x and y satisfy the above equation and also is a shop.
- To achieve this we will iterate over all possible x coordinates that can be a shop and binary search over y in 2 different zones that are (-100000,yc)(yc+1,100000).
- In this way, we can get all possible y coordinates as well hence the total number of (x,y) coordinates.
