9 weeks ago

John 910

Hyderabad

Question 1

Hungry Rabbit

There is m*n table with a rabbit in one of the cell - rabbit is initiall at position [startR, startC] . rabbit is Hungry, want to eat something and crying. He is trying to come out of the table, rabbit is allowed to move to one of the four adjacent cells of a table, rabbit can move at most max no of moves(maxMoves).

Given integers m, n, maxMoves, startR, startC, return number of paths to move the rabbit out of the cell. The result might be very Large, return it using modulo 10^9+7

Example 1

Input m= 2, n = 2, maxMoves = 2, startR = 0, startC = 0

Output: 6

Example 2

Input m= 1, n = 3, maxMoves = 3, startR = 0, startC = 1

Output: 12

Constraints:

1 <= m, n <= 50

0 <= maxMove <= 50

0 <= startRow < m

0 <= startColumn < n

Sample input

1
4
3
0
1

Sample output

14

Question 2

OYO Expansion

OYO plans to expand its network by adding n new rooms numbered 0 to n-1 to your colony. You are given an expansion plan as a 0-indexed integer array previousRoom of length n, where previousRoom[j] indicates that you must build room previousRoom[j] before building current room j, and these two rooms need to be directly linked. Room 0 is built already, so previousRoom[0] = -1. When all the rooms are constructed according to the expansion plan, every room will be accessible from room 0.

You can only construct one room at a time, and connecting rooms are the only ones that allow you to move freely between them any room can be built as long as the previous room has already been built.

Returns the number of different orders in which all rooms can be built. Since the answer can be large, return it modulo 10^9+7

Example 1:

Input: n = 3
previousRoom[] = [-1,0,1] 
Output: 1
Explanation: There is only one way to build the additional rooms: 0 --- 1 --- 2

Example 2:

Input: n = 5
previousRoom[ ] = [-1,0,0,1,2]
Output: 6
Explanation: The 6 ways are:
0 --- 1 --- 3 --- 2 --- 4
0 --- 2 --- 4 --- 1 --- 3 
0 --- 1 --- 2 --- 3 --- 4
0 --- 1 --- 2 --- 4 --- 3
0 --- 2 --- 1 --- 3 --- 4
0 --- 2 --- 1 --- 4 --- 3

Question 3

War For Chocolates

Tuntun mausi challenged Hari and his team to solve a problem. Hari, Mohit and Sam are trying to solve this problem but are unable to do so. As you are a good friend of Hari, he asks for your help.

Given an array, For each element find the value of nearest element to the right which is having frequency greater than as that of current element. If there does not exist an answer for a position, then print '-1'.

Please help Hari and his team to solve this problem to get the Chocolates.

Input First line contains T denoting the no of test cases. First line of each test case contains N denoting the no of elements in array. Second line of each test case contains N integers (A1.......An) denoting the given array.

Output For each test case print space separated N numbers denoting the answer corresponding answer.

Constraints

20 points: T<=100 1<=N<=10^2 1=Ai<=10^2

80 points: T<=100 1<=N<=10^5 1<=Ai<=10^5

Time Limit 2.5 seconds

Sample input

    3
    10
    1 3 7 2 5 1 4 2 1 5
    5
    1 1 1 1 1
    6
    1 1 2 2 2 3

Sample output

   -1 2 2 1 1 -1 2 1 -1 -1 
   -1 -1 -1 -1 -1 
    2 2 -1 -1 -1 -1

11 months ago

Manas 310

Bānswāra

Question 2 - OYO Expansion

The problems is to find the count of topological orderings of a tree with a fixed root i.e 0.

Why tree? If we connect all the edges the structure form will be tree. Because there will be no room which will be connected with more than 1 incoming edge. (As there is only element in array corresponding to each index i.e room)

The total number of topological orderings = N! / (Product of size of subtrees for each node). N is total nodes i.e the size of given array. Size of Subtree for a given node = Size of each of its children + 1(counting current node as well).

In sample case 1: 0->1->2 Size array = {3, 2, 1} and N = 3. Answer = 3! / (3 2 1) = 1

In sample case 2: Size array = {5, 2, 2, 1, 1} and N = 5, Answer = 5! / (5 2 2 1 1) = 6

The formula generated is simply(not actually simple) a result of combinations. If you draw all the possible orders of sample case 2 then you come to this formula.

