Hi everyone I was reading article on mos algo from Mos algo. Let's say we have 1e5 and the queries are like (b1,bn) (b2,b3) (b4,bn) (b5,b6) (b7,bn). If we sort the queries according to Mos algorithm where bi represents the block number it seems that the left pointer will always be increasing However the right pointer is jumping between blocks (eg bn to b3, b3 to bn and bn to b6) Wouldnt the right pointer need O(n) time because if we want to go from bi to bn then we have traverse all the elements in all the blocks present between bi to bn Please help what i am getting wrong here ?

the developres at amazon are developing a regex matching libraary for their nlp use cases. a prototype regex matching has the following requirments:

the regex expression contains lowecase english letters, '(', ')' , '.' and '*'.

'.' matches with exactly one lower case english letter

a regular expression followed by '*' matches with zero or more occurences of the regular expression

if an expression is enclosed in parentheses '(' and ')' it is treated as one expression and any asterisk '*' applies to the whole expression

for example regex " (ab)*d "matches with string "d" , "ababd", "abd", but not with "abbd"

given an array arr of length kcontaining strings consisting of lower case english letters only and a string regex of length n , for each of them find whether the given regex matches the string or not and report an array of strings "YES" or "NO" RESPECTIVELY

This question is quite frequently appearing in recent amazon oa observed from leetcode discuss sections. There is similar question on leetcode wildcard matchig but in this we have quotes also () which makes it more tougher any help would be much appreciated on it Thanks.

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

int dfs(int u, int mask, vector<vector<int>>& gp, int n, int m, int dp[][1 << 11], vector<int>ps = {}){
    //ps.push_back(u);
	if(mask == all){
        for(auto pp: ps){
            cout<<pp<<" ";
        }
        cout<<endl;
        return 1;
	}
	int res = 0;
	// if(dp[u][mask] != -1)return dp[u][mask];
	for(int v: gp[u]){
		if((mask >> v) & 1)continue;
		ps.push_back(v);
		res += dfs(v, mask | (1 << v), gp, n, m, dp, ps);
		ps.pop_back();
	}
	return dp[u][mask] = res;
}
int main(){
	int t;
	t = 1;
	while(t--){
		int n;
		cin>>n;
		int m;
		cin>>m;
		all = (1 << n) - 1;
		int dp[11][1 << 11];
		memset(dp, -1, sizeof(dp));
		vector<vector<int>>gp(n + 1);
		for(int i = 1; i <= m; i++){
			int u, v;
			cin>>u>>v;
			u--, v--;
			gp[u].push_back(v);
			gp[v].push_back(u);
		}

		int res = 0;
		for(int i = 0; i < n; i++){
			//memset(dp, -1, sizeof(dp));
			res += dfs(i, 1 << i, gp, n, m, dp, {i});
		}
		cout<<res<<endl;
	}
}

For the Test case

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

Output is 8 after debugging we can see some of them are counted 2 times.

0 6 5 2 1 4 3 0 6 5 2 1 4 3 1 2 5 6 0 4 3 1 2 5 6 0 4 3 3 4 0 6 5 2 1 3 4 0 6 5 2 1 3 4 1 2 5 6 0 3 4 1 2 5 6 0 8

Correct answer is 4. Please help in how can i fix this code ?

Problem link

Problem statement A series of highways connect n cities numbered from 0 to n — 1. You are given a 2D integer array highways where highways[i] = [city1i, city2i, tolli] indicates that there is a highway that connects city1i and city2i, allowing a car to go from city1i to city2i and vice versa for a cost of tolli. You are also given an integer discounts which represents the number of discounts you have. You can use a discount to travel across the ith highway for a cost of tolli / 2 (integer division). Each discount may only be used once, and you can only use at most one discount per highway. Return the minimum total cost to go from city 0 to city n — 1, or -1 if it is not possible to go from city 0 to city n — 1.

Example 1: Input: n = 5, highways = [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]], discounts = 1 Output: 9 Explanation: Go from 0 to 1 for a cost of 4. Go from 1 to 4 and use a discount for a cost of 11 / 2 = 5. The minimum cost to go from 0 to 4 is 4 + 5 = 9.

