10 weeks ago

Rohit • 610

Hyderabad

Question 1

Omega Primes

Carl is bored of playing with ordinary prime numbers. Thus, he comes up with some special numbers called Omega Primes.

A number X is called Omega Prime, if there exists no perfect square Y (Y > 1) such that Y divides X.

For example, 6 is an Omega Prime because there is no perfect square except 1 that divides 6.

On the other hand, 12 is not an Omega Prime as 4 (which is a perfect square) is a divisor of 12.

Carl decides to play a bit more with Omega Primes. He has an array A of integers. Carl wants to find the number of different subsets such that the product of elements for each subset, results in an Omega Prime. Help Carl find this number.

Since this number can be large, output the answer modulo 10^9 + 7.

Constraints

• 1 <= length of A <= 2*10^4
• 1 <= A[i] <= 30

Input Format

The first argument is the integer array A. . Output Format

Return an integer denoting the number of different desired subsets modulo 10^9 + 7.

Input 1

A = [2, 4, 3]

Output 1

3

Input 2

A = [2, 2, 2]

Output 2

3

Question 2

Fruits on Tree

Given a complete rooted tree with N nodes numbered 1 to N. This tree has its leaves at the top and root at the bottom.

A complete tree is a tree on every leaf of the tree and in order to get all the fruits you have to shake the tree any number of times.

But this tree is a little different than the rest it has following properties:

• Every node has its capacity value that represents the number of fruits a node can hold at any moment.
• Only one fruit falls from each node to its present node in one shake.
• If a number of fruits at a node is more than its capacity then excess fruits (greater than capacity) on that node at that instant will fall to the ground. This process happens instantaneously hence no shake is required.

The tree is rooted at 1. You may assume that root is one level above the ground so all fruits which fall from roots lands on the ground.

You have to find the minimum number of shakes you have to perform such that all the fruits are on the ground.

Constraints

• 1 <= N <= 10^5
• 1 <= A[i], B[i] <= 10^9
• 1 <= C[i][0], C[i][1] <= N
• A[i] = 0 for non-leaf nodes
• Initially A[i] <= B[i]

Input Format

First argument is an integer array A of size N where A[i] denotes the number of fruits on ith node.

Second argument is an integer array B of size N where B[i] denotes the capacity of ith node.

Third argument is a 2D array of size (N-1) * 2 denotes edges in tree. There is an edge between nodes C[i][0] and C[i][1].

Output Format

Return an integer denoting the minimum number of shakes you have to perform such that all the fruits are on the ground.

Input 1

A = [0, 0, 0, 1, 1, 2]
B = [1, 1, 1, 1, 1, 2]
C = [
        [1,2]
        [1,3]
        [2,5]
        [2,6]
        [3,4]
      ]

Output 1

4

Input 2

A = [0, 0, 5, 5]
B = [10, 3, 10, 10]
C = [
        [1,2]
        [2,3]
        [2,4]
      ]

Output 2

9

Question 3

Damaged Roads

You are the Prime Minister of a country and once you went for a world tour.

After 5 years, when you returned to your country you were shocked to see the condition of the roads between the cities. So, you plan to repair them, but you cannot afford to spend a lot of money.

The country can be represented as a N*M grid, where Country[i,j] is a city.

The cost of repairing a repairing a road between [i,j] and [i+1,j] is A[i]. The cost of repairing a road between [i,j] and [i,j+1] is B[i].

Return the minimum cost of repairing roads.

As the cost can be large, return the cost modulo 10^9+7.

Input Format

The first argument will be an integer array, A, of size N.

The second argument will be an integer array, B, of size M.

Output Format

Return an integer representing the minimum possible cost.

Constraints

• 1 <= N,M <= 1e5
• 1 <= A[i],B[i] <= 1e3

Example

Input 1

A = [1, 1, 1]
B = [1, 1, 2]

Output 1

16

Input 2

A = [1, 2, 3]
B = [4, 5, 6]

Output 2

39

20 days ago

Lokesh 310

Hyderabad

Question 2

*Overview:

• Given an inverted tree, with each leaf node having a certain number of fruits and each node having a certain capacity, and at a given sec one fruit from each node can move to its parent, then what is the minimum number of seconds needed so that the tree empties.

*Approach:

• First, note the constraints. All the leaf nodes have at least one fruit and all at the same level.
• This leads to the observation that for node i, if the first fruit moves from node 'ito its parent attime[i],` then every second after that until the final fruit is emptied, a fruit moves from it to its parent.
  • All the time points in which a fruit from node i to parent[i] is continuous, there is no break.
• The other observation first move from node i to parent[i] happens at depth[i], seconds. (this is because all leaves are the same level and have at least one fruits)
  • depth[leaf node] = 1
