Problem link

I could not think of any approach but just am getting an intuition of using DSU in reverse or querying offline but I can't think of anything. Someone please help.

I just need an approach not complete code.:)

Since most of the engineering colleges are having placement tests in India, I believe all those students can use this blog for discussion of questions being asked in different colleges. Feel free to post questions in the comment section with relevant descriptions and examples and someone from the community will surely help I believe.

Those who are not interested/Indians please ignore the blog.

I have a problem: Given two numbers in l and r where l<=r and can be as large as 1e18, I want to count the number of palindrome numbers in the range l to r such that they are a square of some palindrome number.

For example, I have L=4 and R=1000

ans = 4 , numbers are 4, 9, 121, 464.

My code:

code

I am getting the wrong answer on this test case

L=92904622 R=232747148

My answer is 3 but the correct answer is 6.

My approach is to generate all palindromes of length at most 10 and then check if their square is also a palindrome.

I am generating palindromes as follows,

For length 1 I have 10 palindromes from 0 to 9 and for length 2 I have 9 palindromes of the form {11, 22,.., 99}.

Now for forming l length palindrome I simply append digits 1 to 9 at the beginning and the end to each of the generated palindromes of length l-2

Can someone point out what am I doing wrong??

Any help is appreciated.

Problem link : link

code : link

I am considering each element as a maximum element and then determining the size of the subarray in which that element can be maximum. If x is my maximum element and y is my minimum element in the optimal subarray, then we have (x-y)<B which implies that my y should be -> x-B< y <= x . Now I store the elements in a vector of pair where the first element is the element at index i and the second element is the index i. Then I sort it based on the first element. After that, I build a segment tree on the modified index array to get the maximum and minimum index of y which will then determine our ans.

In other words, if v[i] is my maximum element of the optimal subarray I need to find the maximum and minimum index of an element in the entire array which has a value y satisfying v[i]-B< y <=v[i]. For this purpose, I am using a segment tree to store the maximum and minimum index in a range and that range I am finding with the help of lower_bound and upper_bound.

If you look at the code maybe you can understand what I am trying to say.

This is giving wrong answer.

Can someone please help me, whether my approach is wrong or am I doing some implementation mistake.

Sorry for poor explanation of my code .

I was wondering if we can find the mother vertex in a directed connected graph by topological sorting. The last finished vertex will be the mother vertex.

Is this approach correct or am I thinking wrong?

Hi, I was going through this point of bfs application from cpalgorithms,

Find the shortest path of even length from a source vertex s to a target vertex t in an unweighted graph: For this, we must construct an auxiliary graph, whose vertices are the state (v,c), where v — the current node, c=0 or c=1 — the current parity. Any edge (a,b) of the original graph in this new column will turn into two edges ((u,0),(v,1)) and ((u,1),(v,0)). After that we run a BFS to find the shortest path from the starting vertex (s,0) to the end vertex (t,0).

I was wondering if this problem can be solved as follows:

Run bfs from src and store the shortest distance from src in an array a.
Run bfs from dest and store the shortest distance from dest in an array b.
Now iterate over all the vertices u and check if a[u]+b[u] is even and if so then get the minimum distance.
Is this approach correct or am I thinking wrong.

Can someone suggest some method to count the number of prefixes of a given string which are also palindromes? It would be even helpful if I can get a boolean array of the length of string where a true denotes that a prefix up to this index is a palindrome.

Right now I have a simple 2d dp approach where dp[i][j] is true if string i to j is a palindrome, but this is O(n2). Is there some O(n) or O(nlog(n)) method thankyou.

problem : link

code : link

My approach is also the same as mentioned in the editorial but I am getting wrong answer.

Instead of using two separate memoisation table for true and false I am using only one dp

dp[i][j][w] = the number of ways to put parenthesis such that the result is w

where w is 1 for true and 0 for false;

Can someone tell me where am I wrong

code

I cannot estimate the time complexity of this code? This code is for optimal binary search tree dp problem.

Is it O(n3) or O(n4) or O(n2)

Someone please help.

Also if someone could tell me some tutorial on how to find time complexity of recursion.

Problem : link

Code : code

My approach is : For any {i,j} I maintain 4 colors dp[i][j][0],dp[i][j][1],dp[i][j][2] and dp[i][j][3];

dp[i][j][k] denotes the number of ways to fill the board[0..i][0..j] using the color k at position i,j.

