Question: DBOI OA | SGSITS Indore | Candle Bunch | One Block | Minimum Maximum Distance | 2023
9
Entering edit mode

QUESTION 1

Candle Bunch

Mary has baked K cakes and she wants to put numbered candle on top of eadd of them, She wants to put candies numbered 1,2, . .., K on the cakes (one candle on each cake). She went to the store to buy candles. The candle shop has a row of N candle boxes. The shopkeeper will sell only a consecutive subset of
candles. Mathematically, Mary can choose L and R (1 <= L <= R <= N) and she can buy the candles candle[L], candle|L + 1], . .., candle[R], considering 1-based
indexing. Since Mary does not want to spend extra money, She wants to buy the minimum number of candles to get her desired candles.
You are given a row of candles. Find out the minimum number of
candles that Mary has to buy in order to have at least the candles
numbered 1, 2,...,K.
Note: All the boxes in the stack have one unique numbered candle.

Function description
Complete the function solution(). The function takes the following 3
parameters and returns the solution:
•M:Represents the number of boxes of candles
•K: Represents the number of candles Mary needs
• candle: Represents the row of candle boxes

Input format
Note: This is the input format that you must use to provide custom
Input (available above the Complle and Test button)
•The first line contains N denoting the number of boxes of candles.
• The second line contains K denoting the number of candles Mary needs.
• The third line contains an array candle denoting the row of candle boxes.
Output format
Print an integer denoting the minimum number of candles Mary must buy.
Constraints
1<=K<=N <=105
1 ≤ candle[i] ≤ N

Sample Input:

7 
3
4 5 3 1 7 2 6 

Sample Output:

4

Explanation
Given

Input
• N = 7                                                                                                                                                                                                                           • K = 3
• candle = [4,5,3,1,7,2,6]
Output: 4
Approach
It Mary buys the candles from the 3rd position to the 6th position, she will have [3, 1, 7, 2]. These are the minimum candles she needs to buy.


QUESTION 2

One block

You are working in the resource distribution team of your company A One block Is a block of data having exactly one resource which has value 1. You are given an array Arr containing N resource values.
What is the number of ways to divide the array into continuous
blocks such that each block is One block.
Function description
Complete the function OneBlock() which takes an integer N and an array Arr. This function takes the following 2 parameters and returns the required answer:
•N:Represents the number of resources
•Arr: Represents the value of resources
Input format for custom testing                                                                                                                                                                         Note:Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code
• The first line contains an integer N denoting the number of resources.
• The second line contains N space-separated integers denoting the value of resources.
Output format 

Print the number of ways to divide the array into continuous blocks such that each block Is One block.
Constraints
1 ≤ N ≤ 100
0 ≤ Arri ≤ 1

Sample Input:
3
0 1 0

Sample Output:
1

Explanation
Given
• N= 3
• Arr=[0, 1, 0]
Approach
There is exactly one resource that has the value of 1. Hence, the number of
ways is 1.

Sample Input 1:
5
1 0 1 0 1

Sample Output 1:
4

Sample Input 2:
10
0 0 1 0 0 0 1 1 0 1 

Sample Output 2:
8

Note:
Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases.Therefore, your code must pass these hidden test cases to solve the problem statement.
Limits
Time Limit: 1.0 sec(s) for each input file
Memory Limit 256 MB
Source Limit: 1024 KB
Scoring
Score is assigned if any testcase passes


QUESTION 3:

Minimum maximum distance

The Department of Parks and Recreation wants to minimize the maximum distance between any two trees in the city by cutting exactly one tree. The trees' locations are represented by coordinates (x,y) where x and y are the distances from the x axis and y axis, respectively. The distance between two trees is defined as the Manhattan distance between them. Find the minimum possible maximum distance between any two trees by cutting exactly one tree.
Function descriptionComplete the function solve() which takes as input an integer N denoting the number of trees in the city and a 2-D integer array trees denoting the coordinates of the trees.
Input format for custom testing
Note: Use this input format if you are testing against custom input or writing code in a language
where we don't provide boilerplate code
•The first line contains N denoting the number of trees in the city.
• The next N lines contain 2 space-separated integers each - Xi, Yi
Output format                                                                                                                                                                                                       Print a single integer representing the minimum possible, maximum distance that can be achieved by cutting precisely one tree.
Constraints
3 <= N <= 1e3
1 <=Xi,Yi < =1e9

Sample Input 1:
5
2 4 
3 9
1 2 
3 7
2 8 

Sample output 1:
6

Sample Input 2:
6 
12 11
10 12
2 10
1 9
3 100
2 11

Sample output 2
13

Explanation
Here coordinates of the trees are [[1,2],[2,4],[2,6],[3,9],[2,8]]
dist(1,2)= |1-2| + |2-4| = 3
dist(1,3)=|1-2| + |2-6| = 5
dist(1,4)=|1-3| + |2-9| = 9
dist(1,5)=|1-2| + |2-8| = 7
dist(2,3)=|2-2| + |4-6| = 2
dist(2,4)=|2-3| + |4-9| = 6
dist(2,5)=|2-2| + |4-8| = 4
dist(3,4)=| 2-3| + |6-9| = 4
dist(3,5)=|2-2| + |6-8| = 2
dist(4,5)=| 3-2|+ |9-8| = 2
Initial max distance-=max(dist(1,2), dist(1,3), dist(1,4), dist(1,5),dist(2,3),dist(2,4), dist(2,5), dist(3,4),dist(3,5),dist(4,5))=max(3,5,9,7,2,6, 4,4,2,2)= 9
Now we cut the tree 1.
New max distance=max(dist(2,3), dist(2,4),dist(2,5), dist(3,4),dist(3,5),dist(4,5))=max(2.6,4,4.2.2)=6
It can be proved that 6 is the minimum maximum distance that can be achived

 

ADD COMMENTlink 11 months ago Delta 2.7k
Entering edit mode
0

Link

ADD REPLYlink 8 months ago
Prasanna
• 0
0
Entering edit mode

Anyone, solution of these !??

ADD COMMENTlink 11 months ago Bhutesh kumar Meher • 0
0
Entering edit mode
#includeusing namespace std; // 1ST ANSWER int main() { int n,k; cin>>n>>k; vectorv(n); for(int i=0;i>v[i]; } unordered_mapmp,mpp; for(int i=1;i<=k;i++)mp[i]++; int i=0,j=0,ans=INT_MAX; while(j
ADD COMMENTlink 11 months ago mrphenomenal • 10
Entering edit mode
2
#include<iostream>
using namespace std;

int main(){
  cout<<"Tum kehna kya chahte ho?"<<endl;
return 0;
}

 

ADD REPLYlink 11 months ago
Raunit Verma
• 80
Entering edit mode
0

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int arr[n+3];
    for(int i=0;i<n;++i)cin>>arr[i];
    map<int,int>mp;
    for(int i=0;i<n;++i){
        mp[arr[i]]=i;
    }
    int maxi=-1e8,mini=1e8;
    for(int i=1;i<=k;++i){
        maxi=max(maxi,mp[i]);
        mini=min(mini,mp[i]);
    }
    cout<<maxi-mini+1<<endl;
}

ADD REPLYlink 7 months ago
Yololo
• 20
0
Entering edit mode

sdfsd

Zcxzczxc

 

ADD COMMENTlink 11 months ago mrphenomenal • 10
0
Entering edit mode

yes

ADD COMMENTlink 11 months ago mrphenomenal • 10

Login before adding your answer.

APPLY NOWSimilar Posts
Loading Similar Posts