Problem Statement :

Given a string s, return the longest palindromic substring in s.

My solution

class Solution {
public:
    
    
    
    bool checkPalindrome(int l,int r,string s, vector<vector<int>>& dp)
    {   
        
        //cout<<l<<' '<<r<<dp[l][r]<<endl;
        if(dp[l][r]==-1)
        {
            
            if(r-l<=1)
            {   
               
               //cout<<2<<endl;
                dp[l][r]= s[l]==s[r];
                return dp[l][r];
            }
            else 
            {   
                //cout<<3<<endl;
                bool is_palindrome=checkPalindrome(l+1,r-1,s,dp);
                
                dp[l][r]=s[l]==s[r] && is_palindrome;
                return dp[l][r];
            }
            
        }
        else 
        {
                return s[l]==s[r] && dp[l][r];
        }
        
    }
    string longestPalindrome(string s) {
               
               
               int n = s.size();
               vector<vector<int>> dp(n, vector<int>(n));
               int ans=-1,i,j;
               int curl=-1,curr=-1;

               for(i=0;i<n;i++)
               {
                for(j=0;j<n;j++)
                {
                    dp[i][j]=-1;
                }
               }

              // cout<<checkPalindrome(0,3,"aaca");
               for(i=0;i<s.size();i++)
               {
                for(j=i;j<s.size();j++)
                {   
                   //cout<<s.substr(i,abs(i-j)+1)<<' '<<checkPalindrome(i,j,s)<<endl;
                    if(checkPalindrome(i,j,s,dp) && abs(i-j)>ans)
                    {   
                        //cout<<s.substr(i,abs(i-j)+1)<<endl;
                        ans=abs(i-j);
                        curl=i;
                        curr=j;
                    }
               }

               }
                  //cout<<s.substr(curl,ans+1);
                return s.substr(curl,ans+1);

           //return s;
        
    }
};

It is getting MLE,my 2D vector is not a problem as the constraint is 10^3.

Is it for recursion stack ?

Today I used two maps like that

map<pair<char,int>,int>mp1;

map<pair<char,int>,int>mp2;

It leaded to MLE-Memory Limit exceeded.

I guess some solutions with like this below got accepted-

map<int,vector<int>>mp1

map<int,vector<int>>mp2;

Then a question comes to my mind is there some anticpated benchmarks for using maps.How less complex it should be to avoid MLE?Is there some suggestions?

Is doing div2 A<B<C regularly fast is enough for reaching expert?Do I ever need to solve D?

In order to solve 1300-1600 rated problem,what kind of algo I need to be learned or those also like Div2 A/B,especially I am talking about Div2-c?

Is it not a simple and correct assumption that if anyone solving a particular rated problem like all under and inclusive 1400 in contest time regulary like for 4-5 contests,he/she will become 1400/specialist?

Am I wrong here ?

For this Problem

1829E - The Lakes

The solution is written in O(n*m)

But How it is possible if there is recursion calls inside the nested solution.

Solution in tutorial is:

https://mirror.codeforces.com/blog/entry/116108 (Problem E)

Please someone help me understand the time complexity?Shouldn't it be O(n*m*n*m).I know we are not checking same grid twice.

Please someone help me.

In coding interviews,how much time is given for solving a single problem?As one can prepare for interviews by allocating time while practicing,this information can help him/her.

Can anybody give me idea about leetcode contests problem difficulty compared to codeforces level?

I have a string which is empty initially.Then I added characters to it.

string s="";
s=s+'a';

it works fine in my pc but getting error in codeforces submission because it prints garbage at the end of hathe printed string.

Same things happen I use vector of char.In that case I use push_back method to add chars.But it still prints garbage in codeforces submission.

vector<char>vc;
vc.push_back('a')

Why is that happening? /predownloaded/42/08/4208fdc2b1a8d618adc8327184077c6b4baa0b60.png

Codeforces problems are always entitled with many tags assuming there are diverse solution approach for problems.

If one solved a problem with greedy approach which is in the tags,then if he want to know the data structure approach to solve a problem how can he find the other tags approach?