Time complexity As per my understanding Time complexity for this would be k * E log (V * k). Since Each edge can be reached with k different number of discount values and with decreased toll value everytime (k * E) and also this means each vertex may be present in heap k number of times (log(V * k)). Here K is the number of discounts. Is it correct ?

You are given an array arr of size n and an integer k. Score of an array is defined as number of its non-empty subarrays with sum = k. Your task is to find sum of scores of all the subsequences of arr. Since the answer can be very large print its modulo 1e9+7.

Input format :

First line contains T , the number of testcases. Each testcase has two lines. First line contains two integers n and k. Second line contains n integers describing arr.

Output Format :

For each testcase, print a single integer denoting sum of scores of all the subsequences of arr modulo 1e9+7

Constraints :

1<=T<=1000 1<=n<=1000 1<=k<=1000 1<=arr[i]<=1e5 Sum of n over all the testcases will not exceed 1000 Sum of k over all the testcases will not exceed 1000.

First Test Case

2

10 1

5 1 4 5 4 5 3 3 2 2

10 2

2 2 5 1 2 3 2 1 2 4

Output:

512

2592

Dry run:

For 1st tc, for subarray [1] there are 9-left out elements, possibility of taking-not-taking = 2^9 = 512 no other subarray possible, hence ans = 512

For 2nd tc, for subarray [2], there are 5 such subarrays, possibility of other 9 elements = 2 ^ 9 = 512 (for each) there are 5 such, hence ans for subarray [2] = 5 x 512 = 2560 now there is one more possible subarray [1,1], to make this as a subarray we need to exclude all the elements in between, hence new array = [2,2,5,1,1,2,4], now keeping [1,1] aside, we are left with 5 other element, possibility = 2 ^ 5 = 32 no other subarray possible

hence ans = 2560 + 32 = 2592

Description

The cows have reconstructed Farmer John's farm, with its N barns (1 <= N <= 150, number 1..N) after the terrible earthquake last May. The cows didn't have time to rebuild any extra roads, so now there is exactly one way to get from any given barn to any other barn. Thus, the farm transportation system can be represented as a tree.

Farmer John wants to know how much damage another earthquake could do. He wants to know the minimum number of roads whose destruction would isolate a subtree of exactly P (1 <= P <= N) barns from the rest of the barns.

Problem link — http://poj.org/problem?id=1947

I am trying to understand the recurrence from below accepted solution but not able to understand few things. As per my understanding dp[i][j] = number of edges needs to be deleted for tree rooted at i having j nodes in that tree.

Doubt 1 Is it included root or only considers child

dp [ cur ][ j ] = min ( dp [ cur ][ j ] , dp [ v ] [ k ] + dp [ cur ][ j — k ] — 2 ); } dp[cur][j] when not considering child v dp [ v ] [ k ] + dp [ cur ][ j — k ] — 2 ) when considering child v and taking k nodes from it and j — k from the previous child nodes.

Doubt 2 why we are subtracting 2 when we include this child v rooted at v.

Accepted solution found from one blog(which does not have explanation to recurrence).

#include<stdio.h>
    #include<vector>
    #include<iostream>
    #define ll long long 
    #define pb push_back 
    #define pm make_pair 
    using  namespace  std ; 
    const  int  MAX  =  555 ; 
    const  int  INF  =  0x3f3f3f3f ; 
    int  dp [ MAX ][ MAX ] ; 
    // The minimum knife number 
    int  n  ,p;
    vector < int >  vv [ MAX ]; 
    void  dfs ( int  cur , int  rt ) { 
    int  up  =  vv [ cur ]. size (); 
    for ( int  i  =  0 ; i < up ; i ++ ) { 
        int  v  =  vv [ cur ][ i ]; 
        if ( v  ==  rt )continue ; 
        dfs ( v , cur ); 
        for ( int  j  =  p ; j > 1 ; j -- ) { 
        for ( int  k  =  1 ; k  <  j ; ++ k ) // divide into nodes under the subtree and itself 
        dp [ cur ][ j ] = min ( 
            dp [ cur ][ j ] , dp [ v ] [ k ] + dp [ cur ][ j - k ] - 2 ); 
        } 
    } 
    } 
    int  main () 
    { 
    cin >> n >> p ; 
    for ( int  a , b , i  =  1 ; i <= n - 1 ; i ++ ) { 
        cin>>a>>b;
        vv[ a ] .pb ( b ); 
        vv[ b ] .pb ( a ); 
    } 
    memset ( dp , INF , sizeof  dp ); 
    for ( int  i  =  1 ; i <= n ; i ++ ) dp [ i ] [ 1 ] =  vv [ i ]. size (); 
    dfs ( 1 , - 1); 
    int  ans  =  INF ; 
    for ( int  i = 1 ; i <= n ; i ++ ) ans = min ( dp [ i ][ p ], ans ); 
    cout  << ans  << endl ; 
    return  0 ; 
    }

