There can be a really easy greedy solution the problem.We can initialise the array A by -1.There is crucial observation that the array A can be constructed with only two values 0 and 1.Sort the index value pairs.Now if both the given index are unassigned,assign them according to the value given.Like 1 3 1 would mean 1 and 3 would be different .So initialise a[1] with 0 and a[3]=a[1]XOR val.Keep doing this and if at some point when both the indices are intialised with values!= -1 ,then check if they satisfy the given value,if not break and print -1.
The testcases for this problem were very weak.
[My solution][1] got an AC even though it is incorrect. It is easy to see that this fails in cases where 2 previously visited sets of weight 0 have an edge of weight 1 in between.
An example where my solution should fail is :
1
5 4
1 2 0
1 5 0
3 4 0
4 5 1
I reported the issue in the comments section of the problem link but to no avail. I wonder how many people with a similar solution got away with an AC.
[1]: CodeChef: Practical coding for everyone
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.