Hello All.

I am a Software Engineer, due to join a FAANGM company this week. A little bit about myself, I am not well versed with competitive programming. My aim is to better myself in algorithmic thinking and problem solving. I find a certain beauty in thinking and solving a difficult problem elegantly. I have finished college about a year ago, and I didn't participate in contests much in college. I don't have much CP experience. I recently participated in the Codechef long challenge in April, and could solve only 3 problems.

Here is my leetcode handle

My codeforces handle

My Spoj handle

I can spend around 2 hours a day right now. How do I about improving my rating and becoming 5 star on Codechef within a year or two ? How can I improve in competitive programming ? More importantly, how can I optimise my training process to achieve better results ? I request you to kindly view my handles, and advise me accordingly. Any suggestions, including books, courses, tutorials, or general advice from the coding community is welcome. Thanks

I have applied the following logic for the problem https://codeforces.com/contest/799/problem/A

#include<iostream>
using namespace std;
int main(){
	double N, T, K, D;
	cin>>N>>T>>K>>D;
	double x=(D*K)/T;
	double a=D+((N-x)*T)/(2*K);
	double b=(N*T)/K;
	if(a<b)
	cout<<"YES";
	else
	cout<<"NO";
	cout<<endl;
}

I saw a solution here which used int instead of double and some modulo arithmetic. My solution is producing wrong answer in some cases. But the underlying logic seems to be the same. How to approach this problem then ?

Please help.

Thanks.

I have been attempting this problem on codechef.

LINK TO PROBLEM STATEMENT

My approach:

Sort the numbers in descending numbers.

Segregate the numbers into buckets based on Most Significant Bits.

Process the buckets in decreasing order.

Once all the elements of a bucket have been divided by 2, merge them into the previous bucket and move backwards to the previous bucket.

However this gives wrong answer. What is wrong with this approach ?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> merge(vector<ll>a,vector<ll>b){
    int i=0;
    int j=0;
    vector<ll>ans;
    while(i<a.size() && j<b.size()){
        if(a[i] > b[j])
        {
            if(a[i]>0)   
            ans.push_back(a[i]);
            i++;
        }
        else{
            if(b[j]>0)
            ans.push_back(b[j]);
            j++;
        }
    }
    while(i<a.size()){
        if(a[i]>0)
        ans.push_back(a[i]);
            i++;
    }
    while(j<b.size()){
        if(b[j]>0)    
        ans.push_back(b[j]);
            j++;
    }
    return ans;
}

int main() {
	// your code goes here
	int N,M;
	cin>>N>>M;
	vector<ll>arr(N);
	for(int i=0;i<N;i++)
	    cin>>arr[i];
	vector<ll>steps(M);
	for(int i=0;i<M;i++){
	    cin>>steps[i];
	}
	vector<vector<ll>>buckets(64);
	for(int i=0;i<64;i++){
	    vector<ll>tmp;
	    buckets[i]=tmp;
	}
	sort(arr.begin(),arr.end(),std::greater<ll>());
	for(int i=0;i<N;i++){
	    int pos=0;
	    int num=arr[i];
	    while(num > 0){
	        num=num >> 1;
	        pos++;
	    }
	    buckets[pos].push_back(arr[i]);
	}
	
	int cur=0;
	int count=0;
	
	for(int i=63;i>=0;i--){
	    for(int j=0;j<buckets[i].size();j++){
	        count++;
	        if(cur<steps.size() && count==steps[cur]){
	            cur++;
	            cout<<buckets[i][j]<<endl;
	        }
	        buckets[i][j]=buckets[i][j] >> 1;
	    }
	    if(i>=1)
	    {
	        buckets[i-1]=merge(buckets[i],buckets[i-1]);
	    }
	}
	return 0;
}

I have been trying to solve a LeetCode Problem and I have written a solution for it. I have applied Kadane's algorithm for this problem. But it passes only 21/27 test cases. Could someone please tell how to approach this problem ? I am unable to figure out the approach in the solutions posted online.

This is my code.