Given a word length n and max number of consecutive vowels k ,we need to tell how many words that we can form using given constraints.

n=3 and k=2 means we have to tell the number of words of length 3 and in which we can use at most k consecutive vowels.

I know its a dynamic programming problem but unable to figure out the recurrence.Please help!

word can contain letters only 21 consonants and 5 vowels

I m learning binary search and here i need to find the nth root of a number ,i am not able to figure out the error in the below program please help. I am getting answer wrong when x is between 0 and 1 ,I don't know why binary search is not working for in that case can someone explain? eg test case 0.09 3,whhy bs is not able to converge for l=0 and x=0.09?

#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
using namespace std;

double solve(double x, int n){
    int iter=200;
    double low=0;
    double high=x;
    while(iter--){
        double mid = (low+high)/2;
        //cout<<mid<<endl;
        double val = pow(mid,n);
        cout<<val<<endl;
        if(val<x)low=mid;
        else high=mid;
    }
    return low;
}

int main() {
    // int t--;
  int t;
  cin>>t;
  while(t--){
    double x;
    cin>>x;
    int n;
    cin>>n;

    cout<<fixed<<setprecision(12)<<solve(x,n)<<endl;
  }
  return 0;
}

Div 3 dp problem polycarp

I need help in understanding the recurrence in below solution especially the significance of this taken variable in the recurrence whose value can be zero or one.

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
 
const int N=2e5+5;
 
int n;
string s;
int cache[N][3][2];
 
int dp(int i, int rem, int taken)
{
	if(i==n)
		return (rem==0 && taken==1);
	int &ans=cache[i][rem][taken];
	if(ans!=-1)
		return ans;
	if(!taken)
	{
		if(s[i]!='0')
			ans=max(dp(i+1, (s[i]-'0')%3, 1), (((s[i]-'0')%3)==0) + dp(i+1, 0, 0));
		else
			ans=1+dp(i+1, 0, 0);
	}
	else
	{
		ans=max((((rem+s[i]-'0')%3)==0) + dp(i+1, 0, 0), dp(i+1, (rem+s[i]-'0')%3, 1));
	}
	return ans;
}
 
int32_t main()
{
	IOS;
	memset(cache, -1, sizeof(cache));
	cin>>s;
	n=s.size();
	int ans=dp(0, 0, 0);
	cout<<ans;
	return 0;
}

I was solving the probablity problem ? In which i faced this calculation.

Please forgive me if my ques is not good ? I am still a beginner.I know that pasting code here is not considered good . But I am not able to understand some part in solution after trying it whole day Please help me . I am going to copy whole post here and i will refer in that. where the above calculation is being calculated.So that your time is not wasted. In the perm function you can see that ans is taking as double but we can see that (a!+b!)/a!*b! involves integer calculation (although i have tried unsigned long long but it overflowed)it means we have already lost some data by taking double . moreover we are calculating perm(a)*perm(b) in dfs function which also gives number of ways which also involves integers but again we are multiplying two double values which already gone through precision loss.

Problem Link on leetcode

Problem Link for those who don't have leetcode account

Original Post

First, compute the total number of distinct shuffles.

