What I thought is we can see for the conditions when the array is not possible.
There would be 3 cases for this:
For an index (i, j) of the matrix a, if (i==j) but a(i, j) =1.
For two different indices (i1, j1) and (i2, j2) if(i1=j2) and (i2=j1) but a(i1, j1)! =a(i2, j2).
For three different indices if any two of them have one common index (i, j) then the number of 1’s at these three indices should not be 1 or 3. Eg. If three indices are (1,2), (1,4), (2,4) here for any two indices 1 index(i or j) is common. Then for this 1 should not be at all the three positions or there should not be only one 1 at any of these 3 indices.
Can you tell me if there is any problem with this logic.
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.
@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 ?
` 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;
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.
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.
Editorialist’s solution is what I majorly followed . But I must say, I learnt a lot of terminologies from editorial. Reminds me that I still have a long way to go…
@r_64 just my opinion
Although you do explain things in considerable detail, which I’m sure I will appreciate when going through the WEASELSC editorial
Well, to say the truth, i didn’t even read the solution line to line but only after seeing the PREREQUISITES, it was apparent to me that the solution discussed here would appear far more complex than it actually is!!!
Which, i believe, is never appreciable.
@meooow my solution resembles the editorial one considerably, but not in finer details as well as complexity as i think.