Hello Coders, Please checkout video to see solution for problem 1 and 2 of Trilogy Innovations(CodeNation) 15th May 2022 Test. Problems were very nice to solve.

Video Link — https://youtu.be/phE4EL41rC8

Hello Coders, Recently In online test of BNY company these two questions were asked. It will be great if someone can give approach to solve these questions.

1. Given two arrays of integer A and B of length n. We have to choose k indexes such that min(Sum of elements of A at chosen indexes, sum of elements of B at chosen indexes) is maximized. We have to return that maximum sum.

1<=A[i],B[i],n<=50

1<=k<=n

1. Given integer array A of length n. Initially our power will be 0. Now in one operation we can choose two indexes i and j, i != j. Now we can add A[i] ^ A[j] to power and have to remove any one element. So after n — 1 operation we will be left with only 1 element. At that point we have to stop the process. We have to return what is the maximum power we can collect.

1 <= n <= 1000

1 <= A[i] <= 10^9

Hello, Can anyone provide hint to solve below problem on segment tree.

Problem Link:Problem Link

Problem Description:

A city is a sequence of n cells numbered from 0 to n−1. Initially, all cells are empty. Then m events of one of two types occur sequentially:

a building with the strength h is being constructed in the cell i (if the building already existed in this cell, it is demolished and replaced with a new one),

in the interval from l to r−1 an earthquake of power p happens, it destroys all buildings whose strength is not more than p. Your task is for each earthquake to say how many buildings it will destroy.

Input

The first line contains the numbers n and m, the number of cells and the number of events (1≤n,m≤105). The following m lines describe events. The description of each event is as follows:

1 i h: a building with the strength h is constructed in the cell i (0≤i<n, 1≤h≤10^9).

2 l r p: an earthquake of power p happens on a segment from l to r−1 (0≤l<r≤n, 0≤p≤10^9).

Output

For each event of the second type, print how many buildings were destroyed.

Hello, Can anyone explain idea to solve E. Lucky Array problem. I tried to understand from editorial but I'm finding difficult to understand. Problem Link:E. Lucky Array

Problem Description: Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya has an array consisting of n numbers. He wants to perform m operations of two types:

add l r d — add an integer d to all elements whose indexes belong to the interval from l to r, inclusive (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ 10^4);

count l r — find and print on the screen how many lucky numbers there are among elements with indexes that belong to the interval from l to r inclusive (1 ≤ l ≤ r ≤ n).

Each lucky number should be counted as many times as it appears in the interval. Petya has a list of all operations. The operations are such that after all additions the array won't have numbers that would exceed 10^4. Help Petya write a program that would perform these operations.

Hello, Is it possible to do range add query in segment tree for XOR queries as we can do for sum queries. I am not finding way to do it. Because for range add for sum, we can update parent node and push update for child so we can use lazy propagation. But for range add for XOR queries how can we update parent node without updating child nodes?

Hii Coders, Recently I gave NCR Campus Codewar Test on Hackerearth. Has anyone get any update about shortlist?

Also in Hackerrank it is showing "Not Participated", why?

Hello Everyone,

There are many solutions for LCA query,like simple O(N) by traversal only,O(log(N)^2) using Binary lifting + Binary Search,Also most famous O(log(N)) solution. But recently I when I was learning about sparse table, I accounted with O(1) sol for each query using Euler Tour+RMQ using Sparse table. I tried to submit sol using this on SPOJ and CSES problem set and got accepted.

 #include "bits/stdc++.h"
using namespace std;
#define for1(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
const int N=5e5+5;
int log1[N],first1[N],vis[N];
vector<int> adj[N],euiler,old_ind;
void dfs(int i,int par){
    int new_ind=old_ind.size();
    old_ind.push_back(i);
    first1[i]=euiler.size();
    euiler.push_back(new_ind);
    for(int x:adj[i]){
        if(x!=par){
            dfs(x,i);
            euiler.push_back(new_ind);
        }
    }
}
void sparse(int n,vector<vector<int>> &v){
    int p=log1[n];
    vector<int> v1(n+1,0);
    for(int i=0;i<=p;i++) v.push_back(v1);
    for(int i=1;i<=n;i++){
        v[0][i]=euiler[i];
    }
    for(int j=1;j<=p;j++){
        int len=(1<<j);
        int len1=len/2;
        for(int i=1;i+len-1<=n;i++){
            v[j][i]=min(v[j-1][i],v[j-1][i+len1]);
        }
    }
}
int query(int l,int r,vector<vector<int>> &v){
    int len=r-l+1;
    int p=log1[len];
    return min(v[p][l],v[p][r+1-(1<<p)]);
}
int main()
{
   ios_base::sync_with_stdio(false);cin.tie(NULL);
    for(int i=2;i<N;i++){
        log1[i]=1+log1[i/2];
    }
    int t;cin>>t;
    int kk=1;
    while(t--){
        vector<vector<int>> v;euiler.clear();
        old_ind.clear();
        cout<<"Case "<<kk++<<":"<<endl;
        int n,m,u1,u2;cin>>n;
        for1(i,1,n+1){
            cin>>m;
            while(m>0){
                m--;
                cin>>u1;adj[i].pb(u1);vis[u1]=1;
            }
        }
        int root;
        for1(i,1,n+1){
            if(vis[i]==0){
                root=i;break;
            }
        }
        dfs(root,-1);
        sparse(euiler.size(),v);
        int q,l,r,ind1,ind2,ind;cin>>q;
        while(q--){
            cin>>l>>r;
            ind1=first1[l];ind2=first1[r];
            if(ind1>ind2){
                swap(ind1,ind2);
            }
            ind=query(ind1,ind2,v);
            cout<<old_ind[ind]<<endl;
        }
        for1(i,1,n+1){
            vis[i]=0;
            adj[i].clear();
        }
    }
    return 0;
}