total = factorial(sum( A[i] | 0 <= i < k )) / (factorial(A[0]) * factorial(A[1]) * ... * factorial(A[k-1])) where factorial(x) is the number of permutations of x different items. For example, factorial(3) = 1 * 2 * 3 = 6.

I denote the right-hand side of the above equation as perm(A) where A is an array of numbers. We'll need it later.

Then we need to compute the count of valid splits. Assume array a and b is a split of A, then:

size(a) == size(b) == size(A) == k For each 0 <= i < k, a[i] + b[i] = A[i] For example, if A = [1, 2, 3], then a = [1, 0, 1], b = [0, 2, 2] is a split of A.

A split is valid if:

Each of them contains half of the balls: sum( a[i] | 0 <= i < k ) == sum( b[i] | 0 <= i < k ) == sum( A[i] | 0 <= i < k ) / 2 They contain equal number of distinct colors: count(a) == count(b) where count(x) is the number of positive numbers in array x. For example, if A = [1, 1, 2], then a = [1, 0, 1], b = [0, 1, 1] is a valid split of A.

So we can use DFS to get different valid splits of A. For each valid split a, b, the count of distinct permutation of the split is perm(a) * perm(b) .

The answer is the sum of perm(a) * perm(b) of all valid splits a, b divided by total.

// OJ: https://leetcode.com/contest/weekly-contest-191/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/
// Author: github.com/lzl124631x
// Time: O((M+1)^K * MK) where M is the maximum number of A[i]. It's O(7^8 * 6 * 8) given the constraints of this problem.
// Space: O(K)
class Solution {
    double perm(vector<int> &A) {
        double ans = 1;
        for (int i = 0, j = 1; i < A.size(); ++i) {
            for (int k = 1; k <= A[i]; ++k, ++j) ans = ans * j / k; 
        }
        return ans;
    }
    int sum = 0;
    double dfs(vector<int> &A, vector<int>& a, vector<int> &b, int i, int sa, int sb) {
        if (sa > sum / 2 || sb > sum / 2) return 0; // invalid split because either `a` or `b` takes up more than half of the balls.
        if (i == A.size()) {
            int ca = 0, cb = 0;
            for (int j = 0; j < A.size(); ++j) ca += a[j] > 0;
            for (int j = 0; j < A.size(); ++j) cb += b[j] > 0;
            if (ca != cb) return 0; // invalid split because `a` and `b` don't have the same number of distinct colors.
            return perm(a) * perm(b);
        }
        double ans = 0;
        for (int j = 0; j <= A[i]; ++j) { // try different splits at the `i`-th element, i.e. a[i] + b[i] = A[i]
            a[i] = j;
            b[i] = A[i] - j;
            ans += dfs(A, a, b, i + 1, sa + a[i], sb + b[i]);
        }
        return ans;
    }
public:
    double getProbability(vector<int>& A) {
        sum = accumulate(begin(A), end(A), 0);
        vector<int> a(A.size()), b(A.size());
        return dfs(A, a, b, 0, 0, 0) / perm(A);
    }
};

````````````

Lanterns Problem Please forgive me if my ques is not good i am not good at it I am getting precision error on it Test case was huge so i was not able to debug. Mentioned in Prob absolute or relative error doesn't exceed 10 - 9.