To fill dp[i][j][k] we need only summation of (dp[i-1][j][l]+dp[i][j-1][l]) where l varies from 0 to 3 and l is not equal to k.

In simple words to fill i,j with color k number of ways would be we can fill i-1,j with color other than k and i,j-1 with color other than k.

In the end my answer would be summation of dp[3][n][k] where 0<=k && k<=3;

Why is this approach wrong as I am getting wrong answer for n=2 test case?

Any help is appreciated.

Can someone please help me in binary search. I am confused whether to use

--> l=0 , h = arr.size()-1 and m = (l+h)/2 and while(l<h)

--> l=0 , h = arr.size() and m = (l+h+1)/2 and while(l<h)

--> l=0 , h = arr.size()-1 and m = l+(h-l)/2 and while(l<h)

--> l=0 , h = arr.size()-1 and m = (l+h)/2 and while(l<=h)

It seems that in some cases some of the above give TLE. Can some experienced community member help me which I should use .

I think many of the beginners face this issue while implementing binary search . A little help would be appreciated

So basically there are confusion regarding

while(l<h) or while(l<=h) or while(h-l>1)

m=(l+h+1)/2 or m=l+(h-l)/2 or m=(l+h)/2

h=arr.size() or h=arr.size()-1

Problem link : link

code :

for(int i=1;i<27;i++)

{

    fact[i]=fact[i-1]*i;

    fact[i]%=hell;

}

if(fact[26]==1)

    oncer();

long long int ans=0;

string s1=s;

sort(s1.begin(),s1.end());

if(s==s1)

    return 1;

for(int j=0;j<s.length();j++)

{

    if(s[0]==s1[j])

    {

        ans+=j*fact[s.length()-1];

        ans%=hell;

        break;

    }

}

return (ans+findRank(s.substr(1)))%hell;

This gives only 23 points on interviewbit and says that the code might be failing for larger test cases. Can someone give a test case where my code might fail. I have tried a lot of test cases and all those cases match the expected output.

Problem link: link

My code

if(s>e)

    return {0,0};

if(dp.find({s,e})!=dp.end())

    return dp[{s,e}];

pair <int,int> l;

l=help(a,s+1,e);

int s1,s2;

s1=l.second+a[s];

s2=l.second-a[s];

if(abs(s1)<=abs(s2))

    return dp[{s,e}]={l.first,l.second+a[s]};

else

    return dp[{s,e}]={l.first+1,l.second-a[s]};

dp.clear();

vector <int> a;

a=A;

return help(a,0,a.size()-1).first;

We have 2 choices for each element either + or — I am considering both the choices and then picking the optimal one. In the code the dp[i].first = the minimum number of sign inversions dp[i].second = the optimal sum we achieve by either inverting this one or not;

It fails on array 10 4 3 2 1

Can someone point out why my aaproach is wrong?

I have solved the maximum product subarray problem using divide and conquer. Can someone help me with the time complexity of my solution . Whether it is O(log(n)) or O(nlog(n)) . I am confused please help.

int premin,premax, sufmin,sufmax, p,prod;

node ans;

if(s==e)

{

    ans.premin=ans.sufmin=ans.sufmax=ans.p=ans.prod=ans.premax=a[s];

    return ans;

}

int m=(s+e)/2;

node l=help(a,s,m);

node r=help(a,m+1,e);

ans.p=max(l.p,max(r.p,max(l.sufmax*r.premax,l.sufmin*r.premin)));

ans.premax=max(l.premax,max(l.prod*r.premax,l.prod*r.premin));

ans.sufmax=max(r.sufmax,max(r.prod*l.sufmax,r.prod*l.sufmin));

ans.premin=min(l.premin,min(l.prod*r.premax,l.prod*r.premin));

ans.sufmin=min(r.sufmin,min(r.prod*l.sufmax,r.prod*l.sufmin));

ans.prod=l.prod*r.prod;

return ans;

return help(a,0,a.size()-1).p;

My approach is either the max product subarray lie in left half or right half or be passing through the middle. In the third case the answer can be formed from max of following:

left part's maximum suffix product * right part's maximum prefix product

left part's minimum suffix product * right part's minimum prefix product

as elements can be negative

Problem Link — problem

code —

