### acash's blog

By acash, history, 9 days ago, , 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 is the cost of painting house 0 with color 0; costs 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.size();

int dp[n][k];
int min1=INT_MAX;
int min2=INT_MAX;
int minind=-1;
for(int i=0;i<k;i++){
dp[i]=cost[i];
if(cost[i]<min1){
min2=min1;
minind=i;
min1=cost[i];
}else min2=min(min2,cost[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;
}
};


By acash, history, 3 weeks ago, , 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.

By acash, history, 3 weeks ago, , 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?

By acash, history, 2 months ago, , 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

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;
} cpp,
By acash, history, 3 months ago, , 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;
}
}; By acash, history, 4 months ago, , 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.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[i]=costs[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.

By acash, history, 5 months ago, , 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??

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;
for (int i = 0; i < 1e6 + 100; i++) {
if (f[i] == mx) {
int temp = v[i][v[i].size() - 1] - v[i];
if (diff > temp) {
diff = temp;
ans = v[i];
ans = v[i][v[i].size() - 1];
}
}
}
cout << ans + 1 << " " << ans + 1;

} By acash, history, 5 months ago, , 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;
} By acash, history, 7 months ago, , 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 + arr + .... 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=a%m;
long sum = a%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;
}
} By acash, history, 7 months ago, , 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 dfs(TreeNode* root) {
if (root == NULL) return 0;

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

return max(leftdepth + 1, rightdepth + 1);
}

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

}
}; By acash, history, 7 months ago, , 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;
} By acash, history, 7 months ago, , 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? By acash, history, 7 months ago, , 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 ? By acash, history, 7 months ago, , 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. By acash, history, 7 months ago, , 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 By acash, history, 7 months ago, , 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 By acash, history, 7 months ago, , 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 By acash, history, 13 months ago, ,  