Explanation for the formula : lets take the example given in discussion: Size array = {5, 2, 2, 1, 1} and N = 5, Answer = 5! / (5 2 2 1 1) = 6 here we have total number (array size) 5 so total number of ways to arrange this 5 number is 5!. now we know that there are some restriction on the position of sum number in permutations. Like node with size of subtree 5, we have to ensure in each permutation this node will come first before its subtree Nodes. We have total 5 option for first position but there is only one node on position first that is correct, So we divide total number of ways by 5. (because in 1/5th part of total number we have a node in first position and rest are ahead of this).

11 months ago

Manas 310

Bānswāra

Question 1 : Hungry Rabbit

Main idea is that if we can reach some position in X moves then we can reach its neighbours in X+1 moves. Based on this idea, we make use of a 2-D dp array to store the number of ways in which a particular position can be reached. dp[i][j] will refer to the number of ways in which position (i,j) can be reached in some particular number of moves.

If we have the number of ways to reach every position in x-1 moves, then we can update the dp array for x moves as follows. dp[i][j] = dp[i−1][j] + dp[i+1][j] + dp[i][j−1] + dp[i][j+1]. The boundary conditions should be taken care of. Since the entire dp array is going to get updated, we should have a temporary array which will have the values for x-1 moves stored and then update the dp array with using the temporary array.

Initially we start with our dp array being assigned to 0. We initialise dp[x][y] = 1 , where x,y correspond to our starting position. After performing the operation for N moves we will have our answer by adding all the values of the cells which satisfy the boundary condition.

Complexity Analysis

Time Complexity : O(Nmn). We need to fill the n*m dp N times, and hence the complexity. \ Space Complexity : O(mn). We use only one dp and one temp array which are of size mn.

15 months ago

piyush • 50

Mumbai

#include<bits/stdc++.h>
using namespace std;

int fact(int n){
    if(n == 0 || n == 1){
        return 1;
    }
    else{
        return n*fact(n-1);
    }
}

void dfs(int i,vector<int> &visit,vector<int> adj[]){
    visit[i] = 1;
    
    for(auto child : adj[i]){
        if(visit[child] == 0){
            dfs(child,visit,adj);
        }
    }
}

int main(){
    
    int n;
    cin>>n;
    vector<int> pre;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        pre.push_back(x);
    }
    
    vector<int> adj[n];
    
    for(int i=1;i<n;i++){
        //adj[i].push_back(pre[i]);
        adj[pre[i]].push_back(i);
    }
    
    int ans =1;
    
    for(int i=0;i<n;i++){
        vector<int> visit(n,0);
        dfs(i,visit,adj);
        int sum = accumulate(visit.begin(),visit.end(),0);
        // cout<<ans<<"\n";
        ans = ans* sum;
    }
    
    cout<<fact(n)/ans;
    
}

Code of 2nd question

15 months ago

shhhh • 0

Mumbai

War for choclates o(n) solution

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n ;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0 ; i < n ; i++) cin >> arr[i];
    unordered_map<int, int> mp;
    for(auto it: arr) mp[it]++;
    
    stack<pair<int, int>> st; // freq -- ele
    vector<int> ans(n);
    
    for(int i = n-1 ; i >= 0 ; i--){
        if(st.empty()){
            ans[i] = -1;
            st.push({mp[arr[i]], arr[i]});
        }else if(st.top().first > mp[arr[i]]){
            ans[i] = st.top().second ;
            st.push({mp[arr[i]], arr[i]});
        }else{
            while(!st.empty() && st.top().first <= mp[arr[i]]){
                st.pop();
            }
            if(st.empty()) ans[i] = -1;
            else ans[i] = st.top().second;
            st.push({mp[arr[i]], arr[i]});
        }
        if(!st.empty()) cout << st.top().first << " " << st.top().second << endl;
    }
    
    for(auto it: ans) cout << it << " ";
    cout << endl;
}
int main() {
    int t ;
    cin >> t ;
    while(t--){
        solve();
    }
    return 0;
}

15 months ago

Nikunj Adhiya • 0

Mumbai

Question:- 3 

WAR FOR CHOCLATES

 

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int n;

    cin >> n;

    vector<int> v(n);

    unordered_map<int, int> m;

    for (int i = 0; i < n; i++)

    {

        cin >> v[i];

        m[v[i]]++;

    }

    stack<int> st;

    vector<int> ans(n);

    for (int i = n - 1; i >= 0; i--)

    {

        while (!st.empty() and m[st.top()] <= m[v[i]])

            st.pop();

        if (st.size() == 0)

        {

            ans[i] = -1;

        }

        else

        {

            ans[i] = st.top();

        }

        st.push(v[i]);

    }

    for (auto i : ans)

        cout << i << ' ';

    cout << endl;


    return 0;

}