1 day ago

Gigaliths 390

IIT Ropar

Recently Asked OAs in DE Shaw

Question 1: String Reversal 

Question 2

Question 3: Minimum Cost Path:

4 hours ago

Akash 150

Question 1: String Reversal

Overview

• Given the final string after performing m operations, determine the initial string.

Approach

• After working out a few cases, you can find the pattern and solve the problem.
•  For a string of size n, after m operations string will be rearranged like,

1. For an odd number of operations,        S_mS_m-2S_m-4…S₁S₂…S_m-1S_m+1S_m+2…S_n
2. For an even number of operations,      S_mS_m-2S_m-4…S2S1…S_m-1S_m+1S_m+2…S_n

•  After this, it is basic implementation to determine the initial string

Complexity

• O(|S|), |S| is the size of the string.

Pseudocode

    int n, m;
    string s;
    cin >> s >> m;
    n = s.size();
    string ans = s;
    int x = m - 1, i = 0;
    while (x >= 0) {
        ans[x] = s[i++];
        x -= 2;
    }
    x = (m % 2 != 0);
    while (x <= m - 2) {
        ans[x] = s[i++];
        x += 2;
    }
    cout << ans << endl;

2 days ago

Rishabh Verma 80

Solution 3 : minimum cost path

Overview : In this question we have to find the a path form node 0 to node n-1 such that the distance (number of edges) between the nodes are less than of equal to " max edge " and maximum weight among the these edges be minimum.

Approach : 

• suppose if you have fixed your cost and you have to do a dfs or bfs call from node 0 and check wether you reached to node n-1 as well as distance between node 0 and node n-1 is atmax "max edge". then you know the aswer will be definitely less than that fixed number.
• For this you can use binary search to fix the cost and everytime find the minimum distance from node 0 to node n-1 and that should be less than or equal to "max edge" (remember that we are we are using distance between 2 connected nodes is 1).

Time Complexity : O(log2(1e9)*(n+m)).

PseudoCode : 

void dfs(int node,vi &dis,vi &vis,int val){
    vis[node]= 1;
    for(pii cur:adj[node]){
        int ch = cur.ff,w = cur.ss;
        if(w<=val and vis[ch]==0){
            dis[ch] = dis[node]+1;
            dfs(ch,dis,vis,val);
        }
    }
}

while(r>=l){
    int mid = (r+l)>>1;
    vi dis(n,inf),vis(n,0);
    dis[0]= 0;
    dfs(0,dis,vis,mid);
    if(dis[n-1]<=k) ans = mid,r = mid-1;
    else l = mid+1;
}

1 day ago

hardik kapoor 80

Solution 2

Overview

In this question, we are given two integers, num1 and num2 (in form of string, as it can be bigger than integer range) and two integers (minsum and maxsum). Our task is to find the number of integers x s.t. num1 <= x <= num2 and minsum <= sum of digits of x <= maxsum. Length of num1 and num2 <= 100.

Approach

Such kinds of problems are more easily solved by digit DP. Hence, using DP, we will try to find the number of integers <= num, having sum of digits <= maxsum. Using this, we can find the number of integers <= num having sum of digits between minsum and maxsum by the following method:

Let f be the result of the dp, then f(num,maxsum) - f(num,minsum-1)  will give us required result.

Finding the same for num2 and num1-1 (as we have to remove all integers <= num1-1 from our result in num2), our final answer will just be the difference of f(num,maxsum) - f(num,minsum-1) between 'num2' and 'num1-1'.

The dp is formulated as follows:

• dp[i][f][sum], will be the states of the dp, where i will be the position of placing the integer from 0 to size(num)-1; 0 being the most siginicant place, f will be a flag variable, where 0 means that the current number is not a tight bound, and 1 means the current number is a tight bound (tight bound means all the siginficant digits before ith one is matching to num), and sum is the current sum of the digits of the number created.
• The state transitions will are self explainatory, see the psuedo code for more information.

Time Complexity

O(len(num2)^2) {as sum goes from 0 to 9*len(num2)}.

Pseudo Code

Contains Dp state and transitions only.

const int maxn=101;

int dp[maxn][2][maxn*10]={};

for(int i = 1;i < n;i++)
{
    for(char c = '0';c <= '9';c++)
    {
        if(c < num[i])
        {
            int currC=(c-'0');
            for(int s=currC;s<=maxsum;s++)
            {
                dp[i][0][s]+=dp[i-1][1][s-currC]+dp[i-1][0][s-currC];
                dp[i][0][s]%=mod;
            }
        }
        else if(c == num[i])
        {
            int currC=(c-'0');
            for(int s=currC;s<=maxsum;s++)
            {
                dp[i][0][s]+=dp[i-1][1][s-currC]+dp[i-1][0][s-currC];
                dp[i][0][s]%=mod;
                dp[i][1][s]+=dp[i-1][1][s-currC];
                dp[i][1][s]%=mod;
            }
        }
        else{
            int currC=(c-'0');
            for(int s=currC;s<=maxsum;s++)
            {
                dp[i][0][s]+=dp[i-1][0][s-currC];
                dp[i][0][s]%=mod;
            }
        }
    }
}