example wrong answer 1st numbers differ - expected: '22258199.5000000', found: '22258200.0000000', error = '0.0000000'

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<double>a;
double eps = 1e-9;
bool check(double s,double dist){
    if(a[0]-s>eps)return false;
    if(dist-a.back()-s>eps)return false;
    for(int i=1;i<((int)a.size());i++){
        if(abs(a[i]-a[i-1])-2*s>eps){
            return false;
        }
    }
    return true;
}
int32_t main(){
    int n,d;
    cin>>n>>d;
    a.resize(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
   // for(auto p : a)cout<<p<<endl;
    //exit(0);
    double low=0;
    double high=d;
    int iter=200;
    while(iter--){
        double mid=(low+high)/2;
        if(check(mid,d)){
            high=mid;
        }else low=mid;
    }
    cout<<low<<endl;

}

Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the locations where the cuts are to be made for maximum profit.

I need help how can we approach this problem ?

Sudoku solver

I have added comments in my solution ,I am getting wrong answer on leetcode

Is below condition correct to check if i can find solution for coming places.Since it is hard to debug of large number of recursive calls Please can anyone help me where I am doing wrong?

if(ok==false){ //if i didn't find a single position to put a number here
     board[i][j]='.'; //then some thing wrong has happened earlier 
     return false;
}

My solution class

    class Solution {
    public:
        bool isvalid(vector<vector<char>>board,int x,int y,char c){  //to check if there is no duplicates
                                                            //according to given condition
            for(int i=1;i<=9;i++){
                if(board[(x+i)%9][y]==c)return false;  //checking in row
                if(board[x][(y+i)%9]==c)return false;  //checking in col

            }
            for(int i=-1;i<=1;i++){
                for(int j=-1;j<=1;j++){      //checking in 3*3 square
                    if(i==0&&j==0)continue;
                    int row = x+i;
                    int col = y+j;
                    if(row>=0 && col<9 && col>=0 && row<9 && board[row][col]==c)return false;
                }
            }
            return true;
        }
        bool solve(vector<vector<char>>board){
            int n = board.size();
            int m = board[0].size();

            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(board[i][j]=='.'){
                        bool ok=false;   //to check  if at least one value can be place 
                        for(char c='0';c<='9';c++){  //at the current pos or not 

                            board[i][j]=c;
                            if(isvalid(board,i,j,c)){
                                ok=true;
                                if(solve(board))return true; //if valid see remaining  board can be solve or not
                            }
                        }
                        if(ok==false){ //if i didn't find a single position to put a number here
                            board[i][j]='.'; //then some thing wrong has happened earlier 
                            return false;
                        }

                    }
                }
            }
            return true;
        }
        void solveSudoku(vector<vector<char>>& board) {
            solve(board);
        }
    };

https://leetcode.com/problems/paint-house-ii/

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

I am unable to pass all the test cases

class Solution {
public:
    int minCostII(vector<vector<int>>& cost) {
        if(cost.size()==0)return 0;
        int n=cost.size();
        int k=cost[0].size();
        
        int dp[n][k];
        int min1=INT_MAX;
        int min2=INT_MAX;
        int minind=-1;
        for(int i=0;i<k;i++){
            dp[0][i]=cost[0][i];
            if(cost[0][i]<min1){
                min2=min1;
                minind=i;
                min1=cost[0][i];
            }else min2=min(min2,cost[0][i]);
            
            
        }
        cout<<min2;
        for(int i=1;i<n;i++){
            int curmin=INT_MAX;
            int curmin2=INT_MAX;
            int curind=0;
            for(int j=0;j<k;j++){
                if(minind!=j){
                    dp[i][j]=min1+cost[i][j];
                }else{
                    dp[i][j]=min2+cost[i][j];
                }
                if(curmin>dp[i][j]){
                    curmin2=curmin;
                    curmin=dp[i][j];
                    minind=j;
                    
                }else curmin2=min(curmin2,dp[i][j]);
                
            }
            min1=curmin;
            min2=curmin2;
            minind=curind;
        }
        
        return min1;
    }
};

Given an array a[].Find the two pairs (a,b) and (c,d) such that a+b==c+d.And the sum (a+b==c+d)value as maximum as possible we just have to print that sum value if it is forming the two pairs with same sum value else -1 Note->NO cpp only c language allowed which makes this problem more difficult for me

Example: N = 6, S[] = { 2, 3, 6, 4, 1, 5 } You can select pair of (6, 3) and (5, 4), two numbers can be same ,but same number can not be part of both pair.

My Thinking 1 -> I tried to make all possible pairs store the pairs sum in sorted array ,then i started searching form end to check if it is possible that we can find two teams with maxsum But unable to handle like case 0 0 1 1(which contain duplicates)

My Thinking 2 ->all ways to choose 1st, 2nd and 3rd student and check whether you have 4th one with skill equal to (S1+S2−S3)? And then choose maximum among all possible teams. But since n<=500 it will be O(n^4) can give TLE.

please help!