int kadane(vector<int>arr, int k){
        int max_sum_so_far=arr[0];
        int max_sum=arr[0];
        for(int i=1;i<arr.size();i++)
        {
            max_sum=max(arr[i],arr[i]+max_sum);
            if((max_sum <=k) && (max_sum >= max_sum_so_far))
                max_sum_so_far=max_sum;
        }
        return max_sum_so_far;
    }
    
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        
        int rows=matrix.size();
        int cols=matrix[0].size();
        int maxsum=numeric_limits<int>::min();
        
        for(int i=0;i<cols;i++){
            int left=i;
            int right=cols;
            vector<int>arr(rows,0);
            while(left < right){
                for(int x=0;x<rows;x++)
                    arr[x]+=matrix[x][left];
                int sum=kadane(arr,k);
                if(sum > maxsum)
                    maxsum=sum;
                left++;
            }
        }
        
        return maxsum;
       
    }

Hello guys. I have been trying out dynamic programming problems and found this one quite difficult to wrap my head around. Could someone please explain the intuition behind this dynamic programming problem ?

https://www.geeksforgeeks.org/shortest-uncommon-subsequence/

I have been trying out this problem on Hackerearth.

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/practice-problems/algorithm/help-ashu-1/

This is my code:

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


int evencount[400004];
bool A[100001];
int num;
void build(int node,int start,int end)
{
    if(start==end)
    {
        evencount[node]=(A[start]%2==0);
        return;
    }
    int mid=start+(end-start)/2;
    build(2*node+1,start,mid);
    build(2*node+2,mid+1,end);
    int left=2*node+1;
    int right=2*node+2;
    evencount[node]=evencount[left]+evencount[right];
}

void update(int node,int start,int end,int idx,int val)
{
    if(start==end)
    {
        A[idx]=val%2;
        evencount[node]=(val%2==0);
        return;
    }
    int mid=start+(end-start)/2;
    if(idx <= mid)
    {
        update(2*node+1,start,mid,idx,val);
    }
    else{
        update(2*node+2,mid+1,end,idx,val);
    }
    int left=2*node+1;
    int right=2*node+2;
    evencount[node]=evencount[left]+evencount[right];
}

int query(int node,int start,int end,int left,int right)
{
    if(end < left || start > right)
    {
        return 0;
    }
    if(left<=start && end>=right)
    return evencount[node];

    int mid=start+(end-start)/2;
    int p1,p2;
    p1=query(2*node+1,start,mid,left,right);
    p2=query(2*node+2,mid+1,end,left,right);
    return p1+p2;
}


int main(){
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>num;
        A[i]=num%2;
    }
    int Q;
    cin>>Q;
    for(int i=0;i<Q;i++)
    {
        int q,a,b;
        cin>>q>>a>>b;
        if(q==0)
            update(0,0,N,a-1,b);
        else
        {
            int t=query(0,0,N,a-1,b-1);
            if(q==1)
            cout<<t<<endl;
            else
            cout<<(b-a+1)-t<<endl;
        }
    }
}

I have optimized it as much as I can. It is still giving memory limit exceeded. Where and how can I optimize this code further in terms of memory ?

I am trying out this problem on Hackerearth, I am getting Memory Limit Exceeded. I am using Segment Trees and I don't know where to optimize.

https://www.hackerearth.com/challenges/hiring/Samsung-R-D-Institute-Hiring-Challenge/algorithm/fibonacci-with-gcd-16/description/

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

void build(vector<int>&tree,vector<int>A,ll node, ll start, ll end){
	if(start==end){
		tree[node]=A[start];
        return;
	}
	ll mid=start+(end-start)/2;
	build(tree,A,2*node,start,mid);
	build(tree,A,2*node+1,mid+1,end);
	tree[node]=__gcd(tree[2*node],tree[2*node+1]);
}


ll query(vector<int>tree,ll node, ll start, ll end, ll left, ll right){
	if(start >right|| end <left )
		return 1;
	
	if(start>=left && right<=end){
		// this node is completely within the range
		// return it as a partial answer
		return tree[node];
	}
	ll mid=start+(end-start)/2;
	int leftAnswer=query(tree,2*node,start,mid,left,right);
	int rightAnswer=query(tree,2*node+1,mid+1,end,left,right);
	return __gcd(leftAnswer,rightAnswer);
}

