The problem is not yet added to the practice portal
It is already added dear.
I tried to solve it using bicoloring(dfs) but getting TLE on subtask 2 of task 2. Can someone help me ? Here is my code:
https://www.codechef.com/viewsolution/15367330
The editorial seems actually very long. But its good as it is detailed.
I have summarized the tutorial in my short ~10 min video here : https://www.youtube.com/watch?v=6qWg7-O4Fmg
You can refer this for complete list of video tutorials for SEP17 including WEASTELX.
The editorial seems actually very long. But its good as it is detailed.
I have summarized the tutorial in my short ~10 min video here : https://www.youtube.com/watch?v=6qWg7-O4Fmg
You can refer this for complete list of video tutorials for SEP17 including WEASTELX.
Yeah, but was not visible at that moment. Fixed now.
I used bipartite graph for 1 difference edges and disjoint sets for 0 difference edges. I am getting WA. Please, take a look at the code :
[1]
[1]: https://www.codechef.com/viewsolution/15414051
I have used the same approach
Explanation https://discuss.codechef.com/questions/109357/fillmtr-editorial/110997
A link to code is given alongwith…
Feel free to ask anything…
Upvote…
@taran_1407
Sorry I don’t know how to reply to your comment.
I used the same approach. Can you find out why my code is getting TLE in the 2nd task of the 2nd subtask ?
[My Code][1]
[1]: https://www.codechef.com/viewsolution/15379751
` cananyone tell me why my logic isnt working
#include
#include
using namespace std;
/*
*
*/
const int MAX=2e6+9;
int main() {
int i ,t ,n ,q;
cin>>t;
while(t--){
cin>>n>>q;
int v[MAX]={0} ,x ,y ,d , a[MAX]={0};
for(i=1;i<=n;i++){
a[i]=0;
v[i]=0;
}
int f=0;
while(q--){
cin>>x>>y>>d;
if(x==y){
if(d!=0){
f=1;
}
v[x]=1;
a[x]=0;
}
else if(v[x]==0&&v[y]==0){
a[x]=0;
a[y]=d+a[x];
v[x]=1;
v[y]=1;
}
else if(v[x]==0&&v[y]==1){
a[x]=a[y]+d;
v[x]=1;
}
else if(v[x]==1&&v[y]==0){
a[y]=a[x]+d;
v[y]=1;
}
else if(v[x]==1&&v[y]==1){
if(abs(a[x]-a[y])!=d){
f=1;
}
}
}
if(f==1){
cout<<"no"<<"\n";
}
else{
cout<<"yes"<<"\n";
}
}
}
`can anyone tell me why my logic is not working
first i declared two array a[] and other array v[] array v will keep the record of all the integers which
are visited now during each query 4 condition arises
- both 1st and 2nd are unvisited
- 1st is visited and 2nd is unvisited
3 1st is unvisited and 2nd is visited
4 both are visited
now
for the 1st condition
i marked both the nodes as visited
and assigned a[i]=d;
a[j]=a[i]+d;
for the 2nd condition
marked 2nd node as visited
a[j]=a[i]+d;
for 3rd condition
marked 1st node as visited
a[i]=a[j]+d;
for 4 th condition
since both nodes are visited and are assigned some values
therefore
if(abs(a[i]-a[j])!=d)
ans=no and exit
else
ans=yes;
Will anyone please tell me whats the problem with my solution …
Thnks in advance…
i tried checking if graph is bipartite or not…
https://www.ideone.com/OGDY8I
PLease do check …
can anyone give me test case where my code fails ?
here is the link - https://www.codechef.com/viewsolution/15423175
Well, You ought to go for vertex 2-coloring instead of bipartite graph testing…
You might like to have a look at my approach with explanation
Feel free to ask anything…
Please upvote
Well, i dont code in C language, so i can’t understand your code…
But, You might like to have a look at my approach with explanation
Feel free to ask anything…
Please upvote…
can anyone tell me what is wrong in this logic
- Initially all nodes are uncolored.
- As I get values of i,j and val, if both a[i] and a[j] are uncolored then if val is 0 then give them same color or if val is 1 then give different colors.
- If anyone of a[j] or a[i] is already colored then color other one accordingly if val is 1 then different color or same color if val is 0.
- If both a[i] and a[j] are colored then if val is 0 then they should have same color if not then matrix is wrong similarly if val is 1 then they should have different color if not the matrix is wrong.
- In all other cases matrix will be correct.
Hello! can anyone pls tell me why the solution on going according to author’s logic is getting WA? I have written code according to the logic explained in the “Author’s Solution” section of the editorial which seems to be absolutely correct. Any help is much appreciated. Thanks!! U can find my code here.
Simple solution can found only by sorting the initial m commands and then trying to assign the values to the array. This takes O( m*log(m) ) time, which is the time for sorting. U can see the solution here.