how can we solve this problem Select team The language allowed was only C thats make problem more hard I tried to make all possible pairs store the pairs sum in sorted array ,then i started searching form end to check if it is possible that we can find two teams with maxsum But unable to handle like case 0 0 1 1

can anyone tell me how to approach this problem efficiently considering c language?

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

  -10
   / \
  9  20
    /  \
   15   7

ans = 42

I am beginner please help me.

Below maxpathsum function must return int value i am using long long just to avoid to integer overflow

input : [1,2] (1 is parent of two) expected output : 3

actual output : every time garbage value on leetcode but sometimes gives correct output as 3 also I know its data type error i want your help because when i try to run it on visual studio or codeblocks ,i am getting correct output as 3. whats wrong in below code.

long long int solve(TreeNode* root,long long int &res) {
	if (root == NULL)return INT_MIN;
	long long int left = solve(root->left, res);
	long long int right = solve(root->right, res);
	//cout << left + right;
	long long int temp = max(left, max(right, left + right)) + root->val;
	res = max(1LL*res, temp);
	res = max(1LL*res,1LL* root->val);
	return max(left + 1LL * root->val, max(right + 1LL * root->val, 1LL * root->val));
}
//below function must return int value 
// i am using long long just to avoid to integer overflow
int maxPathSum(TreeNode* root) {
	long long int res;
    if(root==NULL)return 0;
    if(root->left==NULL && root->right==NULL)return root->val;
	solve(root, res);
	int ans = (int)res;
    return ans;
}

Given a collection of numbers that might contain duplicates, return all possible unique permutations. Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] I am failing on a large test cases can anyone help me where i am doing wrong? please:)

class Solution {
public:
    void solve(vector<vector<int>>&res,int j,vector<int>&nums){
        if(j==nums.size()){
            res.push_back(nums);
            return;
        }
        for(int i=j;i<nums.size();i++){
            if(i==j||nums[i]!=nums[j]){
            swap(nums[i],nums[j]);
            solve(res,j+1,nums);
            swap(nums[i],nums[j]);}
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>>res;
        sort(nums.begin(),nums.end());
        solve(res,0,nums);
        return res;
    }
};

There are a row of n houses, each house can be painted with one of the m colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color, and you need to cost the least. Return the minimum cost. Generally this problem is asked for 3 colors but I am doing it for m colors. I have commented my solution.

    int minCost(vector<vector<int>> &costs) {
        
        if(costs.size()==0)return 0;
        int n = costs.size();
        int m = costs[0].size();
        int dp[n][m];
       	for (int i = 0; i < n; i++) {
	    	for (int j = 0; j < m; j++) {
		     	dp[i][j] = INT_MAX;
		    }
     	}
        for(int i=0;i<n;i++){
            dp[0][i]=costs[0][i];
        }
        //dp[i][j] represents min cost to paint ith house with jth colour
        for(int i=1;i<n;i++){
            for(int j=0;j<m;j++){
                   //searching min cost in previous row
                for(int k=0;k<m;k++){
                    if(j!=k){  //no two adjacent house can have same color
                    dp[i][j]=min(dp[i][j],dp[i-1][k]);
                    }
                }
                dp[i][j]+=costs[i][j];
            }
        }
        int ans=INT_MAX;
        //picking minimum from last row
        for(int i=0;i<m;i++){
            ans=min(ans,dp[n-1][i]);
        }
        return ans;
        
    }

I am failing on some of test cases.Test cases seems to be large,I am unable to find where i am doing wrong.

I stuck at a problem ,It was a basically implementation problem ,It passed all the test cases But I have doubt regarding its time complexity.

for (int i = 0; i < 1e6 + 100; i++) {
    sort(v[i].begin(), v[i].end());
}

The time complexity of this loop seems to be O(n*n*logn) .Then It should definitely fail because n value can be 10^6.Even O(n*n) fail for such higher value of n,I have seen already so many times on codeforces.

What is its correct time complexity??

Problem link

Please forgive me if it is too basic!

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1e6 + 100;
vector<int> a, f(1e6 + 100);
vector<int>v[N];
int main() {
    int n;
    cin >> n;
    a.resize(n);
    int mx = -1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        f[a[i]]++;
        v[a[i]].push_back(i);
        mx = max(mx, f[a[i]]);
    }
    for (int i = 0; i < 1e6 + 100; i++) {
        sort(v[i].begin(), v[i].end());
    }
    int diff = INT_MAX;
    int ans[2];
    for (int i = 0; i < 1e6 + 100; i++) {
        if (f[i] == mx) {
            int temp = v[i][v[i].size() - 1] - v[i][0];
            if (diff > temp) {
                diff = temp;
                ans[0] = v[i][0];
                ans[1] = v[i][v[i].size() - 1];
            }
        }
    }
    cout << ans[0] + 1 << " " << ans[1] + 1;

}

