Thanks for pointing out!
https://www.codechef.com/viewsolution/37002426
i think i did almost same way…but i got WA. what’s wrong in my code ? please help me to find out…thanks
in the explanation of the problem in second query - The size of the largest connected group of cities in which parity of each city is odd after XOR with 8 is equal to 4 because, after XOR with 8, cities 2,1,5,3,6 have odd parity. Since 2 is not connected with either 1,5,3, or 6, therefore answer is equal to 4. weight of city 2 is 4 . 4 XOR 8 =12 (1100) how is this parity odd
@sau
correct during contest too I was thinking about this statement. I spent a lot of time on this.
in dfs function why you have written
if (!visited[it] && __builtin_parity(weight[it]) == check)
won’t you make your ans 0 otherwise ,i mean if we have encountered some mismatching parity wont the ans be 0 in that case
ya they should have a ask ques during contest thing in Codechef like in CF
2 Likes
the concept of odd even parity and its xor operation takes my whole day to find that formula in lon g challenge.
Even parity xor Even parity = Even parity .
odd parity xor odd parity = Even parity.
odd parity xor Even parity = odd parity
Even parity xor odd parity = odd parity
Can someone please see where i did wrong here ?
https://www.codechef.com/viewsolution/36993607
First i found values of largest even and odd connected parity nodes using dfs(respectively in variables e and o).
Then answered queries using same method.
the way u are counting connected components is wrong.
try this
1
5 4
4 6 9 10 2
1 2
1 3
1 4
2 5
0(queries-let it be any value)
ur even value is 2 (it should be 1)
ur odd value is 3(it shoud be also 1)
consider connected components only not all
3 Likes
why ans is coming wrong using the editorial ans
Thank you bro.
Now i got it where i did mistake.
Dry run your DFS, to make sure it’s correct.
1 Like
Thanks ,
This really helped what i was missing.
Thanks . Figured out what i was missing.
Anytime you are stuck with WA then just write a code which generates input randomly.
Pass that input to your program, and the one written by author.
compare the results
Ofcourse doing it manually is a very tedious job, so writing a script to perform above task is recommended.
Here is my script (for linux / wsl on windows)
#!/bin/bash
while((1))
do
python3 tmp.py > /dev/shm/testcase
a=$(diff <(./my < /dev/shm/testcase) <(./chef < /dev/shm/testcase) | wc -l)
if(($a!=0))
then
cat /dev/shm/testcase
read p
fi
done
I am using Python3 , i did similair approach using BFS , i first find connect components and max odd and even size then wrt parity of input K , i print either odd or even. but i my solutin says Run Time error. I am new to competative programming., can someone help please!!!
sir, in the question they said Bidirectional so the graph is non directed so entire [1,2,3,4,5] are connected component only. so even value is 2 odd value is 3 , I don’t know how it will be 1 for both??? I am new to Competitive programming could you please Help!!!
I use Python3
https://www.codechef.com/viewsolution/37212495
All are connected in total,but here according to the question we have to separatly deal with even and odd value connected components
and if we see the values 6 ,9,10(nodes2,3,4 respectively) which have 2 bits set are not connected with each other(i.e no edge in common),same goes for 4,2(nodes 1,5).
That is why the value of odd and even connected components having max size is 1 for both.
Nice Editorial. 