Here is the link of problem at atcoder:

I tried it with a naive recursion approach. It's running good with the testcases in my pc but getting RE in atcoder compiler. I have no clue how it is getting RE.

Here is the solution

#include<bits/stdc++.h>
using namespace std;
int N,sum=0,mn=INT_MAX,h[100006];
int recur(int i,int sum)
{
   if(N>=4)
   {
       return mn=min(sum,mn);
   }
    else
    {
       recur(i+1,sum+abs(h[i+1]-h[i]));
       recur(i+2,sum+abs(h[i+2]-h[i]));
    }
}
int main()
{
    int n,i,j,k;
    cin>>N;
    for(i=1;i<=N;i++)
    {
        cin>>h[i];
    }
    cout<<recur(1,0)<<endl;
    return 0;
}

We have an array which is produced from a sorted array by right shifting array elements some number of times.

Like [4,5,6,1,2,3] is produced from [1,2,3,4,5,6] by right shifting the sorted array 3 times.

The sorted array is always increasing.

If the given array cannot be produced from any increasingly sorted array the answer is no, otherwise answer is yes.

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=565

does it allow multiple solution?

like 43 2 is a correct answer for the fifth test case?

I am getting wrong answer and the problem description is not clearing it.

Where to get a dfs based problemset hierarchical, I mean easy to upper level hierarchy.Please anybody help me out as I just learn dfs.

Here is my submission Submission

It seems to be both output and answer is same.Though it is giving wa. Please can anybody help me out?

In this problem,I have come up with a solution that is only equal bit length numbers meet the condition of & operation >= XOR operation. That means number 2-3,4-7,8-15.... meet the conditions given in this problem.

Based on this idea, I write a solution, But this is giving always wrong answer. I am so frustrated and don't have a clue what is missing.

My code is

Can anybody please help me,what is wrong with my approach?

I have submitted my solution for a problem quite a while ago.But it still showing in queue,is there any problem.What are the reason for that?

We all know that, in recent years codeforces popularity rose very high. Thus participants in contests have grown to a large number. I want to know that, does increased participant number somehow devalued the ranking of those who participated with fewer number of participants?

I mean ,is 1400+ rating in 6-7 years back is devalued compare with today's 1400.

Why second loop of sieve of Eratosthenes starting from square of current prime number?

vector<bool>vc(100006,1);
void seive(int n)
{
    vc[0]=vc[1]=0;
    int i,j;
    for(i=2;i*i<=n;i++)
    {
        if(vc[i]==1)
        {
            for(j=i*i;j<=n;j=j+i)
            {
                vc[j]=0;
            }
        }
    }

}

My question is why the second loop starting from square of i. How the multiples before the square of current prime(i) getting marked ?Actually how are we so sure of it?

There are many problems statement with this written.Actually what does mean by it from the view of time complexity?

A famous company in our country recruits people by asking them to solve problems without using C++ STL. Their problemset having problems on Searching Techniques, BFS, DFS, Tree Traversal, Prefix Tree or Trie , Backtracking and A glimpse of Dynamic Programming and many others.

Now I wonder how one can solve problems without STL. Like when using BFS how one can not using queue, vector, etc.

Can anybody please help me how to solve problems without STL?

Problem:

A man just come to codeforces with basic knowledge of CP. After looking the contests and taking part in some of it,he decided to do a strange thing that is he will never solve a problem none but the DIV2-D.He decides that with all the 2/2.5/3 hours he will get in a live contest, he will use those time to solve his favourite problem DIV2-D.

But as his very early days in CP he does not know any DSA or anything. He become frightened and helpless that he might not be able to gain the capability to solve just his favourite problem DIV2-D.Now he ask for help?

What path he should follow now to fulfill his dream.Let help help him .But there is a condition you cannot say him practice more D.He need to know the learning and practicing roadmap for achiving his dream.

I am wishing to deep dive in Competitive Programming .I want to have a list of Basic DSA. Can you people help me with the basic DSA list and tutorial && Problem resources.I want it as simple as possible.