Can anyone help me with what test case I am missing ,It is failing at test case 12,which is very large.Please help. Link to submission: http://codeforces.net/contest/551/submission/59558421

#include<bits/stdc++.h>
using namespace std;
vector<int> cnts(26),cnta(26),cntb(26);

int main(){
    string s,a,b;
    cin>>s>>a>>b;

    for(int i=0;i<a.size();i++){
        cnta[a[i]-'a']++;
    }
    for(int j=0;j<b.size();j++){
        cntb[b[j]-'a']++;
    }
    for(int i=0;i<s.size();i++){
        cnts[s[i]-'a']++;
    }
    int mn=INT_MAX;
    for(int i=0;i<26;i++){
        if(cnta[i]>0){
            mn=min(mn,cnts[i]/cnta[i]);
        }
    }
    for(int i=0;i<26;i++){
        cnts[i]=cnts[i]-mn*cnta[i];
    }
    int mn1=INT_MAX;
    for(int i=0;i<26;i++){
        if(cntb[i]>0){
            mn1=min(mn1,cnts[i]/cntb[i]);
        }
    }
    for(int i=0;i<26;i++){
        cnts[i]=cnts[i]-mn1*cntb[i];
    }
    string ans;
    while(mn--){
        ans+=a;
    }
    while(mn1--){
        ans+=b;
    }
    for(int i=0;i<26;i++){
        if(cnts[i]){
            while(cnts[i]--){
                ans+='a'+i;
            }
        }
    }
    cout<<ans<<endl;
}

I was trying to solve a problem problem link

This problem is also on hackerrank

I am failing in some test cases I used the approach given in above link

MY solution

Method (efficient approach): The idea is to compute prefix sum of array. We find maximum sum ending with every index and finally return overall maximum. To find maximum sum ending at index at index, we need to find the starting point of maximum sum ending with i. Below steps explain how to find the starting point.

Let prefix sum for index i be prefixi, i.e., prefixi = (arr[0] + arr[1] + .... arr[i] ) % m

Let maximum sum ending with i be, maxSumi. Let this sum begins with index j.

maxSumi = (prefixi — prefixj + m) % m

From above expression it is clear that the value of maxSumi becomes maximum when prefixj is greater than prefixi and closest to prefix[i We mainly have two operations in above algorithm.

1)Store all prefixes. 2)For current prefix, prefix[i], find the smallest value greater than or equal to prefix[i] + 1. For above operations, a self-balancing-binary-search-trees like AVL Tree, Red-Black Tree, etc are best suited. In below implementation we use set in STL which implements a self-balancing-binary-search-tree.

#include <bits/stdc++.h>

using namespace std;


// Complete the maximumSum function below.
long maximumSum(vector<long> &a, long m) {
    set<long> seen;
    //prefix[0]=a[0]%m;
    long sum = a[0]%m;
    long ans=0;
    long maxx = 0;
    for(long i=1;i<a.size();i++){
        sum = (sum%m + a[i]%m)%m;
        maxx = max(sum,maxx); 
        auto it  =  seen.lower_bound(sum+1);
        if(it!=seen.end()){
            ans = max(ans,(sum-(*it)+m));
        }
        seen.insert(sum);
    }
    return max(ans,maxx);

}