int main(){
	ll N,Q;
	cin>>N>>Q;
    vector<int>tree(2*N+1);
	vector<int>A(N+1);
	for(ll i=1;i<=N;i++) {
		cin>>A[i];
	}

	build(tree,A,1,1,N);

	for(ll i=0;i<Q;i++){
		ll left,right;
		cin>>left>>right;
		ll index=query(tree,1,1,N,left,right);
		cout<<index<<endl;
	}

}

Hello all. I am trying out this problem on CodeChef.

Codechef Problem

I am using Disjoint Set along with path compression and union by rank. Still I am getting TLE. Please suggest the changes I should incorporate. Here is my code.

#include <iostream>
using namespace std;
typedef long long ll;

struct DisjointSet 
{
    ll *rank, *parent;
    DisjointSet(ll N){
        rank=new ll[N+1];
        parent=new ll[N+1];
        for(ll i=0;i<=N;i++)
        {
            rank[i]=1;
            parent[i]=i;
        }
    }
    
    ll find(ll x){
       if(parent[x]!=x){
           parent[x]=find(parent[x]);
       }
        return parent[x];
    }
    
    void union_rank(ll a,ll b){
        ll pa=find(a);
        ll pb=find(b);
        if(pa==pb)
        return;
        if(rank[pa] > rank[pb])
        {
            parent[pb]=pa;
            rank[pa]+=rank[pb];
        }
        else {
            parent[pa]=pb;
            rank[pb]+=rank[pa];
        }
    }
    
};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll tc;
    cin>>tc;
    while(tc--)
    {
        ll N,M;
        cin>>N>>M;
        DisjointSet d(N);
        for(int i=0;i<M;i++)
        {
            ll q,x,y;
            cin>>q>>x>>y;
            if(q==1){
                d.union_rank(x,y);
            }
            else
            {
                if(d.find(x)==d.find(y)){
                    cout<<"YES"<<endl;
                }
                else
                {
                    cout<<"NO"<<endl;
                }
            }
        }
    }
}

I am trying out this problem on Codeforces. https://codeforces.com/contest/478/problem/C

I get the correct output for the test case 5 4 3 as 4 in my system, which is also the output of the sample test case.

Here is my code. Could someone please tell where I am going wrong ?

But the online judge shows my answer as 3 and hence failed in the first test case.

1 Time: 15 ms, memory: 0 KB Verdict: WRONG_ANSWER Input

5 4 3

Participant's output

3

Jury's answer

4

Checker comment

wrong answer 1st numbers differ — expected: '4', found: '3'

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int r,g,b;
	cin>>r>>g>>b;
	int mini=min(min(r,g),b);
	int ans=mini;
	int maxi=max(max(r,g),b);
	int sma;
	if(r!=maxi && r!=mini)
	r=sma;
	else if(g!=maxi && g!=mini)
	g=sma;
	else
	b=sma;

	if(maxi > 2*sma)
	{
		ans+=sma;
	}
	else
	{
		ans+=((sma+maxi)/3);
	}
	
	cout<<ans<<endl;
	return 0;
}

https://leetcode.com/problems/word-search-ii/

I am preparing for my interviews and I am trying out this problem. My approach is based on backtracking and I use Tries to check if a prefix of the current string in the recursion exists in the trie. If a prefix does not exist, then return control back.

This approach passes 32/36 test cases.

How do I optimize this further to pass all 36 TCs ?

Please have a look at my code.

struct Trie
{
	bool is_leaf;
	unordered_map<char,Trie*>children;
	
	Trie(bool il)
	{
		is_leaf=il;
	}
	
	
	bool search(string s)
	{
		int i=0;
		int n=s.length();
		Trie *cur=this;
		while(i<n)
		{
			if(cur->children[s[i]]!=NULL)
			{
				cout<<s[i];
				cur=cur->children[s[i]];
				i++;			
			}
			else
			{
				return false;
			}
		}
	
		
		if(cur->is_leaf)
		return true;
		return false;
	}
	