• Let:
  • ANS[i] be the minimum time needed to empty node i

    - `ans[i] = a[i]` for leaf node 
    

  • sum[i] is no of fruits that falls from its children.
  • Depth[i] is depth of node withdepth[leaf node] = 1`
• Now do a DFS.
  • sum[i] = sum(ans[child]-depth[child])

    - The first fruit falls at `(depth[i] = (depth[child]+1))`, the last fruit falls at ANS[i] , and it falls continuously
    - for each child no of fruits falling to the node `i` is `ans[child]-depth[child]`
    

    • maxi = max(ans[child])
    • ANS[i] = maxi + min(capacity[i], sum - (maxi - d[node])).
      • This is because the last fruit to fall into parent happens at maxi time.
      • After this time, the remaining fruit is sum - (maxi - d[node]). If this greater than capacity, those just fall off, that's why min with capacity[i]
        • (maxi - d[node]) is no of fruits that fell to parent[i] before last fruit reached node i

pseudocode:

vector<ll> ch[100005];
vector<bool> vis(100005, false);
vector<ll> ans(100005, 0);
vector<ll> a(100005);
vector<ll> b(100005);
vector<ll> d(100005, 0);
void dfs(ll node)
{
    vis[node] = true;
    ll sum = 0;
    ll maxi = 0;
    ll ct = 0;
    for (auto child : ch[node])
    {
        if (!vis[child])
        {
            dfs(child);
            if (ans[child] > maxi)
            {
                maxi = ans[child];
            }
            d[node] = max(d[node], d[child] + 1);
            sum += (ans[child] - d[child]);
            ct++;
        }
    }
    if (ct == 0)
    {
        ans[node] = a[node];
    }
    else
    {
        ans[node] = maxi + min(b[node], sum - (maxi - d[node]));
    }
}

8 months ago

Shikhar Mehrotra 480

Chennai

Q1)
Assuming not considering empty subset

Prerequistes

Dp,Dp with bitmasks

Solution

• If X is omega prime, it means that there exists no perfect square that could divide X perfectly, which means that X should be product of distinct primes or X=p1 p2 p3... * pk. where p1,p2...pk are distinct primes .
• Now the question is to count number of subsets such that product of elements of subsets result in a number which is product of distinct primes(i.e omega prime number) and also if product is omega prime then elements would be also omega prime.
• It could be solved by DP.
• Let dp[prod][val] represent count of number of subsets such that it contains elements with values < = val and product of the elements is prod and prod is omega prime.
• So we could transition dp[prod][val]=dp[prod][val-1](Not considering val)+(prod%val==0)?dp[prod/val][val-1]*frequency[val](Considering val if prod divisible by val):0 where frequency[val] represent count of numbers with values=val in given array.
• But Since a[i] < =30, then prod could be atmost (2 3 5 7 11 13 17 19 23 * 29) primes < = 30 which is too big to make dp array
• Representing prime{2,3,5,7,11,13,17,19,23,29}
• To avoid this issue we could treat prod as mask of above mentioned primes where mask's ith bit represents that whether we have included prime[i] (1) or not (0) prime[i] is 0-based(left to right)
• In the above mentioned transition , division check and divide could be changed with checking submask and XOR respectively because we are considering the values only which are product of distinct primes.
• So we could reform the above defined dp by : dp[mask(prod)][val]=dp[mask(prod)][val-1]+(if mask(prod) could be divided by val)dp[mask(prod) XOR val][val-1]
• Now for each valid subset we have picked we could put as many 1's available in the given array in that subset so that would be 2^(count of 1's in the array) combinations because out of all 1's we have to pick some 1's (we could also take no 1) .
• Finally our answer would be just sum of dp[mask][max_value in array] * 2^(count of 1's in array) over all mask=1....(1 < < max_primes)

Pseudo Code

for(int i=0;i < 32;i++)
        dp[0][i]=1; // if mask is 0(i.e not a product of prime) then taking empty set
for(int mask=1;mask < (1 < < max_primes);mask++) //iterating over all masks
    {
        for(int value=1;value < =30;value++)
        {
            dp[mask][value]+=dp[mask][value-1];
            dp[mask][value]%=MOD;
            if(freq[value] and valid(value))//check whether value is also a omega prime or not
            {
                int mask_pf=mask_generate(value); //creating mask of value
                //Suppose value=21(3*7) then mask_pf would be decimal of (0101000000)
                //Suppose value=6(2*3) then mask_pf would be decimal of  (1100000000)
                if(mask_pf is submask of mask)//checking whether mask (which is just product represent in mask ) is divisible by value
                {

                    dp[mask][value]+=(dp[mask^mask_pf][value-1]*freq[value])%MOD;

                    dp[mask][value]%=MOD;
                }
            }
        }
    }

2.0 years ago

Tayal • 40

Question 2

Approach

• This question is solved by using post traversal in the tree.
• You have to calculate at each node, the max time by which all its children are emptied plus self time by which the node itself will become empty.
  • The max time to empty of children, is simply max of left time and right time.
  • Time to empty self, is according to how many fruits it will have by the time all children empty. So when the children are empty and the node have x fruits left, then it will take x time to empty self.
• Some cases to handle
  • One thing you have keep in mind while calculating self time if that it could happen the parent was initially empty and thus the continuous passing of fruits was not there, at this situation it takes one extra self time to accommodate the first fruits, after which fruits will be transferred in continuous manner.
  • Also self can not have fruits more the its capacity, thereby when the child empties, the self will upper limits by its capacity of fruits.

Pseudo code

    int helper(vector<vector<int>> &adj, vector<int> &A, vector<int> &B, int i) {
        int left=0, right=0;
        int n = adj[i].size();
        if(n >= 1)
            left = helper(adj,A,B,adj[i][0]);
        if(n == 2)
            right = helper(adj,A,B,adj[i][1]);

        int childtime = max(left,right);

        int selftime = A[i-1] + min(left,right);    // self gets extra fruits only when both children are passing fruits
        if(n!=0 && A[i-1]==0) selftime += 1;        // if not leaf and have 0 fruits initially, it takes 1 more time to store to get continuous passing of fruits
        if(selftime > B[i-1]) selftime = B[i-1];

        return childtime + selftime;
    }

    int main() {
        vector<int> A = {0,0,5,5};
        vector<int> B = {10,3,10,10};
        vector<vector<int>> C = {{1,2},{2,3},{2,4}};

        int n = A.size();
        vector<vector<int>> adj(n+1);
        for(auto &c:C) {
            adj[c[0]].push_back(c[1]);
        }
        int ans = helper(adj,A,B,1);
        court << ans << endl;
}