int main(){
    long n,k;
    long q;
    cin>>q;
    while(q--){
    cin>>n>>k;
    vector<long> a;
    for(long i=0;i<n;i++){
        long u;
        cin>>u;
        a.push_back(u);
    }
    cout<<maximumSum(a,k)<<endl;
    }
}

Please help : I have two job interview first one is tomorrow next one is a week later In last 18 hours i solved 25 interview problems from diferent In seven days My target is 300 ,please save my life :)

I am trying to find diameter using recursion ,I am confused with recursion

some of the test cases I tried I got correct answer at some point Integer overflow occured But Below author's solution was accepted with same data types

My approach:

For every node, length of longest path which pass it = MaxDepth of its left subtree + MaxDepth of its right subtree.

My question is whats wrong with my implementation

  class Solution {
  public:
      int mx = 0;
      int solve(TreeNode* root) {
          if (root == NULL)return 0;
          int leftheight = solve(root->left) + 1;
          int rightheight = solve(root->right) + 1;
          mx = max(mx, leftheight + rightheight);
          return max(leftheight, rightheight);
      }
      int diameterOfBinaryTree(TreeNode* root) {
          solve(root);
          return mx;
      }

  };

Authors approach: same approach but different recursion implementation

  class Solution {
  public:
      int maxdiadepth = 0;

      int dfs(TreeNode* root) {
          if (root == NULL) return 0;

          int leftdepth = dfs(root->left);
          int rightdepth = dfs(root->right);

          if (leftdepth + rightdepth > maxdiadepth) maxdiadepth = leftdepth + rightdepth;
          return max(leftdepth + 1, rightdepth + 1);
      }

      int diameterOfBinaryTree(TreeNode* root) {
          dfs(root);

          return maxdiadepth;
      }
  };

Problem link

problem link:Leetcode

problem:Given a binary tree, return the vertical order traversal of its nodes values.

This approah is using unorederd_map and i think it is nlog(n) due to n for loop and log(n) for find operation in it.Is it correct?

Traverse the tree tracking x and y coordinates, and populate m[x][y] with values. Note that we use set to hold multiple values and sorts them automatically.

Then, we iterate x [-999, 999] and y [0, 999] and populate our answer. Since the tree size is limited to 1000, our coordinates will be within these intervals.

unordered_map<int, unordered_map<int, set<int>>> m;
void traverse(TreeNode* r, int x, int y) {
  if (r != nullptr) {
    m[x][y].insert(r->val);
    traverse(r->left, x - 1, y + 1);
    traverse(r->right, x + 1, y + 1);
  }
}
vector<vector<int>> verticalTraversal(TreeNode* r) {
  vector<vector<int>> res;
  traverse(r, 0, 0);
  for (int x = -999; x < 1000; ++x) {
    auto it = m.find(x);
    if (it != end(m)) {
      res.push_back(vector<int>());
      for (int y = 0; y < 1000; ++y) {
        auto ity = it->second.find(y);
        if (ity != end(it->second)) {
          res.back().insert(end(res.back()), begin(ity->second), end(ity->second));
        }
      }
    }
  }
  return res;
}

This approach is using map ,I don't know time complexity of this one

We could also use map[x, map[y, set[val]]], and it will simplify the code a bit:

void dfs(TreeNode* r, int x, int y, map<int, map<int, set<int>>> &m) {
  if (r != nullptr) {
    m[x][y].insert(r->val);
    dfs(r->left, x - 1, y + 1, m);
    dfs(r->right, x + 1, y + 1, m);
  }
}
vector<vector<int>> verticalTraversal(TreeNode* r, vector<vector<int>> res = {}) {
  map<int, map<int, set<int>>> m;
  dfs(r, 0, 0, m);
  for (auto itx = m.begin(); itx != m.end(); ++itx) {
      res.push_back(vector<int>());
      for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {
          res.back().insert(end(res.back()), begin(ity->second), end(ity->second));
      }
  }
  return res;
}

we have to find min cost path in a mtrix from top left to bottom right.

Move allowed -> Right,left,Bottom,Up.

I know suitable approach will be using Dijkstra But can we do this using Dp because here we can move in all 4 direction ,If yes then How?