	bool find_prefix(string s)
	{
		int i=0;
		int n=s.length();
		Trie *cur=this;
		while(i<n)
		{
			if(cur->children[s[i]]!=NULL)
			{
				cout<<s[i];
				cur=cur->children[s[i]];
				i++;			
			}
			else
			{
				return false;
			}
		}

		return true;
	}
	
	
	void add_str(string s)
	{
		int i=0;
		int n=s.length();
		cout<<n<<endl;
		Trie *cur=this;
		while(i<n)
		{
			if(cur->children[s[i]]!=NULL)
			{
				cout<<s[i]<<endl;
				cur=cur->children[s[i]];
				i++;			
			}
			else
			{
				break;
			}
		}
		if(i==n)
		return;
		
		cur->is_leaf=false;

		cur->children[s[i]]=new Trie(1);
		
		cur=cur->children[s[i]];
		
		i++;

		while(i<n)
		{
			cur->is_leaf=false;
			cur->children[s[i]]=new Trie(1);
			cur=cur->children[s[i]];
			i++;
		}
		
		cur->is_leaf=true;
	}
	
};




class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words)     {
        Trie* t=new Trie(0);
        for(int i=0;i<26;i++)
        {
            t->children['A'+i]=new Trie(1);
            t->children['a'+i]=new Trie(1);
        }
        for(int i=0;i<=9;i++)
        {
            t->children['0'+i]=new Trie(1);
        }

        set<string>found;
        unordered_map<string,bool>con;
        vector<vector<bool> >visited(board.size());
        for(int i=0;i<board.size();i++)
        {
            vector<bool>row(board[0].size(),0);
            visited[i]=row;
        }
        for(auto it=words.begin();it!=words.end();it++)
        {
            con[*it]=true;
            t->add_str(*it);
        }
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                string s="";
                if(!visited[i][j])
                {
                    visited[i][j]=true;
                    s.push_back(board[i][j]);
                    findUtil(board,words,i,j,found,s,con,visited,t);
                    s.pop_back();
                    visited[i][j]=false;
                }
            }
        }
        vector<string>ans;
        for(auto it=found.begin();it!=found.end();it++)
            ans.push_back(*it);
        return ans;
    }
    
    void findUtil(vector<vector<char>>& board, vector<string>&words,int i,int j,set<string>&found,string s,unordered_map<string,bool>con,vector<vector<bool> >&visited,Trie* t)
    {
        if(con[s])
        {
            found.insert(s);
            cout<<s<<endl;
            //cout<<i<<" "<<j<<endl;
        }
    

        cout<<i<<" "<<j<<endl;
        
        if(i-1>=0 && i<board.size() && j>=0 && j<board[0].size() && !visited[i-1][j] && t->find_prefix(s))
        {
            visited[i-1][j]=true;
            s.push_back(board[i-1][j]);
            findUtil(board,words,i-1,j,found,s,con,visited,t);
            s.pop_back();
            visited[i-1][j]=false;
        }
        if(i>=0 && i<board.size() && j-1>=0 && j<board[0].size() && !visited[i][j-1] && t->find_prefix(s))
        {
            visited[i][j-1]=true;
            s.push_back(board[i][j-1]);
            findUtil(board,words,i,j-1,found,s,con,visited,t);
            s.pop_back();
            visited[i][j-1]=false;
        }
        if(i>=0 && i+1<board.size() && j>=0 && j<board[0].size() && !visited[i+1][j] && t->find_prefix(s))
        {
            visited[i+1][j]=true;
            s.push_back(board[i+1][j]);
            findUtil(board,words,i+1,j,found,s,con,visited,t);
            s.pop_back();
            visited[i+1][j]=false;
        }
        if(i>=0 && i<board.size() && j>=0 && j+1<board[0].size() && !visited[i][j+1] && t->find_prefix(s))
        {
            visited[i][j+1]=true;
            s.push_back(board[i][j+1]);
            findUtil(board,words,i,j+1,found,s,con,visited,t);
            s.pop_back();
            visited[i][j+1]=false;
        }
            
    }
    
    
};