### antivenom's blog

By antivenom, 7 years ago,

Hi everyone.How can I do this question using segment tree with lazy propagation.

Given an array.

query type 1: Find xor from L to R.

query type 2: Update element present at L to X.

query type 3: Update element from L to R to X.

Would anybody mind explaining how to do this question using SEGMENT TREE+LAZY PROPAGATION .I am not really getting Idea behind lazy propagation so please explain to me using this question.Good day.

• +5

By antivenom, 7 years ago,

So question is something like this- "We are given a tree(weighted) and we have to find longest path in the tree and number of all such possible paths ".Number of nodes is of order (<=10^4).

If I am not wrong part 1 can be done using two dfs(please point me if it is wrong).For the second parth I thought it must be some dynamic programming but could not get to any solution.Help me to find "How many such possible path(with longest distance) exist in the tree" ?

• 0

By antivenom, 7 years ago,

Hello everyone,Question is something like this:: We are given the adjacency matrix for a graph of n vertices(n<=1000) and we need to find the number of edges we need to delete in order to make it a tree.I did this question by applying kruskal's algorithm and I passed all the cases but I can't convince myself that I did correct.I feel as if it was just a blind shot.Can anybody assure me about the correctness or give some other approach to solve this.

My code looks like this.

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define nline cout<<"\n"
#define fast ios_base::sync_with_stdio(false)cin.tie(0)
#define ain(A, B, C) assert(IN(A, B, C))
#define ull unsigned long long int
#define ll long long int
#define pii pair<int,int>
#define MAXX 1009
#define fr(a,b,i) for(int i=a;i<b;i++)
vector<int>G[MAXX];
int a[MAXX][MAXX],cnt=0;
int parent[MAXX],r[MAXX],n;
int find_p(int v){
return (parent[v]==v?v:parent[v]=find_p(parent[v]));
}
void unionme(int a,int b)
{
if(r[a]>r[b]){
parent[b]=a;
}
else{
parent[a]=b;
}
if(r[a]==r[b]){
++r[a];
}
}
void kruskal()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j] or a[j][i]){
int aa=find_p(i);
int bb=find_p(j);
if(aa!=bb){
unionme(aa,bb);
a[i][j]=a[j][i]=0;
}
else
{
cnt++;
a[i][j]=0;
a[j][i]=0;
}
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)parent[i]=i,r[i]=0;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
kruskal();
cout<<cnt<<endl;
return 0;
}



• +3

By antivenom, 7 years ago,

Hello everyone.Please help me in this question.I tried implementing some sort of recursive solution.One like maze solving.I am fairly new to recursion and badly trapped in this one.Help me.My solution run endlessly.Here is what I did.Please improve my solution.

• +1

By antivenom, 7 years ago,

Hi guys,I am practising recursion nowadays and I found this good question based on recursion more of backtracking.I did this question using next_permutation() method.But I find no learning in using a predefined method for this good question(It can teach many good things about recursion)I am really messed up with recursion.can anyone explain me how recursion will do in this question.Thanks

• 0

By antivenom, history, 7 years ago,

Hi everyone,I am learning Graphs for few days so every question looks graph to me.I tried this question and thought of graph(bfs) but for some reason it is running indefinitely.Any help appreciated :).Link solution

• 0

By antivenom, 7 years ago,

Hello everyone,after few months in CP.I have realized some flaws in me.Whenever I try to learn something I face difficulty in converting pseudo code into working code in language(say C++).It is not that i don't know C++.I have decent knowledge.But when it comes to converting what I have learnt I face difficulty.I always search for exact code which I feel comfortable and because of this Many thing I get deprived off.It will be really helpful if anybody could guide me.Thanks

• +4

By antivenom, 7 years ago,

Can anybody help me how to solve this question using segment tree.I am not getting what values should I maintain for nodes in order to get final result and how to merge them back to get parent of the childres etc.if possible please provide source code also.Thanks a lot

• 0

By antivenom, 7 years ago,

I am continuously getting error in my solution.I cant claim that my logic is correct.I will be obliged if anybody can tell me about my mistake.Thank you Link solution and Link question

• 0

By antivenom, history, 7 years ago,

Hello all,with best of my knowledge I wrote my 3rd graph solution for this question.I spent so much time thinking on it but after submitting it,it gave out TLE.As i am amateur in Graphs,I will be obliged if some one come out for help :) link of my code

• -3

By antivenom, history, 7 years ago,

How to solve this question with the help of dfs/bfs/dijktra(as mentioned in ahmed-aly.com).This particular question has not been discussed much and don't have good resources to know about it.

• -3

By antivenom, history, 7 years ago,

Hello,I was trying this question and thought to use Dynamic programming but it will exceed memory limit.Can anybody give me a sight how to solve this question.

• -3

By antivenom, history, 7 years ago,

Hello everyone,I am new to Dynamic programming and what I have observed that in any question whenever I think that this is a permutation combination question,it comes out to be a DP.So my question from you guys is that is permutation and combination Dp in competitive coding.Like this question I thought of P&C but its a Dp

• +5

By antivenom, history, 7 years ago,

Sorry peoples I don't usually post something like my code giving RTE please fix that but this time I am asking help for this.I have tried segment tree implementation many times but never got sucess.I request if anybody can take a glance at my code and point out what's going bad...My code link

• +3

By antivenom, 7 years ago,

Hey guys,I just encountered with a very Interesting and tough problem(at least for me).It is asked to calculate second shortest path from node 1 to N.Can anybody have some idea how to solve this with Dijktra's .In case you want to check if I have tried or not see this(yes,I know I have done nothing special but normal dijktras)

• +3

By antivenom, history, 7 years ago,

Hello guys,Just see Amr_Hassan and see his submissions with submission time.I am so confused.Is he a bot??

• +4

By antivenom, 7 years ago,

Hello,After seeing this question the first thing came to my mind was Dynamic programming.I tried constructing a solution but could not make it,maybe because i don't have that much of experience.

  #include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m,a,b;
cin>>n>>m>>a>>b;
int final=0,dp[n+1];
dp[0]=0;
for(int i=1;i<=n;i++)
dp[i]=min(dp[i-1]+a,dp[i-m]+b);
cout<<dp[n];
return 0;
}


P.S:I know it can be solved without using Dp,but i request you to give Dp approach if it is possible.