acash's blog

By acash, history, 12 days ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

By acash, history, 6 weeks ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -12
  • Vote: I do not like it

By acash, history, 2 months ago, In English,

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;

}

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By acash, history, 3 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By acash, history, 4 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By acash, history, 4 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By acash, history, 4 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By acash, history, 5 months ago, In English,

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?

Read more »

Tags dp
 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

By acash, history, 5 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By acash, history, 5 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By acash, history, 5 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

By acash, history, 5 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By acash, history, 5 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By acash, history, 10 months ago, In English,

47841668 My solution to to codeforces 455A giving wrong answer on test case 12 ,can anyone tell me where i did the mistake?

Read more »

 
 
 
 
  • Vote: I like it
  • -12
  • Vote: I do not like it