18 months ago

Gigaliths 570

IIT Ropar

Recently Asked OAs in DE Shaw

Question 1: String Reversal 

Question 2

Question 3: Minimum Cost Path:

String Reversal

A series of numoperations are performed on a string initial_string of length n that contains lowercase English letters only. In the it operation, the prefix of the string of length / is reversed. The final string thus formed is represented by final string. Given the string final_ string and an integer num_operations, find the initial_string on which the operations were performed.

Example
Suppose final_string = "chakerrank" and num_operations = 3.
Then the initial string will be "hackerrank".
On the first operation, reverse "h" -> "hackerrank"
Reverse "ha" -> "ahckerrank"
Reverse "ahc" -> "chakerrank" which is equal to the final string.
Hence the answer is "hackerrank".

Function Description
Complete the function getinitialString in the editor below.
getinitialString takes the following arguments:
str final_string: The final string formed
int num operations: The number of operations performed
Returns
str. The initial string that results in the given string
Constraints
• 1≤ |final_string| ≤ 2 * 10⁵
• 1 ≤ num_operations ≤ | final_string|

STD In                     Function
bbaaaba   --->           final_string = "bbaaaaba"
Sample Output
aababba


Question 2
Given two strings, num, and num2, containing digits from 0 to 9 that represent
two integers. You are also given two integers, min sum, and max sum. Find the
number of integers x such that num1 ≤ x ≤ num2 and min_ sums ≤ sum of digits of
x ≤ max_sum. Since the answer can be large, report it modulo 10⁹ + 7.
Example
Suppose min_ sum = 3, max, sum = 7, num 1 = 18 and num2 = 26.
The numbers in the range [18, 26] and their sum of digits are:

• 18, the digit sum is 9
• 19, the digit sum is 10
• 20, the digit sum is 2
• 21, the digit sum is 3
• 22, the digit sum is 4
• 23, the digit sum is 5
• 24, the digit sum is 6
• 25, the digit sum is 7
• 26, the digit sum is 8
   

STD In                                  Function
24                  --->           num1 = "24"
29                  --->           num2 = "29"
2                    --->          min_sum = 2
6                    --->          max_sum = 6

Sample Output 
1

3. Minimum Cost Path
A weighted directed graph can be represented with g. nodes nodes numbered from 0 to g_nodes • 1 and g_edges edges where the hedge connects the nodes,
numbered g_from[i) to g_toli] and has a weight g weight[o). The cost of a particular
path between two nodes is defined as the maximum weight of any edge that exists
in the path.
Given g_ nodes, g_edges, & from, g_to, and max_edges, find the minimum cost of a path from the node 0 to g_nodes - 1 that contains at most max_edges edges. If no
such path exists, report -1.
Example
Suppose &_ nodes = 4, g. edges = 5, max_edges = 2, g. from = [0, 1, 0, 2, 2], g. to = [1,3, 2, 3, 2], and g weight = (5, 6, 6, 5, 5].
The optimal path is from node 0 to 1 to 3 with the weights of the edges 5 and 6 respectively. Thus, the cost of the path is 6. Another path with cost 6 is 0 to 2 to 3.
Note that the path 0 to 1 to 2 to 3 has a cost 5 but can not be chosen as the number of edges in the path i.e. 3 is greater than max_edges = 2.

Function Description
Complete the function getMinCost in the editor below. getMinCost takes the following arguments:
int max_edges: the maximum number of edges to be taken in the path
int g_nodes: the number of nodes in the graph
ints. edges) & from: one end of the edges in the graph
inti[g_edges] g. to: the other end of the edges in the graph
int[g_edges] g weight: the weights of the edges in the graph
Returns
int: the minimum cost of the path from 0 to &_ nodes - 1 with at most max edges
edges.

constraints
•1 ≤   g_nodes ≤  5*10⁵
• 1 ≤ g_edges smin(2 * 10⁵, g_nodes * (g nodes - 1))
• 1 ≤ g_from[i], & from(i] s g_nodes, g_from(i] != g. toli]
• 1 ≤ g_weightti] ≤ 10⁹
• 1 ≤ max_ edges ≤ g_edges

29 days ago

Akash 240

New Delhi

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;

16 months ago

Rishabh Verma 170

Solution 3 : minimum cost path

Overview : In this question we have to find 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 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 bfs(int node,vi &dis,vi &vis,int val){
    vis[node]= 1;
    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int nd = q.front();
        q.pop();
        vis[nd]= 1;
        for(pii cur:adj[nd]){
            int ch = cur.ff,w = cur.ss;
            if(w<=val and vis[ch]==0){
                dis[ch] = dis[node]+1;
                q.push(ch);
                vis[ch]= 1;
            }
        }
    }
    
}

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

20 months ago

hardik kapoor 130

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;
            }
        }
    }
}

12 months ago

Apna_time _aayega • 60

They have taken 1-based indexing in this Question remember this. I t is quite confusing and wasted a lot of time because in the sample test cases they are taking 0 based indexing. 
only change in your code adj[n]-> adj[n+1];