int Solution::jump(vector<int> &a) {
    int n=a.size();
    vector <bool> visited(n,false);
    visited[0]=true;
    queue <int> q;
    q.push(0);
    int ans=0;
    while(!q.empty())
    {
        int n1=q.size();
        for(int i=0;i<n1;i++)
        {
            int s=q.front();
            if(s==n-1)
                return ans;
            q.pop();
            for(int j=s;j<=min(s+a[s],n-1);j++)
            {
                if(!visited[j])
                {
                    visited[j]=true;
                    q.push(j);
                }
            }
        }
        ans++;
    }
    return -1;
}

Why is this giving TLE? I am only visiting each array index only once.I am considering this as a graph problem where the neighbors of a node are all the indices reachable from that index.Then BFS will clearly result in the shortest path to reach index n-1.Can someone help me please..

Your title here...I am following the editorial for this problem 489D - Unbearable Controversy of Being and am getting TLE on test case 7. 55729287

Can someone point out what is the difference between my implementation and Mike's.

Your text to link here...

I am also using brute force of selecting the two end nodes and then counting the number of intermediate nodes which provide path length of 2 between the selected nodes.

Anyone out there???

Why does this code get accepted 55539853 and this does not 55539543?

I believe the time complexity of 1st submission is O(k(n+m)) for k bfs and then O(nklog(k)) for sorting each node.

Can someone tell the complexity of the second code because of which it is failing.

For getting s smallest element I am using slog(s) complexity in bfs in 2nd submission.

I want help please don't down-vote.

I want to print the cycle in an undirected graph. I know how to detect cycle in an undirected graph but can't determine how to find the vertices involved in the cycle. Here is the code to find cycle.

if(ch!=p&&visited[ch])

{

    return true;

}

if(!visited[ch])

{

    if(dfs(ch,s))

    {

        return true;

    }

}

Can someone please tell me how to modify this so that I can get the vertices in the cycle as well.

I have seen geeksforgeeks article on printing all cycles but I can't understand it. Is there some simpler approach ?

Is this code to detect cycle in an undirected graph correct. I have run it on a few test cases and it seems good . Can someone from the community verify it.

code:

visited[s]=true;

for(auto ch:adj[s])

{

    if(ch!=p&&visited[ch])

    {

        path.insert(ch);

        return true;

    }

    if(!visited[ch])

    {

        if(dfs(ch,s))

        {

            path.insert(ch);

            return true;

        }

    }

}

return false;

Problem Link : link

code link : code

In the bfs part I am extracting nodes at a given level and then in help function I am greedily sorting the CT and TT by CT time in acsending order as we want the developer to finish the module code asap so that the tester can attend to it. Also I believe that it doesn't matter if we process level 1 first and then subsequent levels as I am adding the time of each level to my answer. Why is this code giving WA. Any help is appreciated.

P.S- No one was able to solve this problem in the contest and thus it seems an interesting problem.

Problem : problem

Code :

vector<int> majorityElement(vector<int>& nums) 

{

    srand(time(NULL));

    int c=0,n=nums.size();

    vector <int> ans;

    while((n-c)>(n/3))

    {

       int i=rand()%n,f=0;

        int x=nums[i];

        for(int j=0;j<n&&x!=INT_MAX-1;j++)

        {

            if(nums[j]==x)

            {

                nums[j]=INT_MAX-1;

                f++;

            }

        }

        //cout<<x<<" "<<f<<" ";

        if(f>(n/3))

            ans.push_back(x);

        c+=f;

    }

    return ans;

}

. I want to know the time complexity of my algorithm. Although it runs within 16 ms on leetcode but is it really O(n) time and O(1) space??

Why does this solution fail at test 21 ?? code : 51444038. and this solution gives AC though code : 51444907 . Aren't the two doing the same thing??

Problem : problem

My code : code

Why is my DSU solution failing on test 14. Am I applying wrong logic Please help

I want to know what is the minimum contribution one can have on codeforces. I am currently at -68 , is there anyone with less contribution than this? Also does having negative contribution affect the accessibility of features on codeforces?? Can the community help me beat r_pi in negative contribution. Come on it's time for a change. bring those downvotes assholes xD

problem link : LINK

submission link : code

I am adding words to the trie and while adding i also store at each node the lexicographically largest encrypted code encountered till now in it. As the encrypted code is unique for all the strings I maintain a hashmap with key=encrypted string and value = original string Then for any query my answer is simply the number of vowels in the original string found after searching the prefix in trie. Why is my code giving wrong answer. Can someone provide some test cases where this fails??

P.S. why are people downvoting this