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.com/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?

Input: given n and m

Task : For given n and m we have to calculate (n+m-2)C(n-1) mod 1000000007 where c is binomial coefficient

Constraints : 1 <= T <= 10^3

1 ≤ m,n ≤ 10^6

My solution

Accepted solution

For the given test case(Which I is used in ideone)

1) Both are passing in ideone

2) My solution is failing on hackerrank(Segmentation fault) other one is passing on hackerrank

Can anyone tell me why my solution is not getting accepted on hackerrank ?

Problem link

Problem link : PK and interesting Language

I read the editorial but I didn't find the proof of correctness in editorial. Can anyone explain with the recurrence,how the below logic is working thanks in advance.

Editorial:

Complexity(per query): O(z^3 log(l)) where z is the number of alphabets and l is the length of word.

Explanation: Suppose we have a graph having each english alphabet as a vertex. There is an edge between the ith and jth english alphabet if the entry a[i][j]=1, where a is the input matrix. Now each word in the language is simply a path from the starting alphabet to the ending alphabet. To calculate the numbers of words of length l ending at particular alphabet,we need to calculate total paths of length l-1 ending at that alphabet. This can be found by raising the adjancy matrix to the power l-1. The jth number in the ith row of this matrix gives the number of words of length l starting at character i and ending at character j. To find the total number of words ending at a particular alphabet take the sum of all the numbers in the jth column.

input:

10 1 2

1

100

debug val 1 and debug val 2 are printing are same but req which is equal to (debug val 1 — debug val 2) is not getting zero ?

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int l,s1,s2;
    cin>>l>>s1>>s2;
    int q;
    cin>>q;
    long long int relspe = abs(s2-s1);
    while(q--){
        long long int a;
        cin>>a;
        cout<<"debug val 1  "<<sqrt(2)*l<<endl;
        cout<<"debug val 2 "<<sqrt(2)*sqrt(a)<<endl;
        double req = abs(sqrt(2)*l-sqrt(2)*sqrt(a));
        cout<<"req "<<req<<endl;
        double ans = req/relspe;

        cout<<ans<<endl;
    }
}

https://www.hackerrank.com/challenges/sherlock-and-moving-tiles/problem

This is authors solution 55959992

This is my solution 55959887

I am getting TLE although i have used the same approach

https://codeforces.com/contest/675/problem/D

I tried many test cases ,I am passing all of them But it is failing at test case 5 on codeforces. Since test case are quite large ,I am unable to figure out my error.Please forgive me if my question is not good. 55748387(My submission)

https://codeforces.com/contest/52/problem/C