#include "bits/stdc++.h"
//#include <algorithm>
#define ll long long 
#define mod 1000000007
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define lb lower_bound
#define ub upper_bound
#define endll "\n";
#define all(x) (x).begin(), (x).end()
#define forr(it,x) for(auto it=x.begin();it!=x.end();it++)
#define for1(i,a,b) for(int i=a;i<b;i++)
#define for2(i,a,b) for(int i=a;i>=b;i--)
#define for3(i,a,b) for(long long int i=a;i<b;i++)
#define for4(i,a,b) for(long long int i=a;i>=b;i--)
#define pp pair<int,int>
#define ld long double
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpp vector<pp>
#define vi vector<int>
#define vpll vector<pll>
#define vld vector<ld>
#define vvld vector<vld>
#define vvi vector<vi>
#define vvll vector<vll>
#define vvpll vector<vpll>
#define vvpp vector<vpp>
#define I insert
#define mem(a,x) memset(a,x,sizeof(a))
#define p_queue(a) priority_queue<a,vector<a>,greater<a>>
using namespace std;
const int N=5e5+5;
vi adj[N];
int log1[N],first1[N];
vector<int> euiler,old_ind;
void dfs(int i,int par){
    int new_ind=old_ind.size();
    old_ind.push_back(i);
    first1[i]=euiler.size();
    euiler.push_back(new_ind);
    for(int x:adj[i]){
        if(x!=par){
            dfs(x,i);
            euiler.push_back(new_ind);
        }
    }
}
void sparse(int n,vector<vector<int>> &v){
    int p=log1[n];
    vector<int> v1(n+1,0);
    for(int i=0;i<=p;i++) v.push_back(v1);
    for(int i=1;i<=n;i++){
        v[0][i]=euiler[i];
    }
    for(int j=1;j<=p;j++){
        int len=(1<<j);
        int len1=len/2;
        for(int i=1;i+len-1<=n;i++){
            v[j][i]=min(v[j-1][i],v[j-1][i+len1]);
        }
    }
}
int query(int l,int r,vector<vector<int>> &v){
    int len=r-l+1;
    int p=log1[len];
    return min(v[p][l],v[p][r+1-(1<<p)]);
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    for(int i=2;i<N;i++){
        log1[i]=1+log1[i/2];
    }
        vector<vector<int>> v;
        int n,u1,q;cin>>n>>q;
        for1(i,2,n+1){
            cin>>u1;
            adj[u1].push_back(i);
        }
        dfs(1,-1);
        sparse(euiler.size(),v);
        int l,r,ind1,ind2,ind;
        while(q--){
            cin>>l>>r;
            ind1=first1[l];ind2=first1[r];
            if(ind1>ind2){
                swap(ind1,ind2);
            }
            ind=query(ind1,ind2,v);
            cout<<old_ind[ind]<<endll;
        }
    return 0;
}

Now I have only one doubt that is this O(1) solution has any flaw?

If yes,what?

And if not,as far as I know this sol is not so famous compared to log(N) sol,why? even it is easy to code.It might possible that it is famous but I didn't know that.

Hello Coders, Suppose I have string s and I'm creating new string s1 by s1=s[j--]+s1 where j is initially (j=s.length()-1). Is this operation in C++ is time costly.

Because I was solving D2. Prefix-Suffix Palindrome (Hard version) problem.In this problem we are given string s,and we need to find string t,which satisfy given condition.

1)The length of t does not exceed the length of s.

2)t is a palindrome.

3)There exists two strings a and b (possibly empty), such that t=a+b ( "+" represents concatenation), and a is prefix of s while b is suffix of s.

I tried to solve it in following way,

1)string s1=s2="" and i=0,j=s.length()-1, now till s[i]==s[j],I added elements to s1 and s2; ie. s1+=s[i++],s2=s[j--]+s2;

2)after first step whatever string remains unused,I found longest prefix and suffix palindrome using manachers alg,and choosen max of them.

Now Main point is that when I submitted it was giving TLE on testcase 13. then I just tried to change s2=s[j--]+s2 by just only finding s1 and s2 will be obviously reverse of s1. And my code gets Accepted.

So my question is how can s2=s[j--]+s2 can be reason for TLE?

sol having TLE.

Accepted sol.

Both sols only differ in way I calculated s2.

UP1: I don't know what's wrong with some people, I have seen many comments in announcement or in tutorial section that's are either funny or sarcastic or memes ,and they gets many upvotes,I'm not saying that should not be upvoted,in fact If I like,I also upvotes them.But when some one ask for doubt most of the time it gets downvoted. IDK why?

I think many people started taking it in wrong way, they think that If they didn't like post or comment then it should be downvoted.But what is meaning of contribution? If someone if contributing to community then he should get +ve contribution and If he is spreading negativity,he should be downvoted.

But when someone ask doubt then surely he is not harming community, also he is not contributing to community either because he asked doubt for himself and it may not be useful to all people.So when someone ask doubt,two things possible either his doubts may not be useful to someone or someone having similar doubt can solve it by reading comments by others. Then how it is harming community that many are downvoting. If they thinks it is not useful they can just ignore it,what's reason for downvote.

I just tried to said what I felt after seeing downvotes on my this blog and others blogs asking for doubts,May be I will be downvoted for saying this.

Hello! In my submission 80851257 to the problem E. Graph Coloring I'm getting RUNTIME_ERROR with Exit Code -1073741819. I don't know what's wrong with my code? I tried in my IDE it's working fine, Also I run same code on online IDE:Can see here and it's running fine but it is giving RUNTIME_ERROR on CF.Can Anyone Explain?