Entering edit mode

**Avg CTC:** 20lpa

**Job roles:** Software Engineer, Backend Developers, Program Analyst and more

**Job List:** Positions open for Uber, India

Click here to Practice

Submit Problem to OJ

There are some job opportunities in one company. And there are some candidates for these jobs. Candidate can be hired for the ith job if he has all skills that are needed for this job. There are some distinct skills which can be needed for jobs. Company needs only one person for each job. Moreover each candidate can be hired only for one job and the profit of hiring somebody for the ith job is profits[i]. Profit of hiring for the set of jobs equals to sum of profits of each job in set. For the empty set it's 0.

Your task is to calculate a maximum profit after hiring a subset of candidates for a subset of jobs.

**Example**

For profits = [4, 10], skillsForJobs = [[true, false], [false, true]], and skillsOfCandidates = [[true, true], [true, false]], the output should be

solution(profits, skillsForJobs, skillsOfCandidates) = 14;

For profits = [5], skillsForJobs = [[true]], andskillsOfCandidates = [[true]], the output should besolution(profits, skillsForJobs, skillsOfCandidates) = 5.

**Input/Output**

[execution time limit] 0.5 seconds (cpp)

[input] array.integer profits

**Guaranteed constraints:**

1 <= profits.length <= 50

0 <= profits[i] <= 106.

[input] array.array.boolean skillsForJobs

If skillsForJobs[i][j] = true then candidate for ith job must have skill with number j.

**Guaranteed constraints:**

skillsForJobs.length = profits.length

skillsForJobs[i].length = skillsForJobs[0].length

1 <= skillsForJobs[i].length <= 50

[input] array.array.boolean skillsOfCandidates

If skillsOfCandidates[i][j] = true then ith candidate has skill with number j.

**Guaranteed constraints:**

1 <= skillsOfCandidates.length <= 50

skillsOfCandidates[i].length = skillsForJobs[0].length

[output] integer

Given 3 positive integers K, L, N where *K* <= *L* <= *N*

A integer set T of size L is called good if all integers in T are distinct and in range [1,*N*].

Let S be the set of all such possible sets T of given length *L*.

Let A be the uniformly and randomly chosen set from S, J*A* be the smallest integer in set A. Find sum of J*A* modulo 998244353 over all such good sets *A*.

Since the problem is too easy for you, you will have to solve this for *Q* such query.

Input is given in form of 3 arrays *Ks*, *Ls*, *Ns* each of size *Q*.

*ith* query consists of *K = ks[i], L = ls[i], N = ns[i]*

**Constraints:**

- 1 <= Q <= 10^3
- 1 <= K <= L <= N <= 10^6

**Sample Input**

```
ks: [2, 1, 2, 3]
ls: [2, 1, 2, 3]
ns: [3, 1, 2, 3]
```

Sample Output:

```
[8, 1, 2, 3]
```

Here one has to solve for four different queries-

- K = L = 2, N = 3
- K = L = N = 1
- K = L = N = 2
- K = L = N = 3

Click here to Practice

Submit Problem to OJ

So Mr.George recently joined college and he is too much fascinated by patterns. He was able to implement the following star pattern-

```
*
**
****
******
********
```

in which the no. of asterisk at a level N is N.

Now instead of just Asterisk, Mr.George also decided to use small alphabet o

So Patterns may look like these -

```
**
oooo
******
********
oooooooooo
```

But he won't mix a row with both 'o' and '*'

Now given He has A no. of 'o' and BB no. of '*'

Tell the total ways he can implement a star pattern.

Since this no. can be very large, return it modulo 998244353998244353.

**Explanation**

Sample Case 1

Asterisk - 2

Alphabet o - 2

Possible patterns -

```
**
oo
**
oooo
oo
****
```

[execution time limit] 4 seconds (cpp)

[input] integer a

denotes the max no. of asterisk we can use.

1 <= a <= 1e51 <= a <= 1e5

[input] integer b

denotes the max no. of alphabet o's we can use.

1 <= b <= 1e51 <= b <= 1e5

[output] integer

find the total no. of ways of creating star patterns with given Asterisk and Alphabet o's

Entering edit mode

Lets first find the maximum height of such a pattern. We can note that the maximum height of the pattern by using atmost `a`

asteriks and `b`

o's will be the same as of that obtained by using atmost `a+b`

characters of the either type. This can be proved as follows:

- First assume that you have created a pattern of the maximal height and now you have to decide the characters to be put on the rows.
- Lets greedily start putting the asteriks on the rows with the largest width possible until we either run out of the asteriks or we dont have sufficient asteriks to be put on the largest row remaining. We can now use the remaining asteriks (if any) to fill the floor with the width equal to the remaining asteriks (we can always do this as we rows with consecutive widths).
- It can be seen that you can easily fill the rest of the floors with the o's.

Now to obtain the maximal height, we need to find the largest `h`

such that `h*(h+1)/2 <= a+b`

. We can do the same using either binary search or even simple math.

Now to solve the original problem , we will use **dynamic programming**. Let `dp[height][cnt_*][cnt_o]`

denote the number of ways to create the patterns of height `height`

and we are currently left with `cnt_*`

asteriks and `cnt_o`

o's. We can do the following transitions for this dp:

- We can place asteriks on the next row (if possible) and update
`dp[height+1][cnt_* - height+1][cnt_o]`

. - We can place o's on the next row (if possible) and update
`dp[height+1][cnt_*][cnt_o - height+1]`

.

The final ans to the problem can be obtained by summing up the dp values for patterns of heights from 1 to `h`

. Thus we solve the problem in a time complexity of `O(h*a*b)`

. Since `h`

is atmost `sqrt(a+b)`

, the total complexity is `O(sqrt(a+b)*a*b)`

. This however TLEs for the constraints.

**How to optimize the dp ?**

We can optimize the dp simply by reducing the state of dp. We only need to keep either of `cnt_*`

or `cnt_o`

in the dp state as the other can be simply obtained by subtracting the first one from the total characters placed. Thus the problem is now solved in a time complexity of `O(sqrt(a+b)*min(a,b))`

.

For an interview setup, you may be asked to code the dp with the minimal space. The following Code(C++) does the same and solves the problem in a space complexity of `O(min(a,b))`

and time complexity of `O(sqrt(a+b)*min(a,b))`

.

```
int solve(int a, int b)
{
int lo = 1, hi = 1000, h = -1; //h is the maximum height of such a tower
while(hi >= lo)
{
int mid = mid(lo,hi);
if((mid*(mid+1))/2 <= a+b)
{
h = mid;
lo = mid+1;
}
else hi = mid-1;
}
if(!a) swap(a,b);
vector<int> dp(a+1,0); //dp[x] denotes the number of ways to create patterns and having x asteriks left
//place o in the first row
if(a) dp[a] = 1;
//paint asterisk in the first row.
if(b) dp[a-1] = 1;
int ans = 0;
for(int height=1; height<h; height++)
{
for(int asteriks_left = 0; asteriks_left<=a; asteriks_left++)
{
ans = (ans + dp[asteriks_left])%mod;
int o_left = b - ((height*(height+1))/2 - (a-asteriks_left)); //calculate the no of o left using math
if(asteriks_left >= height+1) dp[asteriks_left - (height+1)] = (dp[asteriks_left - (height+1)] + dp[asteriks_left])%mod; //place asteriks in the next row.
if(o_left < height+1) dp[asteriks_left] = 0;
}
}
for(int asteriks_left = 0; asteriks_left<=a; asteriks_left++) ans = (ans + dp[asteriks_left])%mod;
return ans;
}
```

Entering edit mode

**Analysis**

Let's first make a **graph** where the nodes are the jobs and the candidates, and if candidate i is a fit of job j add an edge of weight profit[j] between candidate i and job j. Note that this graph is **bipartite** as the only edges are from jobs to candidates. So now our problem reduces to finding a set of independent edges (i.e. edges that do not share a node) that has maximum weight as there exists only a single candidate for a single job and vice versa. Hence what we are looking for is the **maximum weighted matching** of a bipartite graph as the set of independent edges forms a matching. This is a very well-known problem and many algorithms like the Hungarian algorithm and Linear Programming algorithms exist to solve exactly the same problem. Note that the constraints are so low that it even allows the general weighted matching using Blossom's algorithm to pass.

```
int solve(vector<vector<bool>> jobs,vector<vector<bool>> candidates,vector<<ll>profits){
graph.initialize();
for(vector<bool> job:jobs){
for(vector<bool> candidate:candidates){
if(match(candidate,job)){
add_edge(candidate,job,price_of_job);
}
}
}
return blossom(graph);
}
```

Loading Similar Posts